Algorithms for converting binary to decimal floating-point numbers (2021)

by swills on 2/9/2023, 10:55:15 PM with 5 comments

  • by dxf on 2/11/2023, 10:46:27 PM

    LLVM libc's decimal float conversion is based on Ulf Adams' Ryu Printf algorithm (one of the algorithms mentioned in the article). If you're interested in this area, you can look at the code, https://github.com/llvm/llvm-project/blob/main/libc/src/__su... and patches are always welcome :-)

    Initial commit, https://reviews.llvm.org/D131023

  • by thangalin on 2/11/2023, 10:44:17 PM

    In Java, many number-to-string implementations use NumberFormat. This is abysmally slow if the problem domain doesn't require internationalization, which is the case for machine-readable file formats, such as SVG. When I performance tested JMathTeX for rendering TeX, one major bottleneck for converting TeX into SVG elements was JFreeSVG's use of NumberFormat. Replacing NumberFormat with RyuDouble doubled the throughput[0]. (Reusing a StringBuilder to concatenate strings yielded another doubling.)

    For KeenType[1], a fork of the New Typesetting System (and more complete plain TeX implementation than JMathTeX), I added an SVG generator that converts floating point numbers to strings using a StackOverflow answer[2], not the Ryu algorithm[3]. Better performance, simpler algorithm.

    Knuth's advice holds: measure then optimize.

    [0]: https://github.com/jfree/jfreesvg/pull/30

    [1]: https://github.com/DaveJarvis/KeenType

    [2]: https://stackoverflow.com/a/10554128/59087

    [3]: https://github.com/DaveJarvis/KeenType/blob/fef005579021f394...

  • by mattmerr on 2/11/2023, 8:11:31 PM

    The variance in the 10^i number generation graphs stands out to me. Is number generation really so periodic in performance? I've seen bumpy graphs from O(log2) algorithms recursing additional times near each power of two, for example.

    For the last two graphs, is the x-axis "each run"? Maybe there's a better chart for this than a line chart, as you're really trying to show distributions, not the correlation between run # and time. (if the experiments are independent you could rearrange the order of the runs and the meaning shouldn't change)

  • by Lerc on 2/11/2023, 10:38:46 PM

    I really needed this a couple of years ago when I was writing some 8-bit asm. At the time it felt like this was mystical lost knowledge. Everything I encountered just said to use sprintf.