No matter what programming language you are learning, Fibonacci numbers calculation is just too classic to skip. It seems very easy to implement, but also can be deep enough to catch up with, especially when the number is super big. Have you thought that ever before?
It can be super easy to implement using recursion in just one line of code, even using Java.đ
1 | int fib(int n) { |
And to make you understand the basic optimization idea, monetization mechanism will be introduced via an integer array or a HashMap, but the idea is same: calculate once and only once, so that those poor rabbits would feel life much easier.
Add just one more line of code and thanks to the Lambdas feature provided since JDK8, life is much easier nowadays.
1 | private static Map<Integer, Integer> CACHE = new HashMap<>(); |
There is always someone scared of the famous StackOverflowError, they would tell you not to use recursion but do an iterative way, like this:
1 | int fib(int n) { |
Obviously, the integer array can be avoided, you can just keep three values and update them till the end, but thatâs not the problem we want to discuss here. You would have probably found that itâs very easy for the result to be much bigger than the upper limit of int, long, double. For example, if we input n as 2048, what will be the exact result then?
454153044374378942504557144629068920270090826129364442895118239027897145250928343568434971 803477173043320774207501029966396250064078380187973638077418159157949680694899576625922604 895968605634843621876639428348247300097930657521757592440815188064651826480022197557589955 655164820646173515138267042115173436029259905997102292769397103720814141099147144935820441 85153918055170241694035610145547104337536614028338983073680262684101
Itâs 4.54 * 10^427. As for Java, for this kind of problem, you have no other choice but BigInteger, and itâs very easy to
use.
1 | private static Map<Integer, BigInteger> CACHE = new HashMap<>(); |
Congratulations! You will get a BOMB exploding like this:1
2
3Exception in thread "main" java.lang.StackOverflowError
at java.util.HashMap.hash(HashMap.java:339)
at java.util.HashMap.computeIfAbsent(HashMap.java:1099)
You may use -Xss4m
to shut it up, or resolve it in an iterative way a little bit optimized, wherein we wonât waste space to build an array. Yes, itâs right, recursion is easy to think of and implement, but itâs just too close to StackOverflowError.
1 | BigInteger fib(int n) { |
BigInteger, whatâs the secret behind it that it can represent a number beyond the upper limit of all primitive data types of Java?
The idea is still simple, but the implementation can be complex, especially when highly optimized is a must. bigint in Github would give you more information on how Timothy Buktu approaches and optimizes it.
There is a famous quote in The Lord of The Rings by Sam, âI canât carry it for you, but I can carry youâ, as for BigInteger, it seems should be âI canât carry it for you, and I canât carry you, but I can carry a segment of you.âđ
Yes, the whole number is too big, but if we split it into many parts, then we will find each part might be within the upper limit, if we store each of them in an array, and perform the calculation in binary level, also handle the carrying part well, then a container to store a big number will be possible.
Pretty cool and smart, right? But what exactly is under the hood? Letâs check it out in the next post.
TO BE CONTINUED