Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of any fixed precision. Hence the IEEE Standard for Binary Floating-Point Arithmetic does not require the result of such a conversion to be the best approximation. This paper presents an efficient algorithm that always finds the best approximation. The algorithm uses a few extra bits of precision to compute an IEEE-conforming approximation while testing an intermediate result to determine whether the approximation could be other than the best. If the approximation might not be the best, then the best approximation is determined by a few simple operations on multiple-precision integers, where the precision is determined by the input. When using 64 bits of precision to compute IEEE double precision results, the algorithm avoids higher-precision arithmetic over 99% of the time. The input problem considered by this paper is the inverse of an output problem considered by Steele and White: Given a binary floating point number, print a correctly rounded decimal representation of it using the smallest number of digits that will allow the number to be read without loss of accuracy. The Steele and White algorithm assumes that the input problem is solved; an imperfect solution to the input problem, as allowed by the IEEE standard and ubiquitous in current practice, defeats the purpose of their algorithm.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Clinger90	Clinger, William, and Jonathan Rees {editors}. Revisedn report on the algorithmic language Scheme. Technical Report CIS-TR-90-02, Department of Computer and Information Science, University of Oregon, 1990.
	Coonen80	Coonen, Jerome T. An implementation guide to a proposed standard for floating-point arithmetic. Computer 13, 1, January 1980, pages 68-79.
	Goldberg67	I. Bennett Goldberg, 27 bits are not enough for 8-digit accuracy, Communications of the ACM, v.10 n.2, p.105-106, Feb. 1967  [doi>10.1145/363067.363112]
	HW60	Hardy, G. H., and E. M. Wright. An Introduction to the Theory of Numbers, Fourth Edition. Oxford University Press, 1960.
	IEEE85	- IEEE Standard 754-1985. IEEE Standard for Binary Floating-Point Arithmetic. IEEE, New York, 1985.
	Knuth81	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	Matula68	David W. Matula, In-and-out conversions, Communications of the ACM, v.11 n.1, p.47-50, Jan. 1968  [doi>10.1145/362851.362887]
	Matula70	Matula, David W. A formalization of floatingpoint numeric base conversion. IEEE Transactions on Computers, C-19, 8, August 1970, pages 681-692.
	Rees86	J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986  [doi>10.1145/15042.15043]
	Steele90	Guy L. Steele, Jr. , Jon L. White, How to print floating-point numbers accurately, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.112-126, June 1990, White Plains, New York, United States

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  

• ACM SIGPLAN Notices
  Volume 25 ,  Issue 6   Jun. 1990