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;



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

>>> 2**1000


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...)


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...)
Wayne Werner
+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.

Anders K.
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.
Mark Ransom
+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.

Jerry Coffin
+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.


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.

Zan Lynx
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: 
Luther Blissett
Shouldn't the first value of 2**N be 1 as N**0 == 1?
Wayne Werner
Corrected, thanks
Luther Blissett
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...
Wayne Werner
+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)

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;
    for (int i = 0;  i < 1000;  ++i)
    std::cout << std::endl;
    return 0;
Mark Ransom