Vikrant

In my previous post about Fibonacci series, I discussed about some functions to compute fibonacci numbers. I started with a function of exponential complexity and ended it with a lazy O(N) complexity algorithm. is it possible to optimize it beyond O(N)? I found this beautiful algorithm while going through suggested exercise in SICP

Lets look at iterative fibonacci first

fibiter a b count 
    | count==0  = b
    | otherwise = fibiter a+b a count-1

fib = fibiter 1 0

This takes N operations for computing fib N. Look carefully at the transformation of a and b in fibiter function.

a'->a+b
b'->a

If we apply transformation T on (a,b) we get new (a',b'). To get N th Fibonacci number we will to apply this transformation N times in pair (1,0). We have to consider T as special case of transformation

a'-> bq + aq + ap
b'-> bq + ap

with p = 0 & q = 1. (Hats off to the person who discovered this brilliant transformation!). Now Fibonacci computation will look something like this.

T[p,q] (a,b)        -> (a'b')

once more apply the transformation

T^2[p,q] (a,b) -> (a'',b'')

this is equivalent to

T[p',q'] (a,b)        -> T[p,q] T[p,q] (a,b)
.                 -> T[p,q] (bq+aq+ap, bp+aq)
.                 -> T[p,q] (a',b')
.                 -> (b'q+a'q+a'p, b'p+a'q)
.                 -> ((bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p , (bp+aq)p + (bq + aq + ap)q)
(bq'+aq'+ap', bp'+aq')-> ( b (q^2+2pq) + a (q^2+2pq) + a (p^2+q^2), b (p^2+q^2) + a (q^2+2pq)

this gives us p' and q' in terms of p & q

p' = p^2 + q^2
q' = q^2 + 2pq

this gives us a handy way to square the transformation T! How does it help us in improving complexity of Fibonacci? That you will understand immediately if you know how to compute exponential of a number using multiplication and squaring. Lets look at how do we compute b raised to power n.

expiter accumulator b n 
    | n == 1    = accumulator
    | otherwise = expiter b*accumulator b n-1

exp = expiter 1

This is going to take n operations for computing nth power of b. But this can be improved further. For example b^4 can be computed by squaring b^2, b^8 can be computed by squaring b^4 etc.

expiterfast  accumulator b n
    | n == 1    = accumulator
    | even n    = expiterfast accumulator*accumulator b (n `div` 2)
    | otherwise = expiterfast b*accumulator b n-1

expfast = expiterfast 1

This will compute b^N in O(logN)! This proves that if we know how to multiply and how to square, we can compute Nth power in O(logN) complexity. Use the same technique for applying the transformation we discussed for Fibonacci.

fibiter a b p q count 
    | count == 0        = b
    | odd count         = fibiter (b*q + a*q + a*p) (b*p + a*q) p q (count -1)
    | otherwise         = fibiter a b p1 q1 (count `div` 2)
            where 
                p1 = p*p + q*q
                q1 = q*q + 2*p*q


efficientfib = fibiter 1 0 0 1

last updated 1 year ago #