Java & Calculating very big numbers

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

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

#16 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,048
  • Joined: 11-December 07

Re: Java & Calculating very big numbers

Posted 13 April 2011 - 07:31 AM

Oops, you're right. Fixed below. Shouldn't make much difference to the running time. How's it looking so far?

	public static BigInteger fib(int n) {
		if (n <= 0) throw new IllegalArgumentException();
		BigInteger fibLast = new BigInteger("0");
		if (n == 1) return fibLast;
		BigInteger fibI = new BigInteger("1");
		for(int i = 3; 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? 0
  • +
  • -

#17 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1390
  • View blog
  • Posts: 3,075
  • Joined: 05-April 11

Re: Java & Calculating very big numbers

Posted 13 April 2011 - 07:48 AM

View PostCasiOo, on 13 April 2011 - 06:13 AM, said:

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


Quote

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


Well here is how it's going:
start:
Wed Apr 13 15:12:55 CEST 2011 100000 (i's value)

now:
Wed Apr 13 16:42:17 CEST 2011 5400000

Are you sure yours only took 1 hour 45 mins?
Was This Post Helpful? 0
  • +
  • -

#18 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,048
  • Joined: 11-December 07

Re: Java & Calculating very big numbers

Posted 13 April 2011 - 08:07 AM

Yes. Started at 10:31 and finished at 12:14.

So you got to 5400000 after an hour and a half. It sounds like you're looking at a few hours of runtime. It's certainly better than several days! After that finishes you should take out the abs() and log method from your code and retry that. Yours and mine are almost identical so they should have similar runtimes.

Other than that, different computer specs could account for the difference.

Quote

Intel Core i5 CPU M 450 @ 2.40GHz
Memory 4 GB
Windows 7 64 bit
java version "1.6.0_24"
Java™ SE Runtime Environment (build 1.6.0_24-b07)
Java HotSpot™ 64-Bit Server VM (build 19.1-b02, mixed mode)


Also, did you change the code to print out the time and dates? I doubt it would make much difference but I wouldn't be changing code for benchmarking like that.
Was This Post Helpful? 0
  • +
  • -

#19 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Re: Java & Calculating very big numbers

Posted 05 June 2011 - 01:03 AM

macosxnerd101's solution seems very logical and I suggest you attempt to implement that. However, if you end up using a recursive solution, I suggest using memorization. As I am sure you know a Fibonacci sequence ends up calculating the same Fibonacci values repeatedly in many instances, a solution to this is to store the answers in an array or Map etc... Thus when you have to calculate a Fibonacci value of n again, you check if that value was stored in the array and if it was, you simply call that value. I have a tutorial about this both on Dream.In.Code and on my blog (link in signature).

Here is something I found in the abyss of my HD where I implemented the fibonacci sequence with memorization, I believe that this is also the same solution in my tutorial (note you will have to edit the code for it to suit your purposes exactly, rather if you do use my solution, read my tutorial and understand what I have done):


import java.math.BigInteger;
import java.util.Map;
import java.util.TreeMap;
import java.io.*;
public class  Fibonnaci_memorization{
    // Note: a treemap is used to store the fibonacci numbers that have already been calculated, also a biginteger is used to avoid loss of precision.
    static Map<Integer, BigInteger> memo = new TreeMap<Integer, BigInteger>();
    public static void main (String[] args) throws IOException{
        BufferedReader inKb = new BufferedReader (new InputStreamReader (System.in));
	System.out.println("Enter a number to calculate fibonacci value of that value:");
        int num = 0;
        int fibnum;
	num = Integer.parseInt(inKb.readLine());
	fibnum = fibonacci(num);
	System.out.println("the fibonacci value of " + num + "th is "+ fibnum);
        System.out.println ("The memoized calculation of that value is: " + memoizedFibonacci(num));
    }
    static int fibonacci(int n) {
	if (n <= 1) {
	    return 1;
            //the base case:If k <= 2 then fib(k) = 1.
	}	
	else {
	    return fibonacci(n-1) + fibonacci(n-2);
             //if n > 2 then fibonnaci(n) = fibonacci(n-1) + fibonacci(n-2)
	}
    }
    static BigInteger memoizedFibonacci(int n)
	{
		if (n <= 1) return BigInteger.ONE;
		if (memo.get(n) == null)
                {
			//If the element is not in the treemap, we then calculate it and add it.
			memo.put(n, memoizedFibonacci(n-1).add(memoizedFibonacci(n-2)));
            }
		return memo.get(n); //return the treemap.
	}
}


Was This Post Helpful? 0
  • +
  • -

#20 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1390
  • View blog
  • Posts: 3,075
  • Joined: 05-April 11

Re: Java & Calculating very big numbers

Posted 05 June 2011 - 05:07 AM

View Postv0rtex, on 05 June 2011 - 01:03 AM, said:

macosxnerd101's solution seems very logical and I suggest you attempt to implement that. However, if you end up using a recursive solution, I suggest using memorization. As I am sure you know a Fibonacci sequence ends up calculating the same Fibonacci values repeatedly in many instances, a solution to this is to store the answers in an array or Map etc... Thus when you have to calculate a Fibonacci value of n again, you check if that value was stored in the array and if it was, you simply call that value. I have a tutorial about this both on Dream.In.Code and on my blog (link in signature).

Here is something I found in the abyss of my HD where I implemented the fibonacci sequence with memorization, I believe that this is also the same solution in my tutorial (note you will have to edit the code for it to suit your purposes exactly, rather if you do use my solution, read my tutorial and understand what I have done):


import java.math.BigInteger;
import java.util.Map;
import java.util.TreeMap;
import java.io.*;
public class  Fibonnaci_memorization{
    // Note: a treemap is used to store the fibonacci numbers that have already been calculated, also a biginteger is used to avoid loss of precision.
    static Map<Integer, BigInteger> memo = new TreeMap<Integer, BigInteger>();
    public static void main (String[] args) throws IOException{
        BufferedReader inKb = new BufferedReader (new InputStreamReader (System.in));
	System.out.println("Enter a number to calculate fibonacci value of that value:");
        int num = 0;
        int fibnum;
	num = Integer.parseInt(inKb.readLine());
	fibnum = fibonacci(num);
	System.out.println("the fibonacci value of " + num + "th is "+ fibnum);
        System.out.println ("The memoized calculation of that value is: " + memoizedFibonacci(num));
    }
    static int fibonacci(int n) {
	if (n <= 1) {
	    return 1;
            //the base case:If k <= 2 then fib(k) = 1.
	}	
	else {
	    return fibonacci(n-1) + fibonacci(n-2);
             //if n > 2 then fibonnaci(n) = fibonacci(n-1) + fibonacci(n-2)
	}
    }
    static BigInteger memoizedFibonacci(int n)
	{
		if (n <= 1) return BigInteger.ONE;
		if (memo.get(n) == null)
                {
			//If the element is not in the treemap, we then calculate it and add it.
			memo.put(n, memoizedFibonacci(n-1).add(memoizedFibonacci(n-2)));
            }
		return memo.get(n); //return the treemap.
	}
}



Could you write how long time it takes for your computer to calculate 12345678 together with computer specs please :) ?

Also I found it it's just my laptop which is super slow, but still java is slow to calculate the result (from what I have seen so far). My teacher made the same solution in another language where it took him 11 minutes to get the result.
Was This Post Helpful? 0
  • +
  • -

#21 pbl  Icon User is offline

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

Reputation: 8327
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Java & Calculating very big numbers

Posted 05 June 2011 - 05:53 PM

12345678 will fit with long no need to us BigInteger
This is a false problem
Was This Post Helpful? 0
  • +
  • -

#22 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,048
  • Joined: 11-December 07

Re: Java & Calculating very big numbers

Posted 05 June 2011 - 07:21 PM

But fib(12345678) has over 2.5 million digits. :o
Was This Post Helpful? 2
  • +
  • -

#23 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1390
  • View blog
  • Posts: 3,075
  • Joined: 05-April 11

Re: Java & Calculating very big numbers

Posted 06 June 2011 - 03:37 AM

View Postpbl, on 05 June 2011 - 05:53 PM, said:

12345678 will fit with long no need to us BigInteger
This is a false problem


I meant fib(12345678)

Edit: I ran my own solution on my other computer and this is my result:

specs:
Windows 7 64 bit
i7 920 2.66 GHz
6GB RAM

Start time: 12:40
End time: 13:35

This post has been edited by CasiOo: 06 June 2011 - 04:47 AM

Was This Post Helpful? 0
  • +
  • -

#24 pbl  Icon User is offline

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

Reputation: 8327
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Java & Calculating very big numbers

Posted 07 June 2011 - 09:10 PM

As your only operation on the BigInteger is add (+)
Write your own BigInteger class
Hold each digit in a byte array
Rewrite the add() method to use your own byte implementation
Make your own BigInteger objects mutable
You should gain at least 50% of CPU time
Was This Post Helpful? 0
  • +
  • -

#25 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1390
  • View blog
  • Posts: 3,075
  • Joined: 05-April 11

Re: Java & Calculating very big numbers

Posted 08 June 2011 - 12:11 PM

View Postpbl, on 07 June 2011 - 09:10 PM, said:

As your only operation on the BigInteger is add (+)
Write your own BigInteger class
Hold each digit in a byte array
Rewrite the add() method to use your own byte implementation
Make your own BigInteger objects mutable
You should gain at least 50% of CPU time


So I tried and do this, but I kinda failed ^^ the BigInterger class I made runs even slower :(

I made it with a int array with a max value of Interger.MAX_VALUE each place

This post has been edited by CasiOo: 08 June 2011 - 12:47 PM

Was This Post Helpful? 0
  • +
  • -

#26 nick2price  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 562
  • View blog
  • Posts: 2,826
  • Joined: 23-November 07

Re: Java & Calculating very big numbers

Posted 08 June 2011 - 01:23 PM

I know very little maths, let alone fibonacci sequences. But at the end of the day, this is down to processing. So, question to the other experts. Would it be possible to multi thread the calculation to make use of multi-core cpu's?
Was This Post Helpful? 0
  • +
  • -

#27 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10447
  • View blog
  • Posts: 38,690
  • Joined: 27-December 08

Re: Java & Calculating very big numbers

Posted 08 June 2011 - 01:26 PM

Not effectively. It's possible since the Fibonacci sequence can be calculated using what I like to call "tree recursion." There will be a lot of redundant calculations, though. If you solve the linear recurrence as I demonstrated earlier, you could more easily use Threads to generate the ath through the nth Fibonacci numbers.
Was This Post Helpful? 1
  • +
  • -

#28 nick2price  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 562
  • View blog
  • Posts: 2,826
  • Joined: 23-November 07

Re: Java & Calculating very big numbers

Posted 08 June 2011 - 01:36 PM

Kool. This has started intrigueing me as I tried a number 100000 with some code i have, and it took about 30 seconds to calculate. I then tried Casi0's 8 digit number, and my computer nearly blew up :bananaman:
Somewhere I saw them talking about the multi threading, and they were saying it may not be possible due to the calculations relying on each other. Someone did reply this though

Quote

Re "multi-threaded algorithm" ... have you tried computing vector (F[k+1], F[k]) from (F[k-1], F[k-2])? It implies using a matrix multiplication, which can be parallelised. You can do same trick with vectors of dimensions >=2 as well.

I have no idea what it means, maybe you can make sense of it and see whether its a viable solution.
Was This Post Helpful? 0
  • +
  • -

#29 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10447
  • View blog
  • Posts: 38,690
  • Joined: 27-December 08

Re: Java & Calculating very big numbers

Posted 08 June 2011 - 01:38 PM

The most I've done with matrices was in Algebra II freshman year. I haven't touched them in years, save for adjacency matrices in our graph theory unit in Discrete. Personally, I still prefer just solving the recurrence. You can't beat the O(1) time solution it produces. :)
Was This Post Helpful? 0
  • +
  • -

#30 pbl  Icon User is offline

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

Reputation: 8327
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Java & Calculating very big numbers

Posted 08 June 2011 - 08:33 PM

View PostCasiOo, on 08 June 2011 - 03:11 PM, said:

So I tried and do this, but I kinda failed ^^ the BigInterger class I made runs even slower :(

I made it with a int array with a max value of Interger.MAX_VALUE each place

Not really the good approach, and an int[Interer.MAX_VALUE] is a hugue array for nothing
better to dynamically allocate the room you need
Was This Post Helpful? 1
  • +
  • -

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