Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement