Part I:
=======
1. Write (pow-fast-i b n) that uses an iterative process.
Use this relation:
b^n = (b^2)^n/2 when n is even
2. How long does it take to compute (pow-fast-i 2 1e6)?
3. Trace (pow-fast-i 2 10)
Part II:
=======
a. Assume the multiplication,*, and the division,/, operators are broken. You must define
your own version of mult that works only with nonnegative integers.
Test Cases:
(mult 3 0) = 0
(mult 3 1) = 3
(mult 3 10) = 30
(mult 10 3) = 30
(mult 10 100000000000) = 1000000000000
b.Identify if your solution uses an iterative or recursive process.
c.Time your function. Does the order of the arguments influence the time?
If so, find a way to make the runtime of (mult a b) equal to the runtime
of (mult b a) for all arguments.
d. The following is known as "The Russian Peasant Multiplcation Algorithm".
a x b =
1. if b = 0 the answer is 0
2. if b is even then a x b = (a + a) x (b / 2)
3. if b is odd then a x b = a + (a x (b - 1))
ex. 2 x 10 = 4 x 5
= 4 + 4 x 4
= 4 + 8 x 2
= 4 + 16 x 1
= 4 + 16 + 16 x 0
= 4 + 16 + 0
= 20.
Implement a new version of mult that uses the algorithm. You may use the following functions:
(define double (lambda (n) (+ a a))
(define half (lambda (n) (quotient n 2))
e. Is the new mult function faster? Why?