# SICP 1.2.4 Exponentiation

Published: 2020-06-20T17:04:58.000Z

Today I learned that ancient mit-scheme REPL could be improved with history & tab completion. Thanks to this StackOverflow answer. `sudo apt-get install rlwrap`, and then run scheme as `rlwrap scheme` That answer is not very recent too, but here we are trying to learn really ancient magic.

And this section really starts to feel like magic. In the end, I learned that there is a way to compute n-th Fibonacci number with time complexity `O(log(n))`. And just few sections before, authors show how computing Fibonacci sequence using wrong approach could blow up exponencially.

## Exercise 1.16: Fast exponentiation

``````(define (sqr x) (* x x))
(define (fast-exp x n)
(define (iter x n a)
(cond
((= n 0) a)
((even? n) (iter (sqr x) (/ n 2) a))
(else (iter x (- n 1) (* a x)))
)
)
(iter x n 1)
)``````

## Exercise 1.17: "Fast" multiplication

``````(define (double x) (+ x x))
(define (halve x) (/ x 2))

(define (fast-m a b)
(cond ((= b 1) a)
((even? b) (fast-m (double a) (halve b)))
(else (+ a (fast-m a (- b 1)))
)
)``````

## Exercise 1.18: Iterative multiplicaton

``````(define (fast-m a b)
(define (iter a b p)
(cond
((= b 1) (+ a p))
((even? b) (iter (double a) (halve b) p))
(else (iter a (- b 1) (+ p a)))
)
)
(iter a b 0)
)``````

## Exercise 1.19: Fast Fibonacci

With this exercise first, you discover that there is Fibonacci sequence inside Fibonacci formulas, and then, you figure out from where there appears exponential rise. Magical:

``````(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* p p) (* q q))   ; compute p'
(+ (* q q) (* 2 p q)) ; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))``````

I not dediced yet on how to get latex in Hugo, so I'll not add here my calculations for `p'` and `q'`.