150

7
+1  Q:

Double precision in C++ (or pow(2, 1000))

I'm working on Project Euler to brush up on my C++ coding skills in preparation for the programming challenge(s) we'll be having this next semester (since they don't let us use Python, boo!).

I'm on #16, and I'm trying to find a way to keep real precision for 2¹°°°

For instance:

``````int main(){
double num = pow(2, 1000);
printf("%.0f", num):
return 0;
}
``````

prints

10715086071862673209484250490600018105614050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Which is missing most of the numbers (from python):

`>>> 2**1000`

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376L

Granted, I can write the program with a Python 1 liner

``````sum(int(_) for _ in str(2**1000))
``````

that gives me the result immediately, but I'm trying to find a way to do it in C++. Any pointers? (haha...)

Edit:

Something outside the standard libs is worthless to me - only dead-tree code is allowed in those contests, and I'm probably not going to print out 10,000 lines of external code...

+3  A:

You need a bignum library, such as this one.

Isn't the idea of those programming chalanges to come up with the corresponding algorithms onselves?
3rd party stuff doesn't address my needs - I edited my question to make that clearer - but programming competitions tend to call 3rd party libraries cheating (unless I brought the dead-tree version and transcribed the code myself...)
+3  A:

You probably need a pointer here (pun intended)

In C++ you would need to create your own bigint lib in order to do the same as in python.

You don't need a whole library, you just need a single function to do bigint addition or doubling and another to output the result. If you structure it as I describe in my own answer it becomes trivial.
+1  A:

If you want to do this sort of thing on a practical basis, you're looking for an arbitrary precision arithmetic package. There are a number around, including NTL, lip, GMP, and MIRACL.

If you're just after something for Project Euler, you can write your own code for raising to a power. The basic idea is to store your large number in quite a few small pieces, and implement your own carries, borrows, etc., between the pieces.

+2  A:

C/C++ operates on fundamental data types. You are using a `double` which has only 64 bits to store a 1000 bit number. `double` uses 51 bit for the significant digits and 11 bit for the magnitude.

The only solution for you is to either use a library like bignum mentioned elsewhere or to roll out your own.

A:

Isn't `pow(2, 1000)` just 2 left-shifted 1000 times, essentially? It should have an exact binary representation in a double float. It shouldn't require a bignum library.

Yes, but power of 2 are usually exactly representable in floating point numbers. The printed representation will depend on the implementation of the standard library. As a matter of fact, on linux the OP program gives the same result as the Python one.
+2  A:
Shouldn't the first value of 2**N be 1 as N**0 == 1?
Corrected, thanks
for 13 I just used string stream to read a single number at a time and just summed it all up that way. The only problem on this one is they didn't give me the string representation of this number...
+2  A:

If you just keep track of each digit in a char array, this is easy. Doubling a digit is trivial, and if the result is greater than 10 you just subtract 10 and add a carry to the next digit. Start with a value of 1, loop over the doubling function 1000 times, and you're done. You can predict the number of digits you'll need with `ceil(1000*log(2)/log(10))`, or just add them dynamically.

Spoiler alert: it appears I have to show the code before anyone will believe me. This is a simple implementation of a bignum with two functions, Double and Display. I didn't make it a class in the interest of simplicity. The digits are stored in a little-endian format, with the least significant digit first.

``````typedef std::vector<char> bignum;

void Double(bignum & num)
{
int carry = 0;
for (bignum::iterator p = num.begin();  p != num.end();  ++p)
{
*p *= 2;
*p += carry;
carry = (*p >= 10);
*p -= carry * 10;
}
if (carry != 0)
num.push_back(carry);
}

void Display(bignum & num)
{
for (bignum::reverse_iterator p = num.rbegin();  p != num.rend();  ++p)
std::cout << static_cast<int>(*p);
}

int main(int argc, char* argv[])
{
bignum num;
num.push_back(1);
for (int i = 0;  i < 1000;  ++i)
Double(num);
Display(num);
std::cout << std::endl;
return 0;
}
``````