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 - 31177 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_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.

### #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(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. } }

### #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(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.

### #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