ABSTRACT
We present Ryū, a new routine to convert binary floating point numbers to their decimal representations using only fixed-size integer operations, and prove its correctness. Ryū is simpler and approximately three times faster than the previously fastest implementation.
Supplemental Material
- Ulf Adams. 2018. ulfjack/ryu. (Feb. 2018). https://github.com/ulfjack/ryuGoogle Scholar
- Marc Andrysco, Ranjit Jhala, and Sorin Lerner. 2016. Printing Floating-point Numbers: A Faster, Always Correct Method. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '16). ACM, New York, NY, USA, 555- 567. Google ScholarDigital Library
- Robert G. Burger and R. Kent Dybvig. 1996. Printing Floating-point Numbers Quickly and Accurately. In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation (PLDI '96). ACM, New York, NY, USA, 108s116. Google ScholarDigital Library
- Jerome Toby Coonen. 1980. An Implementation Guide to a Proposed Standard for Floating Point Arithmetic. Computer 13, 1 (Jan. 1980), 68s79. See errata in [5]. Google ScholarDigital Library
- Jerome Toby Coonen. 1981. Errata: An Implementation Guide to a Proposed Standard for Floating Point Arithmetic. Computer 14, 3 (March 1981), 62. See also [4]. Google ScholarDigital Library
- Florian Loitsch et al. 2017. google/double-conversion. (September 2017). https://github.com/google/double-conversion_commit_fe9b384793c4e79bd32133dc9053f27b75a5eeae.Google Scholar
- David M. Gay. 1990. Correctly Rounded Binary-Decimal and Decimal-Binary Conversions. Technical Report. AT&T Bell Laboratories. Numerical Analysis Manuscript 90-10.Google Scholar
- Torbjörn Granlund and Peter L. Montgomery. 1994. Division by Invariant Integers Using Multiplication. In Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation (PLDI '94). ACM, New York, NY, USA, 61s72. Google ScholarDigital Library
- IEEE Computer Society. Microprocessor Standards Committee and Institute of Electrical and Electronics Engineers and IEEE-SA Standards Board. 2008. 754-2008 - IEEE Standard for Floating-Point Arithmetic. Institute of Electrical and Electronics Engineers (IEEE), New York.Google Scholar
- Aubrey Jaffer. 2013. Easy Accurate Reading and Writing of Floating-Point Numbers. (October 2013). https://arxiv.org/abs/1310.8121v6 Updated January 2015.Google Scholar
- Donald Ervin Knuth. 1997. The Art of Computer Programming (3rd ed.). Vol. I: Fundamental Algorithms. Addison-Wesley, Boston, Massachusetts, United States, Chapter 1.2.1 Mathematical Induction, p. 13-17.Google Scholar
- Donald Ervin Knuth. 1997. The Art of Computer Programming (3rd ed.). Vol. II: Seminumerical Algorithms. Addison-Wesley, Boston, Massachusetts, United States, Chapter 4.4 Radix Conversion, p. 326.Google ScholarDigital Library
- Florian Loitsch. 2010. Printing Floating-Point Numbers Quickly and Accurately with Integers. In Proceedings of the ACM SIGPLAN 2010 Conference on Programming Language Design and Implementation, PLDI 2010. ACM, New York, NY, USA, 233-243. Google ScholarDigital Library
- Klaus Samelson and Friedrich L. Bauer. 1953. Optimale Rechengenauigkeit bei Rechenanlagen mit gleitendem Komma. Zeitschrift für angewandte Mathematik und Physik (ZAMP) 4, 4 (Jul 1953), 312-316.Google Scholar
- Guy L. Steele, Jr. and Jon L. White. 1990. How to Print Floating-point Numbers Accurately. In Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation (PLDI '90). ACM, New York, NY, USA, 112s126. Google ScholarDigital Library
- Donald Taranto. 1959. Binary Conversion, with Fixed Decimal Precision, of a Decimal Fraction. Commun. ACM 2, 7 (July 1959), p. 27. Google ScholarDigital Library
Index Terms
- Ryū: fast float-to-string conversion
Recommendations
Ryū: fast float-to-string conversion
PLDI '18We present Ryū, a new routine to convert binary floating point numbers to their decimal representations using only fixed-size integer operations, and prove its correctness. Ryū is simpler and approximately three times faster than the previously fastest ...
Ryū revisited: printf floating point conversion
Ryū Printf is a new algorithm to convert floating-point numbers to decimal strings according to the printf %f, %e, and %g formats: %f generates ‘full’ output (integer part of the input, dot, configurable number of digits), %e generates scientific output (...
Finding the Cyclic Covers of a String
WALCOM: Algorithms and ComputationAbstractWe introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any nonempty string X of length n, a factor W of X is called a cyclic cover if every position of X belongs to an occurrence of a cyclic ...
Comments