35 Replies  18464 Views  Last Post: 10 June 2011  12:22 AM
#1
Java & Calculating very big numbers
Posted 12 April 2011  12:40 PM
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?
Replies To: Java & Calculating very big numbers
#2
Re: Java & Calculating very big numbers
Posted 12 April 2011  01:59 PM
#3
Re: Java & Calculating very big numbers
Posted 12 April 2011  02:24 PM
Start by setting up the recurrence.
F(n) = F(n1) + F(n2)
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.
#4
Re: Java & Calculating very big numbers
Posted 12 April 2011  03:16 PM
#5
Re: Java & Calculating very big numbers
Posted 12 April 2011  03:54 PM
#6
Re: Java & Calculating very big numbers
Posted 12 April 2011  04:13 PM
#7
Re: Java & Calculating very big numbers
Posted 12 April 2011  05:37 PM
joeydog, on 12 April 2011  03:59 PM, said:
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
#8
Re: Java & Calculating very big numbers
Posted 12 April 2011  05:40 PM
Quote
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.
#9
Re: Java & Calculating very big numbers
Posted 13 April 2011  03:05 AM
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.
Actually, that last bit is nonsense.
This post has been edited by cfoley: 13 April 2011  03:36 AM
#10
Re: Java & Calculating very big numbers
Posted 13 April 2011  04:15 AM
#11
Re: Java & Calculating very big numbers
Posted 13 April 2011  04:58 AM
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 ); }
#12
Re: Java & Calculating very big numbers
Posted 13 April 2011  05:08 AM
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; }
#13
Re: Java & Calculating very big numbers
Posted 13 April 2011  05:51 AM
cfoley, on 13 April 2011  05:08 AM, said:
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
#14
Re: Java & Calculating very big numbers
Posted 13 April 2011  05:55 AM
#15
Re: Java & Calculating very big numbers
Posted 13 April 2011  06:13 AM
