[CasiOo]

I have been working with fibonacci numbers, and I want to find F(12345678) which, of course, result in a very big number.

I have tried to find it with the help of BigInterger, but it is extremely slow, and with the current speed, it will take days to find the number.

So my question is: What is the fastest way to find F(12345678) using java?

[joeydog]

Are you using recursion? If not, try it. It seems the best way to me.

[macosxnerd101]

Are you familiar with solving linear recurrences? Or how about homogenous linear differential equations? You solve them the same way, basically.

Start by setting up the recurrence.

F(n) = F(n-1) + F(n-2)

Now set up the characteristic equation:

x^2 - x - 1 = 0

Now just solve the quadratic:

x = [1 +- sqrt(1 - 4(-1)(1))]/2
x = [1 +- sqrt(5)]/2

From there, we set up our solution:

F(n) = Ar(1)^n + Br(2)^n

Where r(1) is root 1, and r(2) is root 2. You know F(0) is 0, and F(1) is 1. Now just set up a system of equations and solve given those values. Whatever you get for A and B, you plug into the equation, and now you can solve for your large Fibonacci number with a formula that we solved by hand.

Happy coding.

[CasiOo]

joeydog, on 12 April 2011 - 01:59 PM, said:

Are you using recursion? If not, try it. It seems the best way to me.

No I'm not doing it using recursion, but I can't see why it would be any faster.

[joeydog]

CasiOo, on 12 April 2011 - 03:16 PM, said:

joeydog, on 12 April 2011 - 01:59 PM, said:

Are you using recursion? If not, try it. It seems the best way to me.

No I'm not doing it using recursion, but I can't see why it would be any faster.

Might not be, but was taught to me that way.

[macosxnerd101]

Solve it by hand first to find the equation, as I showed you above. Then just use that formula programatically. It will make your life much easier.

[pbl]

joeydog, on 12 April 2011 - 03:59 PM, said:

Are you using recursion? If not, try it. It seems the best way to me.

Not really, never seen a case where recursion is faster than iteration (well documented in the litterature). Recursion adds the method call overhead and with that large number you will exhausted the stack quite fast.

@op: sure that it will be slower with BigInteger but you have to realize that you work with very large number

[macosxnerd101]

Quote

@op: sure that it will be slower with BigInteger but you have to realize that you work with very large number

Not only that, but BigIntegers are immutable as well, meaning a new BigInteger is created each time you want to perform a mathematical operation on it, etc.

[cfoley]

Recursion for fibonacci is slow. Say you are calculating fib 6, the tree looks like this:

                      6
             5                 4
         4       3         3       2
       3   2   2   1     2   1
      2 1

You have to calculate fib(4) twice, fib(3) three times. Fib(2) is a base case but it's accessed 5 times. This only gets worse for larger numbers.

You want to do it iteratively, and that sounds like what you've done. I did a quick implementation and it's got to 7200000 in half an hour. It's beginning to slow down now that it's working with bigger numbers but I doubt it'll take more than a couple of hours.

Maybe post your code and we can look for the bottlenecks?

Another option is to look at the wikipedia page which gives you a formula to calculate Fibonacci numbers quickly.

Macos actually for fibonacci, using an immutable structure isn't that big a performance penalty since you need the previous two numbers to calculate the next one.
Actually, that last bit is nonsense.

This post has been edited by cfoley: 13 April 2011 - 03:36 AM

[cfoley]

My BigInteger implementation just finished and took 1 hour, 45 mins.

[CasiOo]

Uhm ok.. please show me how. This is what I've done:

    int x=12345678;

    BigInteger result = new BigInteger( "1" );
    BigInteger før3 = new BigInteger( "1" );
    BigInteger før4 = new BigInteger( "1" );
    
    for ( int nr=3; nr<=x; nr++ ) {
      result = før3.add( før4 );
      før3 = før4.abs();
      før4 = result.abs();
      
      if ( nr % 10000 == 0 )
        log( new Date() + " " + nr );
      
    }

[cfoley]

I did it pretty much like that!. Those calls to abs() might be killing you. Also, depending on what your log() method does, that could be expensive.

Here is my method for comparison. I used the convention fob(0) = 0; fib(1) = 1 but that should make little difference to the time:

	public static BigInteger fib(int n) {
		BigInteger fibLast = new BigInteger("0");
		if (n == 0) return fibLast;
		BigInteger fibI = new BigInteger("1");
		for(int i = 1; i <= n; i++) {
			BigInteger next = fibI.add(fibLast);
			fibLast = fibI;
			fibI = next;
			if (i%100000 == 0) System.out.println(i);
		}
		return fibI;
	}

[CasiOo]

cfoley, on 13 April 2011 - 05:08 AM, said:

I did it pretty much like that!. Those calls to abs() might be killing you. Also, depending on what your log() method does, that could be expensive.

Here is my method for comparison. I used the convention fob(0) = 0; fib(1) = 1 but that should make little difference to the time:

	public static BigInteger fib(int n) {
		BigInteger fibLast = new BigInteger("0");
		if (n == 0) return fibLast;
		BigInteger fibI = new BigInteger("1");
		for(int i = 1; i <= n; i++) {
			BigInteger next = fibI.add(fibLast);
			fibLast = fibI;
			fibI = next;
			if (i%100000 == 0) System.out.println(i);
		}
		return fibI;
	}

I do not believe the abs() make any big difference, and the log 100% doesn't.

Also I have tried and run it on a different computer with the same result. It takes days for it to find the number :S

[cfoley]

So the next thing to try it to run my code and see how long it is taking.

[CasiOo]

cfoley, on 13 April 2011 - 05:55 AM, said:

So the next thing to try it to run my code and see how long it is taking.

Aren't your code giving out 1 number too high? or am I wrong?

I am running it now =)