programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Which data type to use for very big calculations?

Ranch Hand
Posts: 91
• Number of slices to send:
Optional 'thank-you' note:
Hi,

I am currently working on the problems of Project euler [webpage]
There is one problem in which we have to calculate the sum of all digits of 2^1000
The result comes out to be huge! How should i proceed with the calculation of the sum of digits of such a huge number?

For small numbers i calculate the sum of digits using the following code:

now the value of 2^1000 is so big that it cannot be stored as an int. If i store it in a double, then how would i calculate the sum?

Bartender
Posts: 4568
9
• 1
• Number of slices to send:
Optional 'thank-you' note:
You need to have a look at the BigInteger class. That stores integers of arbitrary size.

That particular Project Euler problem is trivial in languages that have a BigInteger type or similar. You've got to go to much more trouble if you don't have it - think about how you might implement your own BigInteger if you had to!

Java Cowboy
Posts: 16084
88
• Number of slices to send:
Optional 'thank-you' note:

Komal Arora wrote:If i store it in a double, then how would i calculate the sum?

That would not work, because you cannot store the number 2^1000 in a double precisely.

The double data type isn't infinitely precise. Its precision is about 16 digits (decimal). The number 2^1000 has more than 300 digits.

Komal Arora
Ranch Hand
Posts: 91
• Number of slices to send:
Optional 'thank-you' note:
Ok i would have a look at the BigInteger class.

Yes, calculating the sum with double would give wrong values because of the precision..

I was thinking of another alternative. What if i store the value of 2^1000 as a String. Then i convert it to a character array. Then i calculate the sum of all the digits by visitng each element in the char array and adding it. Would this work? or is this really bad programming?

Komal Arora
Ranch Hand
Posts: 91
• Number of slices to send:
Optional 'thank-you' note:

Matthew Brown wrote:You need to have a look at the BigInteger class. That stores integers of arbitrary size.

That particular Project Euler problem is trivial in languages that have a BigInteger type or similar. You've got to go to much more trouble if you don't have it - think about how you might implement your own BigInteger if you had to!

Can i manipulate numbers declared as BigIntegers by the simple Arithmetic operators?

Matthew Brown
Bartender
Posts: 4568
9
• Number of slices to send:
Optional 'thank-you' note:

Komal Arora wrote:Can i manipulate numbers declared as BigIntegers by the simple Arithmetic operators?

Not with operators, but there are equivalent methods.

Regarding the previous question - I think using a String or character array would be a reasonable approach, but without BigInteger you'd have to write your own algorithm to calculate 2^1000 in the first place.

Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

Komal Arora wrote:What if i store the value of 2^1000 as a String. Then i convert it to a character array. Then i calculate the sum of all the digits by visitng each element in the char array and adding it. Would this work? or is this really bad programming?

As Matthew said: sounds perfectly reasonable; and that first bit can be done in one line with BigInteger. And if you have a String, then the second part of that idea is theoretically redundant, because String has a charAt(int) method; although a for-each loop using String.toCharArray() might be more readable.

Indeed, if you're into small programs, you could write a sumPowerOfTwoDigits(int) method in four lines with proper indentation.

Winston

Komal Arora
Ranch Hand
Posts: 91
• Number of slices to send:
Optional 'thank-you' note:

Winston GutkowskiAs Matthew said: sounds perfectly reasonable; and that first bit can be done in one line with BigInteger. And if you have a String, then the second part of that idea is theoretically redundant, because String has a [tt wrote:charAt(int)[/tt] method; although a for-each loop using String.toCharArray() might be more readable.

I tried this:

I am getting an error : Cannot invoke toString on the primitive type char. Why is this coming? What am i doing wrong?

Komal Arora
Ranch Hand
Posts: 91
• Number of slices to send:
Optional 'thank-you' note:
As For BigInteger Class. I went through that and all i understood was that it converts Strings into ints of arbitrary length. But we cannot apply usual arithmetic operators on these ints. quite obvious. But then how do i manipulate that big number. I did not understand the methods of that class pretty well! I will try to explore it more.

Komal Arora
Ranch Hand
Posts: 91
• Number of slices to send:
Optional 'thank-you' note:
Ok Got the error

It should have been Character.toString(arr[i]) rather than arr[i].toString() !!!

Matthew Brown
Bartender
Posts: 4568
9
• Number of slices to send:
Optional 'thank-you' note:
There's actually a much easier way of converting a char digit to an int than having to convert to a String and back again. char is an integer type already, so you can do arithmetic on it. And all you need to do is shift it by the right amount. So:

int number = arr[i] - '0';

This only works safely if you know the character is in the range 0-9, but here you do.

Regarding doing arithmetic on BigInteger, the important thing to remember is that it's an immutable class, like String. So the methods don't change the value of the object, they return a new object with the required value.

Winston Gutkowski
Bartender
Posts: 10780
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

Komal Arora wrote:As For BigInteger Class. I went through that and all i understood was that it converts Strings into ints of arbitrary length. But we cannot apply usual arithmetic operators on these ints. quite obvious. But then how do i manipulate that big number. I did not understand the methods of that class pretty well! I will try to explore it more.

BigInteger has a pow() method for raising numbers to powers. However, an even quicker method specifically for powers of 2, is to use shiftLeft(), viz:
BigInteger twoTo1000 = BigInteger.ONE.shiftLeft(1000);

Have a good look at BigInteger - and BigDecimal - they're really useful classes to know about.

Winston