Why I love the Fibonacci program — Part 1 — With Java
There are few programs which teach us so much in so few lines of code.One of the best programs I like to code and see people code is computing the Fibonacci number.
F(n) = F(n-1) + F (n-2)
The Fibonacci program can be approached in 2 ways — recursive and iterative.
Let’s start with the recursive one.
public static int getFibRecursive(int n)
{
if(n==1) return 1;
if(n==2) return 2;
int fibonacci = getFibRecursive(n-1) + getFibRecursive(n-2);
return fibonacci;
}Plain and simple right? Wait, hold your horses. Let’s start computing.
System.out.println("Fibonacci term 8th is : " + getFibRecursive(8));
System.out.println("Fibonacci term 18th is : " + getFibRecursive(18));
System.out.println("Fibonacci term 118th is : " + getFibRecursive(118));
System.out.println("Fibonacci term 1118th is : " + getFibRecursive(1118));While the 8th and 18th term gets computed correctly, the recursive version gets stuck at 118th term. Well, that is a very low number and our dreams of progressing to higher numbers are shattered.
In short, the call stack generated for computing the 118th term is unsustainable for the machine. This quickly shows you the limitations of call stack sizes and makes you wonder the utility of recursion for big numbers.
Let’s try a new approach, shall we?
This time let’s use the iterative approach.
public static int getFibonacciIterative(int n)
{
int fibonacci = 0;
if(n==1) return 1;
if(n==2) return 2;
int prev_older = 1;
int prev_newer = 2;
for(int k=3;k<=n;k++)
{
fibonacci = prev_older + prev_newer;
prev_older = prev_newer;
prev_newer = fibonacci;
System.out.print(fibonacci + ",");
}
System.out.println();
return fibonacci;
}Voila! It works, my machine is no longer stuck. Let’s print the result of first 50 numbers.
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, -1323752223, 512559680, -811192543, -298632863, -1109825406]What the heck! Negative numbers. Who would have thought so. How is it even possible. Well, congratulations! You have hit integer limits.
So, what to do? Let’s try with long then. Let’s print the result of first 50 numbers.
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074]It works! Am I free now? Can I finally get to the 118th term. Let’s try. Let’s print from 50th till 100th.
[20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, -6246583658587674878, 1293530146158671551, -4953053512429003327, -3659523366270331776, -8612576878699335103, 6174643828739884737, -2437933049959450366, 3736710778780434371, 1298777728820984005]Holy crap! Negative numbers again. Who in the world could have thought that computing Fibonacci number can be so hard. After all, it just had a one line formula!
At this point, you have already learnt so much. You have seen call stack limitations and data type limitations.
java.lang.Integer public static final int MAX_VALUE = 2147483647A constant holding the maximum value an int can have, 2^31-1.java.lang.Long public static final long MAX_VALUE = 9223372036854775807LA constant holding the maximum value a long can have, 2^63-1.
Now it is up to you to understand why integer and long have this specific limitations. That will take you to binary system.
Well, so is there any solution. Thankfully, there is.
public class BigIntegerImmutable arbitrary-precision integers.
Using BigIntegers frees us from the limitations of ints and longs. Let’s print some numbers, shall we. Let’s print from 50th till 100th.
[20365011074->11 digits, 32951280099->11 digits, 53316291173->11 digits, 86267571272->11 digits, 139583862445->12 digits, 225851433717->12 digits, 365435296162->12 digits, 591286729879->12 digits, 956722026041->12 digits, 1548008755920->13 digits, 2504730781961->13 digits, 4052739537881->13 digits, 6557470319842->13 digits, 10610209857723->14 digits, 17167680177565->14 digits, 27777890035288->14 digits, 44945570212853->14 digits, 72723460248141->14 digits, 117669030460994->15 digits, 190392490709135->15 digits, 308061521170129->15 digits, 498454011879264->15 digits, 806515533049393->15 digits, 1304969544928657->16 digits, 2111485077978050->16 digits, 3416454622906707->16 digits, 5527939700884757->16 digits, 8944394323791464->16 digits, 14472334024676221->17 digits, 23416728348467685->17 digits, 37889062373143906->17 digits, 61305790721611591->17 digits, 99194853094755497->17 digits, 160500643816367088->18 digits, 259695496911122585->18 digits, 420196140727489673->18 digits, 679891637638612258->18 digits, 1100087778366101931->19 digits, 1779979416004714189->19 digits, 2880067194370816120->19 digits, 4660046610375530309->19 digits, 7540113804746346429->19 digits, 12200160415121876738->20 digits, 19740274219868223167->20 digits, 31940434634990099905->20 digits, 51680708854858323072->20 digits, 83621143489848422977->20 digits, 135301852344706746049->21 digits, 218922995834555169026->21 digits, 354224848179261915075->21 digits, 573147844013817084101->21 digits]Finally, we seem to be getting some traction. Let’s try the 118th, 1118th and 11118th term now. Fingers crossed!
System.out.println("Fib term 118th is : " + getFibIterativeBigInteger(118));
System.out.println("Fib term 1118th is : " + getFibIterativeBigInteger(1118));
System.out.println("Fib term 11118th is : " + getFibIterativeBigInteger(11118));Fib term 118th is : 3311648143516982017180081Fib term 1118th is : 321872918259779894910101296197132795139173273123424544111284023938595776499489243134463539260407815390217807650561946032482172719446324534132709019249279403095897175808290970166661828945376076081964741360258694885538846256970185204706Fib term 11118th is : 24215137383814753677170845251344906506880519487181548962543128318532104867893136570000217543506135185347216939352544122507315616267505542631830758250477377985791489843476414135088151487486325628993575493175073272786139524173115693622367842298882181840710789571954666415483323267120542637656112844839728834418429729604596189215962480035802562526723544037252174477759503895469758985525769036272101330597159703568365269406076656831922722068611366216886939532972263701955111791643321988299676099932403523074777237853788939941544066952404096359013442008262394546922949158282116900364294457461251167574595417623431306205460984573480313961702440294938647608075688312968769296300415675368473466014470783640604674081781896887101690369816577055378443730942284594124361439732639698438514472484129410292189688190063385826751564213258233839294583285508583287475927152733370698116926378641725204763696890867079951723600359366947565341351538678649536289275546415545576076589228209179867485382908110088686375789803073200847920740331056983211990289094111624850534356794068771925106493685158295191534801918686177582330916064562833108506146222764189076658998441112991658027785672065659010569326931945575442721270502023917943420426743187480471953213106171162800636276503243199449503021779688316907048151855625392054930676511781425920756353885746175401255053511128970694288520119686681186387423917299973973733973314939782635992366678636712608248513213301715807890099071463601530853687714012984357966001434642614623029027823479834511705504081926713885058440356230923841513570179159132760517772667438858504636443312472790777046678548706285334686358880751294647133683644310664839269550350153739641603007353518015805090617907351477077992896282693353220517241536928782061180944084354946589484088065813419955266305611340693264565678041372886422309582166378850998804059032827891219533204990686538545371105646692056843006299793174085172080267590091782260199376286059885056169389946972304623499931015106459587626842748287912252869816334016390192036142731503397840267097571975608585392330142037962923979365073777790831678127590847086079640993966658546342721864998709916748960121487774711636982347845077527699262454679845111413978531162096875537590207844112880619159290513402632201143200680305760375076120528171804769095592325135664244437098420884822091581
Finally! It seems to be working. The numbers are getting insanely large. What will the 1 millionth term look like!
Well this ends our journey for now. A simple program taught us so much. Are there other ways of doing this? Ofcourse! There are direct formulas, better algorithms which can teach you further and take you deeper.
Now, this is how I imagine, they should teach us at school, isn’t it!
