math - What does squaring a transformation mean? -

math - What does squaring a transformation mean? -

i trying understand solution read exercise defines logarithmic time procedure finding nth digit in fibonacci sequence. problem 1.19 in construction , interpretation of computer programs (sicp).

spoiler alert: solution problem discussed below.

fib(n) can calculated in linear time follows: start = 1 , b = 0. fib(n) equals value of b. initially, n = 0, fib(0) = 0. each time next transformation applied, n incremented 1 , fib(n) equals value of b.

<-- + b b <--

to in logarithmic time, problem description defines transformation t transformation

a' <-- bq + aq + ap b' <-- bp + aq

where p = 0 , q = 1, initially, transformation same 1 above.

then applying above transformation twice, exercise guides express new values a'' , b'' in terms of original values of , b.

a'' <-- b'q + a'q + a'p = (2pq + q^2)b + (2pq + q^2)a + (p^2 + q^2)a b' <-- b'p + a'q = (p^2 + q^2)b + (2pq + q^2)a

the exercise refers such application of applying transformation twice "squaring transformation". right in understanding?

the solution exercise applies technique of using value of squared transformations above produce solution runs in logarithmic time. how problem run in logarithmic time? seems me every time utilize result of applying squared transformation, need 1 transformation instead of two. how successively cutting number of steps in half every time?

the solution schemewiki.org posted below:

(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter b p q count) (cond ((= count 0) b) ((even? count) (fib-iter b (+ (square p) (square q)) (+ (* 2 p q) (square q)) (/ count 2))) (else (fib-iter (+ (* b q) (* q) (* p)) (+ (* b p) (* q)) p q (- count 1))))) (define (square x) (* x x))

the exercise refers such application of applying transformation twice "squaring transformation". right in understanding?

yes, squaring transformation means applying twice or (as case in solution exercise) finding transformation equivalent applying twice.

how problem run in logarithmic time? seems me every time utilize result of applying squared transformation, need 1 transformation instead of two. how successively cutting number of steps in half every time?

squaring given transformation enables cutting downwards number of steps because values of p , q grow much faster in squared transformation in original one. analogous way can compute exponents using successive squaring much faster repeated multiplication.

so how successively cutting number of steps in half every time?

this in code given. whenever count even, (/ count 2) passed count on next iteration. no matter value of n passed in on initial iteration, on alternating iterations (worst case).

you can read blog post on sicp exercise 1.19: computing fibonacci numbers if want see step-by-step derivation of squared transformation in exercise.

math sicp