How can 8 bytes hold 302 decimal digits? (Euler challenge 16)

Question

c++ pow(2,1000) is normaly to big for double, but it's working. why?

So I've been learning C++ for couple weeks but the datatypes are still confusing me.

One small minor thing first: the code that 0xbadc0de posted in the other thread is not working for me. First of all pow(2,1000) gives me this more than once instance of overloaded function "pow" matches the argument list.

I fixed it by changing pow(2,1000) -> pow(2.0,1000) Seems fine, i run it and get this:

http://i.stack.imgur.com/bbRat.png

Instead of

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

it is missing a lot of the values, what might be cause that?

But now for the real problem. I'm wondering how can 302 digits long number fit a double (8 bytes)? 0xFFFFFFFFFFFFFFFF = 18446744073709551616 so how can the number be larger than that?

I think it has something to do with the floating point number encoding stuff. Also what is the largest number that can possibly be stored in 8 bytes if it's not 0xFFFFFFFFFFFFFFFF?

Answer 1

Eight bytes contain 64 bits of information, so you can store 2^64 ~ 10^20 unique items using those bits. Those items can easily be interpreted as the integers from 0 to 2^64 - 1. So you cannot store 302 decimal digits in 8 bytes; most numbers between 0 and 10^303 - 1 cannot be so represented.

Floating point numbers can hold approximations to numbers with 302 decimal digits; this is because they store the mantissa and exponent separately. Numbers in this representation store a certain number of significant digits (15-16 for doubles, if I recall correctly) and an exponent (which can go into the hundreds, of memory serves). However, if a decimal is X bytes long, then it can only distinguish between 2^(8X) different values... unlikely enough for exactly representing integers with 302 decimal digits.

To represent such numbers, you must use many more bits: about 1000, actually, or 125 bytes.