Java & Calculating very big numbers

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

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

#31 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1372
  • View blog
  • Posts: 3,022
  • 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

Was This Post Helpful? 0
  • +
  • -

#32 cfoley  Icon User is offline

  • Cabbage
  • member icon

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

#33 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1372
  • View blog
  • Posts: 3,022
  • Joined: 05-April 11

Re: Java & Calculating very big numbers

Posted 09 June 2011 - 09:28 AM

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

#34 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1372
  • View blog
  • Posts: 3,022
  • 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

Was This Post Helpful? 0
  • +
  • -

#35 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1372
  • View blog
  • Posts: 3,022
  • 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 :P

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

Was This Post Helpful? 0
  • +
  • -

#36 cfoley  Icon User is offline

  • Cabbage
  • member icon

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

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