4

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:

https://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?

Community
  • 1
  • 1
Ollie
  • 127
  • 1
  • 3
  • 8
  • 1
    `so how can the number be larger than that?` Have 302 decimal digits of zero. Problem solved. – Lightness Races in Orbit Jan 28 '13 at 16:59
  • 1
    A byte is usually 8 bits. Thus one byte is 0xFF. Thus 8 bytes is `0xFFFFFFFFFFFFFFFF` or max of: 18446744073709600000 (though it looks like my calculator rounded that). How you get a 302 digit number in 64 bits is another question (compression)? Some trick. – Martin York Jan 28 '13 at 17:06
  • 1
    Its the difference between floating types and integer types. A floating numeric will store a limited representation of an exponential mantissa along with an exponent. The exponent can tell a print function essentially how many zeros to add after the decimal representation of a mantissa. Essentially it will give you for the pow inputs you are giving, a rounded version of the output which is why you see 17 meaningful digits then a whole buncha 0s. – trumpetlicks Jan 28 '13 at 17:08
  • Here's the wikipedia entry for Floating Point numbers: http://en.wikipedia.org/wiki/Floating_point In particular interest to you should be the section covering IEEE 754, which is the standard that C++ (and most other programming languages) adhere to where floating point numbers are concerned. –  Jan 28 '13 at 17:12
  • Hmm.. I think i got the floating point part, but the long number still has 301 digits of precision, not just 0's, so how do you fit 301 digits in the 52bit mantissa? – Ollie Jan 28 '13 at 17:31
  • How did you calculate the long number (the one that shows the actual number / precision)? – trumpetlicks Jan 28 '13 at 17:32
  • I was pointing to this thread: http://stackoverflow.com/questions/7371928/c-pow2-1000-is-normaly-to-big-for-double-but-its-working-why I didn't get mine to work as he did. Mine cut out and filled the rest with 0s – Ollie Jan 28 '13 at 17:36
  • If your read the answer from the question, you will see that while the printout shows precision, one should be carful in interpretation of the output. The answer strictly states "There's nothing wrong with asking a computer to print more than 16 decimal digits. What's wrong is assuming that those extra digits have any meaning." What he is saying, is exactly what we all here are, is that only the first (leftmost / most significant) 16 significant decimal digits actually mean something in this case. – trumpetlicks Jan 28 '13 at 17:44

5 Answers5

8

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.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
1

It's called 'floating point' for a reason. The datatype contains a number in the standard sense, and an exponent which says where the decimal point belongs. That's why pow(2.0, 1000) works, and it's why you see a lot of zeroes. A floating point (or double, which is just a bigger floating point) number contains a fixed number of digits of precision. All the remaining digits end up being zero. Try pow(2.0, -1000) and you'll see the same situation in reverse.

The number of decimal digits of precision in a float (32 bits) is about 7, and for a double (64 bits) it's about 16 decimal digits.

Most systems nowadays use IEEE floating point, and I just linked to a really good description of it. Also, the article on the specific standard IEEE 754-1985 gives a detailed description of the bit layouts of various sizes of floating point number.

Omnifarious
  • 54,333
  • 19
  • 131
  • 194
  • exactly what i wanted to write. about computing the answer: you can use decimal arithmetic of some standard implementation for computing with big numbers, like BigInteger in java – edofic Jan 28 '13 at 17:07
1

Floating point types can cover a much larger range than integer types of the same size, but with less precision.

They represent a number as:

  • a sign bit s to indicate positive or negative;
  • a mantissa m, a value between 1 and 2, giving a certain number of bits of precision;
  • an exponent e to indicate the scale of the number.

The value itself is calculated as m * pow(2,e), negated if the sign bit is set.

A standard double has a 53-bit mantissa, which gives about 16 decimal digits of precision.

So, if you need to represent an integer with more than (say) 64 bits of precision, then neither a 64-bit integer nor a 64-bit floating-point type will work. You will need either a large integer type, with as many bits as necessary to represent the values you're using, or (depending on the problem you're solving) some other representation such as a prime factorisation. No such type is available in standard C++, so you'll need to make your own.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
1

2.0 ^ 1000 mathematically will have a decimal (non-floating) output. IEEE floating point numbers, and in your case doubles (as the pow function takes in doubles and outputs a double) have 52 bits of the 64 bit representation allocated to the mantissa. If you do the math, 2^52 = 4,503,599,627,370,496. Because a floating point number can represent positive and negative numbers, really the integer representation will be ~ 2^51 = 2,251,799,813,685,248. Notice there are 16 digits. there are 16 quality (non-zero) digits in the output you see.

Essentially the pow function is going to perform the exponentiation, but once the exponentiation moves past ~2^51, it is going to begin losing precision. Ultimately it will hold precision for the top ~16 decimal digits, but all other digits right will be un-guaranteed.

Thus it is a floating point precision / rounding problem.

If you were strictly in unsigned integer land, the number would overflow after (2^64 - 1) = 18,446,744,073,709,551,616. What overflowing means, is that you would never actually see the number go ANY HIGHER than the one provided, infact I beleive the answer would be 0 from this operation. Once the answer goes beyond 2^64, the result register would be zero, and any multiply afterwords would be 0 * 2, which would always result in 0. I would have to try it.

The exact answer (as you show) can be obtained using a standard computer using a multi-precision libary. What these do is to emulate a larger bit computer by concatenating multiple of the smaller data types, and use algorithms to convert and print on the fly. Mathematica is one example of a math engine that implements an arbitrary precision math calculation library.

trumpetlicks
  • 7,033
  • 2
  • 19
  • 33
1

If you want to calculate the range of the digits that can be hold by some bytes, it should be (2^(64bits - 1bit)) to (2^(64bits - 1bit) - 1).

Because the left most digit of the variable is for representing sign (+ and -). So the range for negative side of the number should be : (2^(64bits - 1bit)) and the range for positive side of the number should be : (2^(64bits - 1bit) - 1) there is -1 for the positive range because of 0(to avoid reputation of counting 0 for each side).

For example if we are calculating 64bits, the range should be ==> approximately [-9.223372e+18] to [9.223372e+18]

Eric Duhun Kim
  • 11
  • 3