Java & Calculating very big numbers

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

35 Replies - 19411 Views - Last Post: 10 June 2011 - 12:22 AM Rate Topic: -----

#1 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1407
  • View blog
  • Posts: 3,123
  • 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  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10665
  • View blog
  • Posts: 39,608
  • 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



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. :)
Was This Post Helpful? 3
  • +
  • -

#4 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1407
  • View blog
  • Posts: 3,123
  • Joined: 05-April 11

Re: Java & Calculating very big numbers

Posted 12 April 2011 - 03:16 PM

View Postjoeydog, 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.
Was This Post Helpful? 0
  • +
  • -

#5 joeydog  Icon User is offline

  • D.I.C Head

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

Re: Java & Calculating very big numbers

Posted 12 April 2011 - 03:54 PM

View PostCasiOo, on 12 April 2011 - 03:16 PM, said:

View Postjoeydog, 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.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10665
  • View blog
  • Posts: 39,608
  • 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. :)
Was This Post Helpful? 1
  • +
  • -

#7 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Java & Calculating very big numbers

Posted 12 April 2011 - 05:37 PM

View Postjoeydog, 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
Was This Post Helpful? 1
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10665
  • View blog
  • Posts: 39,608
  • 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.
Was This Post Helpful? 1
  • +
  • -

#9 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • 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

Was This Post Helpful? 2
  • +
  • -

#10 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • 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.
Was This Post Helpful? 1
  • +
  • -

#11 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1407
  • View blog
  • Posts: 3,123
  • 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++ ) {
      result = før3.add( før4 );
      før3 = før4.abs();
      før4 = result.abs();
      
      if ( nr % 10000 == 0 )
        log( new Date() + " " + nr );
      
    }


Was This Post Helpful? 0
  • +
  • -

#12 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • 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++) {
			BigInteger next = fibI.add(fibLast);
			fibLast = fibI;
			fibI = next;
			if (i%100000 == 0) System.out.println(i);
		}
		return fibI;
	}

Was This Post Helpful? 2
  • +
  • -

#13 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1407
  • View blog
  • Posts: 3,123
  • Joined: 05-April 11

Re: Java & Calculating very big numbers

Posted 13 April 2011 - 05:51 AM

View Postcfoley, 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
Was This Post Helpful? 0
  • +
  • -

#14 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • 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.
Was This Post Helpful? 0
  • +
  • -

#15 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1407
  • View blog
  • Posts: 3,123
  • Joined: 05-April 11

Re: Java & Calculating very big numbers

Posted 13 April 2011 - 06:13 AM

View Postcfoley, 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 =)
Was This Post Helpful? 1
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3