Yesterday, I wrote a function for Todd to show him some Java since he's learning it. It was a Fibonacci sequence calculator. Basically, you pass in the index of the sequence that you want, and it'll calculate it for you. So, today, I'm killing some time, and I wanted to figure out how much time it took to figure out some high up numbers of the sequence. Well, the function that I wrote originally pretty much sucks, but it works and it conveys some pretty fun stuff in computer science. First, an explanation.

The Nth number in the Fibonacci sequence is defined as the (N-1)th number plus the (N-2)th number. Or, the Sum of the previous two fibonacci numbers in the sequence. The sequence starts as 1,1,2,3,5,8,13,21,34, ... ending with F(N-1)+F(N-2), or F(Infinity-1)+F(Infinity-2). So it doesn't end. Anyway, there's some good documentation on it out there. Here's the first function I wrote:

public long fibo(int n){
    if (n <= 0) return 0;
    if (n <= 2) return 1;
    long ret = fibo(n-1) + fibo(n-2);
    return ret;
}

Here's the new, much faster function :

public BigInteger fibo2(int n){
    if (n < 3) return BigInteger.ONE;
    BigInteger fn = BigInteger.ONE;
    BigInteger last = BigInteger.ONE;
    BigInteger last2 = BigInteger.ONE;
    for (int i = 0; i < n-2; i++){ // n-2 because first 2 are 1
        last = fn.add(BigInteger.ZERO);
        fn = fn.add(last2);
        last2 = last.add(BigInteger.ZERO);
    }
    return fn;
}

I had to use BigInteger (in the java.math package) because after about 100, "long" couldn't fit the result anymore! That's a big F@#%$!$#!ing number that a long could hold!! But not big enough.

For mathematical clarity, there is a formula out there, called Binet's formula, that calculates the Nth fibonacci number.

F(n) = (a^n - b^n)/(a - b)

I'm having problems with types, I can't get it working.

But for the fun of it, here's some output:

For #40:
102334155
Fibo2 for fibonacci #40 took 0 milliseconds.
102334155
Fibo for fibonacci #40 took 4811 milliseconds.

For #42:
267914296
Fibo2 for fibonacci #42 took 10 milliseconds.
267914296
Fibo for fibonacci #42 took 12955 milliseconds.

As you can imagine, the second one in the results (the function simply named "fibo") will be an unbearable burden to the rest of my experiment. So, I'm getting rid of it and will show you some major f@#%R@#ing numbers produced by "Fibo2". Check it out.

176023680645013966468226945392411250770384383304492191886725992896575345044216019675
Fibo2 for fibonacci #400 took 10 milliseconds.

WHAT IN THE WORLD IS THAT NUMBER?!?!?!?!!! Holy crap!! And 10 milliseconds. Let's see 500!! I wonder when BigInteger overflows... maybe never.

13942322456169788013972438287040728395007025658769 7307264108962948325571622863290691557658876222521294125
Fibo2 for fibonacci #500 took 10 milliseconds.

(I had to put a space in or else my website would be all f'ed up... but that's one number continuous)

That's incredible. "For my next job, I'll take a salary of $Fibo(150)." That's huge :) Anyway, I had fun. I want to see how far it will go before blowing the hell out of my computer, but that will be an experiment reserved for tomorrow at work :) It's not my computer then.