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 = 0
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
165580141
real 0m17.375s
time ./slowfib 42
267914296
real 0m28.109s
time ./slowfib 43
433494437
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
433494437
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
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
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
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
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.