posted 5 years ago

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?

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?

OCPJP

Matthew Brown

Bartender

Posts: 4568

9

posted 5 years ago

- 1

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!

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!

posted 5 years ago

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

The

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.

posted 5 years ago

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?

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?

posted 5 years ago

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

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

posted 5 years ago

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.

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.

posted 5 years ago

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

Indeed, if you're into small programs, you could write a

Winston

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

posted 5 years ago

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?

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 usingString.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?

posted 5 years ago

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.

OCPJP

Matthew Brown

Bartender

Posts: 4568

9

posted 5 years ago

There's actually a much easier way of converting a

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

Regarding doing arithmetic on

`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.
posted 5 years ago

BigInteger has a

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

Winston

- 1

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Consider Paul's rocket mass heater. |