1
$\begingroup$

I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater than or equal to 1), to convert a decimal to binary, the results turn strange likely due to floating point imprecision.

For example, the following is a result you might find when applying the algorithm:

enter image description here

The number 0.531904 multiplied by 2 and then subtracted by 1 should result in 0.063708 instead of what is highlighted. Successive instances of this cause the error to eventually propagate to a much greater margin after more iterations.

Thus, I have made 3 observations:

  1. For a decimal between 0 and 1 with "N" places after the point, multiplying it by 2 should never make it more than "N" places. (e.g. multiplying 0.022, where N=3, by any power of 2 should never give it a fourth place etc.)

  2. For a decimal number between 0 and 1 with "N" decimal places beyond the dot. (e.g. 0.022 has N=3 and 0.0101 has N=4) if the binary representation is repeating, then the repeating portion should be no longer than 10^N digits.

  3. For a decimal number between 0 and 1 with the last (rightmost) digit being {1,2,3,4, ,6,7,8,9} it will always have a repeating representation in binary. It will only not have a repeating representation if the last digit is 5.

My Questions are as follows:

  1. Are these observations true?

  2. If so, is rounding the number to "N" decimal places at every iteration step an appropriate way to fix the problem of precision?

  3. Can someone confirm the result I obtained that 0.002992 has a repeating portion that is 12500 digits long?

$\endgroup$
4
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Round-off_error $\endgroup$ – D.W. Sep 20 '20 at 17:49
  • $\begingroup$ (Observation 1: How do you tally the overflow due for $.5 \le N$?) $\endgroup$ – greybeard Sep 21 '20 at 7:06
  • $\begingroup$ Welcome. Just to make sure, are the decimal number inputs to your program really decimal (given as a sequence of digits instead of as a float)? $\endgroup$ – 6005 Sep 23 '20 at 12:21
  • $\begingroup$ By the way, this might be a bit too many questions for one post, sometimes it's better to focus on just one thing you are most curious about. $\endgroup$ – 6005 Sep 23 '20 at 12:21
1
$\begingroup$

You are not doing arithmetic on arbitrary infinitely precise numbers. You are doing arithmetic on the subset of number representable in your computer's native floating point format. Moreover, the values you see printed out are not infinitely precise representations of the actual values encoded in the computer. They are decimal numbers (of a maximum precision) which approximate the internal value. This makes it a little difficult to see what's really going on. At the very least, it is confusing.

Although some programming languages (and even some computers) natively support decimal arithmetic, most of the time the internal representations you will be working with are fixed-precision binary representation. By fixed precision, I mean that the number represented is a fraction $n/2^i$ where $i$ is an integer in a limited range and $n < 2^p$ for some fixed $p$, the precision. Typical CPUs have settled on a precision of 53 bits, so $n < 2^{53}$.

When you supply $.002992$ -- that is, $2992/10^6$ -- the programming language needs to find an internally representable number that is as close as possible to that value in order to minimise calculation errors. At least on my machine, the value selected is $1724770570891843/2^{59}$. That number is extremely close to $2992/10^6$ -- so close that if you round it off at the 18th decimal point you will still see $0.002992$ -- but it's not equal. So your calculation starts with a small inaccuracy.

However, if you just run your algorithm (multiply by 2; subtract 1 if the result is not less than 1), you will not increase the inaccuracy. Multiplying by 2 is exact (unless you exceed the exponent limits), since it only requires changing the exponent to the next integer. And 1 can be represented exactly. In fact, every integer up to $2^{53}$ can be represented exactly, as well as quite a few other integers (but not $2^{53}+1$). So your algorithm will reveal the binary representation of the number actually being used by your computer instead of $0.002992$. That number has no more than 53 binary digits of precision, but it is slightly longer than 53 binary digits because of the 9 leading 0s (in binary). There is no repeating part at all.

Trying to "correct" this computation by introducing additional round-off errors at each step is not going to help.

If you want to find the exact binary representation of $0.002992$, you can use integer arithmetic to work with successive rational numbers. Start with $2992/1000000$ and repeatedly double the numerator and, if necessary, subtract the denominator [Note 1]. (You don't need any extended precision for that. If you start with $0 \le n \lt d$, then $n$ will never exceed $2d$. In the case of $2992/1000000$, that's well within the range of a normal 32-bit integer.)

That will indeed show that the repeating fraction has a period of 12500. It's straightforward to show that the period of the repeating fraction of $n/d$ is less than $d$ in any base. The above algorithm only depends on the value of $n$ and never changes the value of $d$, so the second time you hit a particular value for $n$, your output will start repeating. The period must be less than $d$ because if $n$ is 0, you have an exact fraction, and there are only $d-1$ other possible values of $n$, so it must repeat before $d$ steps.


Notes:

  1. Base 2 makes this particularly easy. If you want to do the computation for a base other than 2, you'll need to do the following

     n = n * b          # Note: n < d
     f = floor(n / d)   # Thus: f < b
     Output f as the next digit
     n = n - d * f      # Or: n = n mod d
    

    The simpler base 2 case is just what happens if you plug $b=2$ into the above calculation.

$\endgroup$
1
  • $\begingroup$ Excellent answer, thank you! The solution involving using integers to generate rational numbers instead of rounding off the small differences is exactly what I was looking for. $\endgroup$ – wasabiwaffles Sep 21 '20 at 2:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.