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 8 months ago #

It took few beautiful lines of haskell code to generate these beautiful shapes :)

Sierpinskie Triangle

module Main
where
import Graphics.HGL

fillTri::Window->Int->Int->Int->IO()
fillTri w x y size =
    drawInWindow w ( withColor Blue
    (polygon [(x,y),(x+size,y),(x,y-size)]))


minSize::Int
minSize = 8

sierpinskiTri::Window->Int->Int->Int->IO()
sierpinskiTri w x y size = 
    if size < minSize
    then fillTri w x y size
    else let size2 = size `div` 2
      in do sierpinskiTri w x y size2
        sierpinskiTri w (x+size2) y size2
        sierpinskiTri w x (y-size2) size2

main =  runGraphics(
    do w <- openWindow "Sierpinski Triangle" (400,400)
       sierpinskiTri w 50 300 256
       k <- getKey w
       closeWindow w
    )

Snowflake

Snowflake

last updated 1 year ago #

Mathematician D. R. Kaprekar played with four digit numbers and found a magic number 6174. He did something now known as kaprekar operation. Kaprekar operation can be defined as follows. Choose any four digit number. Permute its digits to form maximum and minimum number using those digits. take difference of these two numbers. One gets new number. On this number again keep performing above operation. Surprisingly the operation tends to converge the result to a unique number, 6174! I was delighted to see this nice property of 6174. I wrote haskell programme for it to verify as well as experiment more. Once programme is ready it was easy for me to perform kaprekar operation for various numbers with different number of digits. 3 digit numbers converged to 495. Then I was expecting that even 6, 7 or 8 digit number should converge to some number! But it didn't. Still there was interesting property seen! Although these number do not converge to a single number, the process gets trapped between more than one number. It converges to some kind of sequence. You can see similar patterns for numbers with same number of digits. I generated following patterns for numbers with digits 5, 6 and 7.

haskell function for performing kaprekar operation...

-- performs kaprekar operation on given number for given number of digits
kaprekar::Int->Int->Int
kaprekar n numDigits =
    let
        digits = paddZeros (split n) numDigits
        max = join (quicksort digits)
        min = join (reverse (quicksort digits))
    in (max - min)

last updated 1 year ago #

do you know people write poems in some programming languages? Perl is famous for such things! see Perl Limerics , Perl poetry contest. But what about a language that writes poems? well, python can do that! And mind you it writes a good high level philosophic poem! on your command prompt type

python -c "import this"

and see what happens! it prints following poem

The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

last updated 1 year ago #

Few days back I started playing with Haskell. It took a while to get into pure functional paradigm. Going in this new programing world was fascinating as well as frightening! Frightening!..yeah..because it was a shock for python/C/Java programmer to imagine programming without destructive updates, to see that once assigned you can’t reassign values to variables! And many more surprises, I could not find loops! Loops have to be programmed using recursion! But after getting in here one feels Aha…. to see that your 2-3 lines code can do wonders, while equivalent code in C++/Java code fails to give that kick. So my journey in this wonderland started with Fibonacci numbers. Recently learned functional paradigm instantly gave me easy answer

– Usual recursive fibonaci
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

it was fine till I asked for fib 30, the programme took hours to compute fib 100! oooolaaa, I did the mistake. Memories went back to initial programming lessons. A student programmer is always advised by master programmer that although recursion is beautiful, it is not efficient, always try to put your recursion in the from of iterative loop. But then there are no loops in Haskell! Through some iterations I reached to following piece of code

-- fibonacci sequesnce generator
fibseries fibs n =
if length fibs < n 
    then fibseries ((fibs!!0 + fibs!!1):fibs) n
    else fibs

-- efficient fibonacci
fibonacci n = 
head (fibseries [1,1] n)

and then soon I improved to following

fibonacci n = fib n 1 1
   where
      fib 1 a _ = a
      fib 2 _ b = b
      fib n a b = fib (n-1) b (a+b)

Anand had given me idea about infinite lists in lisp long back. That time i was surprised to see something infinite on a computer. Today I felt enlightened after using it!

-- infinite series!
fibs = 1 : 1 : [ a+b | (a,b) <- zip fibs (tail fibs) ]

last updated 1 year ago #