(programming required) Write a program that implements the Extended Euclidean algorithm. (Rec ommended: if you did Exercises 7.11–7.16, compute m mod n and ⌊ m n ⌋ with a single call to...

(programming required) Write a program that implements the Extended Euclidean algorithm. (Rec

ommended: if you did Exercises 7.11–7.16, compute m mod n and ⌊ m n ⌋ with a single call to mod-and-div-faster(m, n).)

I have a friend named Nikki, who’s from New Zealand. Nikki and I went out to eat together, and I paid for both dinners. She was going to pay me back, in cash—but she had only New Zealand dollars [NZD]. (I was happy to take NZDs.) Nikki had a giant supply of 5NZD bills; I had a giant supply of 5 U.S. dollar [USD] bills. At the time, the exchange rate was 5NZD = 3USD (or close enough to 5 : 3 for two friends to call it good).

Exercises 7.11

The code for mod-and-div-faster as written uses division, by averaging lo and hi. Modify the algorithm so that it uses only addition, subtraction, multiplication, and comparison.

Exercises 7.16

Run the three algorithms from the previous exercise to compute the following values: 2³²
mod 202, 2 32 mod 20²⁰, and 2³²
mod 3¹⁵. How do their speeds compare?