Fibonacci numbers: the slow way or the fast and lazy way

Fibonacci numbers are a series of numbers such as 1,1,2,3,5,8,13,21,34,55,….

You can write a simple program, such as the one given below, in any language such as perl, python, ruby, javascript, php, java, haskell etc.

slowFib 0 = 1 slowFib 1 = 1 slowFib n = slowFib (n -2 ) + slowFib (n – 1)

This algorithm is extremely slow, in any language. It takes exponential time — 2^n

This program was compiled to binary by the haskell compiler ghc. I am not showing the wrapper that takes user input and calls slowFib.

The CPU time taken is shown below. (Core 2 Duo 2.3 GHZ, 2 Gig RAM)

time ./slowfib 41 267914296 real 0m17.375s time ./slowfib 42 433494437 real 0m28.109s time ./slowfib 43 701408733 real 0m45.465s

One of the CPUs was pegged to 100% usage. To compute 43rd Fibonacci number, you compute the 42nd Fibonacci number (takes 28 seconds) and add it to the 41st Fibonacci number (takes 17 seconds). So it takes 28+17 = 45 seconds. Calculations done for the 41st Fibonacci number are repeated for 42nd number which are again repeated for 43rd number and so on and that is the reason for the inefficiency.

If you want the 100th Fibonacci number, you will have to wait for a long, long time.

We can do lot better than this. Let us write the first 10 Fibonacci numbers:

1   1   2   3   5   8  13  21  34  55

Now, skip the first number and write the remaining Fibonacci numbers:

1   2   3   5   8  13  21  34  55

Now let’s put them in 2 rows and add the columns:

1   1   2   3   5    8  13  21  34  55


1   2   3   5   8   13  21  34  55

2   3   5   8  13   21  34  55  89
--------------------------------------

Now, the sum is nothing but the Fibonacci sequence except that first 2 Fibonacci numbers 1 and 1 are missing. The first row is the Fibonacci sequence we are interested in. The second row is the tail of the Fibonacci sequence. Tail is the list without the first element. The sum is the tail of the tail of the Fibonacci sequence. Initially, we have only the first 2 Fibonacci numbers, 1 and 1. So the 2 rows will look like this:

1 1
1

The second row has only one element as it is the tail of the first list which has only 2 elements.

Now let us add the 2 rows

1 1


1

2
----

But we know that the sum is the tail of the tail of the list. Tail of the Tail, as we have seen before, is where we remove the first 2 elements. This means that 2 should be third entry in the Fibonacci list. Let us append it to the first row:

1 1 2


1

2
----

Now that the first row has 3 elements, the second row (which is the tail of the first row) can have 2 elements.

1 1 2


1 2

2
----

Now, we can sum the second column

1 1 2


1 2

2 3
----

The sum, as we said before, is the tail of the tail of the Fibonacci sequence and it has one more number now — 3. Repeating the procedure described above, we get

1 1 2 3


1 2 3

2 3 5
--------

which again becomes

1 1 2 3 5


1 2 3 5

2 3 5 8
--------

and so on. The first row, which is the Fibonacci sequence, which started as 1,1 has now become 1,1,2,3,5. The operations we are doing are basically additions of two lists. We can stop this process as soon get the Fibonacci number we are interested in.

Now, we cannot (at least easily) write such a program in languages such as perl, python, ruby, javascript, php, java. These languages are called strict languages. To write such a program, you need a lazy language like Haskell. Lazy languages don’t compute something unless it is required. For example in haskell you can define

nines = 9:nines

which is an infinite list of numbers where every number is 9. Strict languages, seeing this recursive definition, will keep expanding nines until they run out of memory. Haskell, being a lazy language, won’t do anything. A lazy person like me can truly identify with this! When you ask Haskell to compute “take 4 nines” it will return [9,9,9,9]. If you ask  “take 8 nines”, you will get [9,9,9,9,9,9,9,9] and so on. So, in haskell, you can write the method where we add 2 lists as

fibs = 1:1:zipWith (+) fibs (tail fibs)

A one line program that computes the Fibonacci series — blazingly fast! Let us dissect the program 1:1:zipWith (+) fibs (tail fibs)

Remember, we started out with the first row having 1 and 1. That is what is shown here a 1:1. “zipWith (+)” essentially adds 2 lists. For example, zipWith (+) [1,2,3] [4,5,6] will give you [5,7,9]. So we are using zipWith to (lazily) add the Fibonacci list with the tail of the Fibonacci list, as was described earlier.

Now, if you ask Haskell to evaluate fibs, it will start printing all the Fibonacci numbers and the program will never stop until it runs out of memory. Haskell, being a lazy language, will only compute what is required and in this case you are asking it to print all the numbers. However, if you ask it for the first 10 Fibonacci numbers, like this “take 10 fibs”, it will give you “[1,1,2,3,5,8,13,21,34,55]“, computing only what is required.

If we want just the nth Fibonacci number, we can call “take n fibs” and take the last number in the list. Here’s the output of this program.

time ./fibs 43 701408733 real 0m0.002s

The program took hardly any time. Compare this with 45 seconds taken by the slow version. Now, for fun, let us compute the 5000th Fibonacci number. Let us not even think of doing it with the old algorithm as it will take over thousands of years to complete!

time ./fibs 5000 6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626 real 0m0.005s

The program took hardly any time!. How about the 10000 Fibonacci number? Takes hardly any time. The right algorithm makes all the difference. And, in this case, a lazy algorithm matched perfectly with Haskell’s lazy evaluation, and the problem was solved with a one line program!

time ./fibs 10000 54438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048089793531476108466259072759367899150677960088306597966641965824937721800381441158841042480997984696487375337180028163763317781927941101369262750979509800713596718023814710669912644214775254478587674568963808002962265133111359929762726679441400101575800043510777465935805362502461707918059226414679005690752321895868142367849593880756423483754386342639635970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953884712441028463935449484614450778762529520961887597272889220768537396475869543159172434537193611263743926337313005896167248051737986306368115003088396749587102619524631352447499505204198305187168321623283859794627245919771454628218399695789223798912199431775469705216131081096559950638297261253848242007897109054754028438149611930465061866170122983288964352733750792786069444761853525144421077928045979904561298129423809156055033032338919609162236698759922782923191896688017718575555520994653320128446502371153715141749290913104897203455577507196645425232862022019506091483585223882711016708433051169942115775151255510251655931888164048344129557038825477521111577395780115868397072602565614824956460538700280331311861485399805397031555727529693399586079850381581446276433858828529535803424850845426446471681531001533180479567436396815653326152509571127480411928196022148849148284389124178520174507305538928717857923509417743383331506898239354421988805429332440371194867215543576548565499134519271098919802665184564927827827212957649240235507595558205647569365394873317659000206373126570643509709482649710038733517477713403319028105575667931789470024118803094604034362953471997461392274791549730356412633074230824051999996101549784667340458326852960388301120765629245998136251652347093963049734046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501 real 0m0.010s

As Dana Carvey would say “Well, isn’t that special!” For more info on lazy evaluation in Haskell, look at the 14th chapter in Paul Hudak’s book. There is also a free online Beta book called Real World Haskell, to be published soon by O’Reilly. The online version has been a work in progress for about a year and is almost complete.

Tags: haskell