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; }
35 Replies  23404 Views  Last Post: 10 June 2011  12:22 AM
#16
Re: Java & Calculating very big numbers
Posted 13 April 2011  07:31 AM
#17
Re: Java & Calculating very big numbers
Posted 13 April 2011  07:48 AM
#18
Re: Java & Calculating very big numbers
Posted 13 April 2011  08:07 AM
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
Memory 4 GB
Windows 7 64 bit
java version "1.6.0_24"
Java™ SE Runtime Environment (build 1.6.0_24b07)
Java HotSpot™ 64Bit Server VM (build 19.1b02, 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.
#19
Re: Java & Calculating very big numbers
Posted 05 June 2011  01:03 AM
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(n1) + fibonacci(n2); //if n > 2 then fibonnaci(n) = fibonacci(n1) + fibonacci(n2) } } 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(n1).add(memoizedFibonacci(n2))); } return memo.get(n); //return the treemap. } }
#20
Re: Java & Calculating very big numbers
Posted 05 June 2011  05:07 AM
v0rtex, on 05 June 2011  01:03 AM, said:
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(n1) + fibonacci(n2); //if n > 2 then fibonnaci(n) = fibonacci(n1) + fibonacci(n2) } } 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(n1).add(memoizedFibonacci(n2))); } 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.
#21
Re: Java & Calculating very big numbers
Posted 05 June 2011  05:53 PM
This is a false problem
#22
Re: Java & Calculating very big numbers
Posted 05 June 2011  07:21 PM
#23
Re: Java & Calculating very big numbers
Posted 06 June 2011  03:37 AM
pbl, on 05 June 2011  05:53 PM, said:
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
#24
Re: Java & Calculating very big numbers
Posted 07 June 2011  09:10 PM
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
#25
Re: Java & Calculating very big numbers
Posted 08 June 2011  12:11 PM
pbl, on 07 June 2011  09:10 PM, said:
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
#26
Re: Java & Calculating very big numbers
Posted 08 June 2011  01:23 PM
#27
Re: Java & Calculating very big numbers
Posted 08 June 2011  01:26 PM
#28
Re: Java & Calculating very big numbers
Posted 08 June 2011  01:36 PM
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
I have no idea what it means, maybe you can make sense of it and see whether its a viable solution.
#29
Re: Java & Calculating very big numbers
Posted 08 June 2011  01:38 PM
#30
Re: Java & Calculating very big numbers
Posted 08 June 2011  08:33 PM
CasiOo, on 08 June 2011  03:11 PM, said:
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
