0
$\begingroup$

Let's say I have a decimal floating-point number, i.e. a mantissa and precision (negative exponent), both represented as integers. How do I convert this into a binary floating point number (of the sort you find in most programming languages, with only the standard operations available). This should be done with maximum precision, ideally. The naive method of simply calculating $m \cdot 10^e$, where $m$ is the mantissa and $e$ the exponent, turns out to be very imprecise when $e$ is large, unfortunately.

I was also wondering how to do the reverse. I suspect the algorithm can't simply be reversed, due to the different representations.

Improve this question
$\endgroup$
2
  • $\begingroup$ Use the base conversion algorithm taught in school. $\endgroup$
    – Yuval Filmus
    Sep 7, 2017 at 7:24
  • 1
    $\begingroup$ Perhaps you can edit the question to explain what the intracies / non-trivialities are? It might help to explain what approaches you have considered and why you have rejected them (e.g., what you think the obvious approach is, and why you think it is unsuitable, and how you plan to evaluate answers). $\endgroup$
    – D.W. ♦
    Sep 7, 2017 at 22:17

2 Answers 2

Reset to default
3
$\begingroup$

I am not an expert in this area, but the following is what I know about this problem. This problem was solved in the following paper:

  • William D. Clinger. How to read floating point numbers accurately, ACM SIGPLAN Notices, 25(6) [Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation], pages 92–101, June 1990 (A PDF, you'll find other versions online)

This is also the reference cited by Knuth in TAOCP Volume 2, Exercise 17 in 4.4 (Radix Conversion).

In a retrospective published in 2004, the author looks back and cites the following additional references:

  • David Gay. Correctly rounded binary-decimal and decimal-binary conversions. Technical Report 90-10, AT&T Bell Laboratories, November 1990. At http://www.ampl.com/REFS/ (Direct link)

In particular, see function strtod in David Gay's dtoa.c available at http://www.netlib.org/fp/

The reverse problem (printing floating point numbers) is harder. It should probably be a separate question, but here are some references:

Popular expositions and other implementations:

Aside/Example: Even though this is a problem solved since 1990 (albeit with developments even last year), even Python until 2.6 had suboptimal printing of floating-point numbers, e.g. it would print float('2.2') as '2.2000000000000002'. It was fixed only in Python 2.7. See https://docs.python.org/2/whatsnew/2.7.html#python-3-1-features and https://docs.python.org/3/whatsnew/2.7.html#other-language-changes (specifically https://bugs.python.org/issue7117 and discussion at https://mail.python.org/pipermail/python-dev/2009-October/092958.html).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks very much! I'll have a proper look through this on the weekend, when I get the time, but it looks like just what I want. $\endgroup$
    – Noldorin
    Sep 8, 2017 at 23:43
  • $\begingroup$ @Noldorin I saw you accepted this answer just now, but let me know if this helped or if you felt it needs some explanation… the basic algorithm is simple (just the naive algorithm executed with sufficient precision, more or less, in most cases); most of the subtlety in the papers is in determining how much precision is enough, and being efficient / optimal about it. $\endgroup$
    – ShreevatsaR
    Sep 13, 2017 at 2:07
  • $\begingroup$ Yeah, I think there's enough info in the links you've provided to cover what I want, which I appreciate. As for the basic algorithm you refer to, I don't think it's the same as the naive (really naive!) algorithm I stated in my post, but I rather expected as much. Anyway, I think I'll endeavour to understand both algorithms by reading over some of the material, then try my hand at a port to my intended language (Rust). Any particular existing implementations that you recommend as both lucid and well-optimised? $\endgroup$
    – Noldorin
    Sep 13, 2017 at 2:47
0
$\begingroup$

An example: 13.7 = 137 / 10. You can convert to the exact floating-point numbers 137 and 10, then divide with a floating point division, and get the correctly rounded result. There is a huge range of decimal numbers that can be converted that way.

If this fails, you can do the calculation with higher precision than required, find the best possible upper bounds for the rounding error involved, and check whether or not you can guarantee a correctly rounded result.

(For example, if I wanted a value correctly rounded to an integer, and I can calculate the result with an error < 0.001, and I get a result of 15.4989, then I know the rounded result is 15. If I get a result of 15.4991, I don't know the correctly rouned result).

Then you have to decide what kind of rounding error is acceptable to you. Part 1 will give you in many cases (and in the majority of practical cases) the correctly rounded result very, very quickly. Part 2 will give you the proven correctly rounded result in 99% of cases if you use extended precison for a floating-point result, also quite quickly. Using quad precision you will get the proven correct result in practically all cases, but a bit slower. Conversion with infinite precision is trivial, but slow.

There is a special case: If you generated decimal numbers as good approximations to floating-point numbers (say storing floating-point numbers in a file in human readable format), then converting decimal to floating-point by using slightly higher precision will always be successful.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is the naive an inaccurate method though. I was under the impression there was a much superior approach. $\endgroup$
    – Noldorin
    Sep 7, 2017 at 21:13
  • $\begingroup$ @Noldorin: If you find it, post it. I'm not holding my breath. $\endgroup$
    – gnasher729
    Sep 8, 2017 at 22:07
  • $\begingroup$ I think this is correct, but there is a wealth of detail hiding in phrases like “huge range of decimal numbers that can be converted that way” (what range exactly), “majority of practical cases”, “99% of cases” (or is it 99.9%?), “practically all cases”, “higher precision than required” (how much higher precision), “find the best possible upper bounds for the rounding error involved” (how), etc. So the challenge is to nail down all these details, and stay reasonably fast doing so. (An example in Python: float('903835381541353.5') is a better approximation than float(9038353815413535)/10.) $\endgroup$
    – ShreevatsaR
    Sep 8, 2017 at 23:42
  • $\begingroup$ I updated my post to mention the "naive" method I spoke of. It seems I may not be right that it's "just" imprecise when $e$ (the exponent) is large though. $\endgroup$
    – Noldorin
    Sep 8, 2017 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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