# Java & Calculating very big numbers

• (3 Pages)
• 1
• 2
• 3

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

### #31 CasiOo

• D.I.C Lover

Reputation: 1576
• Posts: 3,548
• Joined: 05-April 11

## Re: Java & Calculating very big numbers

Posted 09 June 2011 - 08:15 AM

So I changed my code a bit and these were my results:
fib(400000)
Java's BigInteger: 4s
My implementation: 11s

If anyone wants to see my implementation, and maybe have some improvements then be free to answer Also ask if you have any questions. Basically it is one big int array where the indexes combined is one big number. Also the number is reversed in the array

```public class MyBigIntegerThree {
private final int base = Integer.MAX_VALUE; //Contains the max value each index
private int[] bigNumber;

public MyBigIntegerThree( int number ) {
bigNumber = new int[1];
bigNumber[0] = number;
}

public int[] add( int[] other ) {
int bigNumberLength = bigNumber.length;
int otherLength = other.length;
int[] result = new int[bigNumberLength >= otherLength ? bigNumberLength : otherLength]; //Setting length to the biggest
long carry = 0;

for ( int i = 0; i < result.length; i++ ) {
if ( i >= bigNumberLength ) {
long sum = (long) other[i] + carry;
carry = sum / base;
result[i] = ((int) (sum % base));
}
else if ( i >= otherLength ) {
long sum = (long) bigNumber[i] + carry;
carry = sum / base;
result[i] = ((int) (sum % base));
}
else {
long sum = (long) bigNumber[i] + (long) other[i] + carry;
carry = sum / base;
result[i] = ((int) (sum % base));
}
}
while ( carry != 0 ) { //expands array by 1
int[] temp = new int[result.length + 1];
System.arraycopy( result, 0, temp, 0, result.length );
temp[temp.length - 1] = (int) (carry % base);
result = temp;
carry = (int) (temp[temp.length - 1] / base);
}
return bigNumber = result;
}

public int[] getArray() {
return bigNumber;
}

public void setArray( int[] array ) {
this.bigNumber = array;
}

public String toString() {
StringBuffer string = new StringBuffer();
for ( int i = bigNumber.length - 1; i >= 0; i-- ) {
string.append( bigNumber[i] * Math.pow( base, i ) + " + " );
}
return string.toString();
}
}

```

EDIT: Corrected the code

This post has been edited by CasiOo: 09 June 2011 - 03:48 PM

### #32 cfoley

• Cabbage

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

## Re: Java & Calculating very big numbers

Posted 09 June 2011 - 08:32 AM

You're allocating a new array each time you add. You should just add the numbers from the other[] into your array, making sure you carry over at each place and expand the array as necessary. Expanding it by doubling the size all the time is better that expanding by 1 each time you go over the limit.

By the way, using Integer.MAX won't work if you need to carry numbers. The variables will just overflow to negative numbers and screw up your results. Get your program working with base 10 and increase the base after.

### #33 CasiOo

• D.I.C Lover

Reputation: 1576
• Posts: 3,548
• Joined: 05-April 11

## Re: Java & Calculating very big numbers

Posted 09 June 2011 - 09:28 AM

cfoley, on 09 June 2011 - 08:32 AM, said:

You're allocating a new array each time you add. You should just add the numbers from the other[] into your array, making sure you carry over at each place and expand the array as necessary. Expanding it by doubling the size all the time is better that expanding by 1 each time you go over the limit.

By the way, using Integer.MAX won't work if you need to carry numbers. The variables will just overflow to negative numbers and screw up your results. Get your program working with base 10 and increase the base after.

The carrying does work from what I have tested (it does not overflow because i put the sum into a long).

I will try and double the size instead of expanding by 1

### #34 CasiOo

• D.I.C Lover

Reputation: 1576
• Posts: 3,548
• Joined: 05-April 11

## Re: Java & Calculating very big numbers

Posted 09 June 2011 - 11:18 AM

EDIT: fixed in post just below.

This post has been edited by CasiOo: 09 June 2011 - 03:47 PM

### #35 CasiOo

• D.I.C Lover

Reputation: 1576
• Posts: 3,548
• Joined: 05-April 11

## Re: Java & Calculating very big numbers

Posted 09 June 2011 - 03:46 PM

I was not printing the correct result out.

The toString method should look like :
```public String toString() {
StringBuffer string = new StringBuffer();
for ( int i = bigNumber.length - 1; i >= 0; i-- ) {
string.append( bigNumber[i] * Math.pow( base, i ) + " + " );
}
return string.toString();
}

```

But still it takes 11s for 400000

This post has been edited by CasiOo: 09 June 2011 - 03:47 PM

### #36 cfoley

• Cabbage

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

## Re: Java & Calculating very big numbers

Posted 10 June 2011 - 12:22 AM

Sorry, I missed that you were using longs.

Did you take my advice about reusing the original array as much as you can? I'm surprised that has not sped it up considerably.