Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm to convert an IEEE 754 double to a string?

Tags:

Many programming languages that use IEEE 754 doubles provide a library function to convert those doubles to strings. For example, C has sprintf, C++ has stringstream, Java has Double.toString, etc.

Internally, how are these functions implemented? That is, what algorithm(s) are they using to convert the double into a string representation, given that they are often subject to programmer-chosen precision limitations?

Thanks!

like image 358
templatetypedef Avatar asked Aug 22 '11 21:08

templatetypedef


1 Answers

The code used by various software environments to convert floating-point numbers to string representations is typically based on the following publications (the work by Steele and White is particularly frequently cited):

Jerome T. Coonen: "An Implementation Guide to a Proposed Standard for Floating-Point Arithmetic." Computer, Vol. 13, No. 1, January 1980, pp. 68-79

Guy. L. Steele Jr. and J. L. White: "How to print floating-point numbers accurately". In proceedings of ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, White Plains, New York, June 1990, pp. 112-126

David M. Gay: "Correctly rounded binary-decimal and decimal-binary conversions." Technical Report 90-10, AT&T Bell Laboratories, November 1990.

Some relevant followup work:

Robert G. Burger and R. Kent Dybvig: "Printing floating-point numbers quickly and accurately." In proceedings of ACM SIGPLAN 1996 conference on Programming Language Design and Implementation, Philadelphia, PA, USA, May 1996, pp. 108-116

Guy L. Steele Jr. and Jon L. White: "Retrospective: How to print floating-point numbers accurately." ACM SIGPLAN Notices, Vol. 39, No. 4, April 2004, pp. 372–389

Florian Loitsch: "Printing floating-point numbers quickly and accurately with integers." In proceedings of 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, Toronto, ON, Canada, June 2010, pp. 233-243

Marc Andrysco, Ranjit Jhala, and Sorin Lerner: "Printing floating-point numbers: a faster, always correct method." ACM SIGPLAN Notices, Vol. 51, No. 1, January 2016, pp. 555-567

Ulf Adams: "Ryū: fast float-to-string conversion." ACM SIGPLAN Notices, Vol. 53, No. 4, April 2018, pp. 270-282

like image 85
njuffa Avatar answered Sep 25 '22 03:09

njuffa