# Java & Calculating very big numbers

• (3 Pages)
• 1
• 2
• 3

## 35 Replies - 32600 Views - Last Post: 10 June 2011 - 12:22 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=227323&amp;s=2af7d51dd638ed101631836b1fb2996c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 CasiOo

• D.I.C Lover

Reputation: 1575
• Posts: 3,542
• Joined: 05-April 11

# Java & Calculating very big numbers

Posted 12 April 2011 - 12:40 PM

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?
Is This A Good Question/Topic? 0

## Replies To: Java & Calculating very big numbers

### #2 joeydog

Reputation: 0
• Posts: 51
• Joined: 03-October 10

## Re: Java & Calculating very big numbers

Posted 12 April 2011 - 01:59 PM

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

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12271
• Posts: 45,363
• Joined: 27-December 08

## Re: Java & Calculating very big numbers

Posted 12 April 2011 - 02:24 PM

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

```

```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 CasiOo

• D.I.C Lover

Reputation: 1575
• Posts: 3,542
• Joined: 05-April 11

## Re: Java & Calculating very big numbers

Posted 12 April 2011 - 03:16 PM

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.

### #5 joeydog

Reputation: 0
• Posts: 51
• Joined: 03-October 10

## Re: Java & Calculating very big numbers

Posted 12 April 2011 - 03:54 PM

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.

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12271
• Posts: 45,363
• Joined: 27-December 08

## Re: Java & Calculating very big numbers

Posted 12 April 2011 - 04:13 PM

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.

### #7 pbl

• There is nothing you can't do with a JTable

Reputation: 8378
• Posts: 31,956
• Joined: 06-March 08

## Re: Java & Calculating very big numbers

Posted 12 April 2011 - 05:37 PM

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

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12271
• Posts: 45,363
• Joined: 27-December 08

## Re: Java & Calculating very big numbers

Posted 12 April 2011 - 05:40 PM

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.

### #9 cfoley

• Cabbage

Reputation: 2388
• Posts: 5,013
• Joined: 11-December 07

## Re: Java & Calculating very big numbers

Posted 13 April 2011 - 03:05 AM

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

### #10 cfoley

• Cabbage

Reputation: 2388
• Posts: 5,013
• Joined: 11-December 07

## Re: Java & Calculating very big numbers

Posted 13 April 2011 - 04:15 AM

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

### #11 CasiOo

• D.I.C Lover

Reputation: 1575
• Posts: 3,542
• Joined: 05-April 11

## Re: Java & Calculating very big numbers

Posted 13 April 2011 - 04:58 AM

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++ ) {
før3 = før4.abs();
før4 = result.abs();

if ( nr % 10000 == 0 )
log( new Date() + " " + nr );

}

```

### #12 cfoley

• Cabbage

Reputation: 2388
• Posts: 5,013
• Joined: 11-December 07

## Re: Java & Calculating very big numbers

Posted 13 April 2011 - 05:08 AM

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++) {
fibLast = fibI;
fibI = next;
if (i%100000 == 0) System.out.println(i);
}
return fibI;
}
```

### #13 CasiOo

• D.I.C Lover

Reputation: 1575
• Posts: 3,542
• Joined: 05-April 11

## Re: Java & Calculating very big numbers

Posted 13 April 2011 - 05:51 AM

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++) {
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 cfoley

• Cabbage

Reputation: 2388
• Posts: 5,013
• Joined: 11-December 07

## Re: Java & Calculating very big numbers

Posted 13 April 2011 - 05:55 AM

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

### #15 CasiOo

• D.I.C Lover

Reputation: 1575
• Posts: 3,542
• Joined: 05-April 11

## Re: Java & Calculating very big numbers

Posted 13 April 2011 - 06:13 AM

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 =)