• Post Reply Bookmark Topic Watch Topic
  • New Topic

Which data type to use for very big calculations?  RSS feed

 
Komal Arora
Ranch Hand
Posts: 91
Eclipse IDE Java Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?

 
Matthew Brown
Bartender
Posts: 4568
9
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok Got the error

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

 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!