Floating-Point Printing and Parsing Can Be Simple and Fast
4 months ago
- #algorithm
- #floating-point
- #performance
- Floating-point printing and parsing can be simple and fast using unrounded scaling.
- Unrounded scaling computes an approximation to m * 2^e * 10^p, often in a single 64-bit multiplication.
- The algorithms presented run faster than existing methods like Dragon4, Grisu3, Ryū, and others.
- The post introduces unrounded numbers, which contain all information needed for rounding in various ways.
- Fixed-width printing formats floating-point numbers with a given number of decimal digits, at most 18.
- Parsing decimals converts decimal numbers of at most 19 digits into floating-point numbers.
- Shortest-width printing formats floating-point numbers using the shortest representation that parses back to the original number.
- Fast unrounded scaling is implemented with a short but subtle algorithm.
- The proof of fast scaling correctness is sketched, with full details in a companion post.
- Optimizations reduce fast unrounded scaling to a single 64-bit multiplication in many cases.
- Performance comparisons show the implementation outperforms earlier algorithms.
- The history and related work trace the origins of the ideas used in the post's algorithms.