1. Let k be arbitrary. Describe an input n for which the doubling search from the last exercise yields a significant improvement on the running time of the algorithm for inputs k and n. 2....

1. Let k be arbitrary. Describe an input n for which the doubling search from the last exercise yields a significant improvement on the running time of the algorithm for inputs k and n.

2. (programming required) Implement, in a programming language of your choice, all three of these algorithms (mod-and-div, mod-and-div-faster, and the doubling-search tweaked version of mod-and-div-faster from the previous exercises) to compute n mod k and ⌊n/k⌋