#lang racket

;; 1.16

;; expt-iter is tail-recursive hence iterative

(define (iterative-fast-expt b n)
  (define (expt-iter coeff base power)
    ; the invariant is coeff * base ^ power = b ^ n
    (cond [(zero? power) coeff]
          [(even? power) (expt-iter coeff (sqr base) (/ power 2))]
          [else (expt-iter (* base coeff) (sqr base) (/ (sub1 power) 2))]))
  (expt-iter 1 b n))

(iterative-fast-expt 2 10)
;; 1024
(iterative-fast-expt 3 5)
;; 243
(time (iterative-fast-expt 2 1234))
;; cpu time: 0 real time: 0 gc time: 0
;; 295811224608098629060044695716103590786339687135372992239556207050657350796238
;; 924261053812082089933038176093702721248284094494136211066544377518349572681192
;; 920386118201521832389936024879031137085494026686245211006117942703402327660993
;; 170980488874938090231273982538640111837184

;; 1.17

(define (double int) (* int 2))
(define (halve even-int) (quotient even-int 2))

(define (fast-mult a b)
  (cond [(= b 1) a]
        [(even? b) (fast-mult (double a) (halve b))]
        [else (+ a (fast-mult (double a) (halve (sub1 b))))]))

(fast-mult 2 3)
;; 6
(fast-mult 3 4)
;; 12
(time (fast-mult 987654321987654321 123456789123456789))
;; cpu time: 0 real time: 0 gc time: 0
;; 121932631356500531347203169112635269

;; 1.18

;; mult-iter is tail-recursive hence iterative

(define (iterative-fast-mult a b)
  (define (mult-iter rem num1 num2)
    ; the invariant is rem + num1 * num2 = a * b
    (cond [(zero? num2) rem]
          [(even? num2) (mult-iter rem (double num1) (halve num2))]
          [else (mult-iter (+ rem num1) (double num1) (halve (sub1 num2)))]))
  (mult-iter 0 a b))

(iterative-fast-mult 2 3)
;; 6
(iterative-fast-mult 3 4)
;; 12
(time (iterative-fast-mult 987654321987654321 123456789123456789))
;; cpu time: 0 real time: 1 gc time: 0
;; 121932631356500531347203169112635269

;; 1.19

(define (exponential-fib n)
  (if (< n 2)
    n
    (+ (exponential-fib (- n 1)) (exponential-fib (- n 2)))))

;; The Fibonacci matrix is T(p, q) where p = 0 and q = 1.

;; T(p, q) is [(p + q, q), (q, p)] and we want to pre-compute T(p, q) ^ 2 as
;; some T(p', q') in order to implement the iterative exponentiation process.

;; T(p, q) ^ 2 = [((p + q) ^ 2 + q ^ 2, q * (p + q) + q * p),
               ;; (q * (p + q) + q * p, p ^ 2 + q ^ 2)]
            ;; = [(2 * q ^ 2 + 2 * p * q + p ^ 2, q ^ 2 + 2 * p * q),
               ;; (q ^ 2 + 2 * p * q, q ^ 2 + p ^ 2)]

;; So p' = q ^ 2 + p ^ 2 and q' = q ^ 2 + 2 * p * q.

(define (logarithmic-fib n)
  (define (fib-iter a b p q cnt)
    ; the invariant is (a, b) acted on by T(p, q) cnt times = (Fib(n + 1), Fib(n))
    (cond [(zero? cnt) b]
          [(even? cnt) (fib-iter a
                                 b
                                 (+ (sqr p) (sqr q))
                                 (+ (sqr q) (* 2 p q))
                                 (/ cnt 2))]
          [else (fib-iter (+ (* b q) (* a q) (* a p))
                          (+ (* b p) (* a q))
                          p
                          q
                          (sub1 cnt))]))
  (fib-iter 1 0 0 1 n))

(time (exponential-fib 30))
;; cpu time: 31 real time: 38 gc time: 0
;; 832040
(time (logarithmic-fib 30))
;; cpu time: 0 real time: 0 gc time: 0
;; 832040


(time (exponential-fib 40))
;; cpu time: 4594 real time: 4608 gc time: 0
;; 102334155
(time (logarithmic-fib 40))
;; cpu time: 0 real time: 1 gc time: 0
;; 102334155

(time (logarithmic-fib 1000))
;; cpu time: 0 real time: 0 gc time: 0
;; 434665576869374564356885276750406258025646605173717804024817290895365554179490
;; 518904038775209689623239873322471161642996440906533187938298969649928516003704
;; 47613779516684922887