MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG

COMPUTING SCIENCE

The Higher Arithmetic

How to count to a zillion without falling off the end of the number line

Brian Hayes

Shaping a Number System

Is there any genuine need for an arithmetic that can reach beyond the limits of IEEE floating point? I have to admit that I seldom write a program whose output is a number greater than 1038. But that’s not the end of the story.

A program with inputs and outputs of only modest size may nonetheless generate awkwardly large intermediate values. Suppose you want to know the probability of observing exactly 1,000 heads in 2,000 tosses of a fair coin. The standard formula calls for evaluating the factorial of 2,000, which is 1×2×3×…×2,000 and is sure to overflow. You also need to calculate (½)2,000, which could underflow. Although the computation can be successfully completed with floating-point numbers—the answer is about 0.018—it requires careful attention to cancellations and reorderings of the operations. A number system with a wider range would allow a simpler and more robust approach.

In 1993 Lozier described a more substantial example of a program sensitive to numerical range. A simulation in fluid dynamics failed because of severe floating-point underflow; redoing the computation with the symmetric version of level-index arithmetic produced correct output.

Persuading the world to adopt a new kind of arithmetic is a quixotic undertaking, like trying to reform the calendar or replace the QWERTY keyboard. But even setting aside all the obstacles of history and habit, I’m not sure how best to evaluate the alternatives in this case. The main conceptual question is this: Since we don’t have enough numbers to cover the entire number line, what is the best distribution of the numbers we do have? Fixed-point systems sprinkle them uniformly. Floating-point numbers are densely packed near the origin and grow farther apart out in the numerical hinterland. In the level-index system, the core density is even greater, and it drops off even more steeply, allowing the numbers to reach the remotest outposts.

Which of these distributions should we prefer? Perhaps the answer will depend on what numbers we need to represent—and thus on how quickly the national debt continues to grow.

©Brian Hayes

Bibliography

  • Clenshaw, C. W., and F. W. J. Olver. 1984. Beyond floating point. Journal of the Association for Computing Machinery 31:319–328.
  • Clenshaw, C. W., F. W. J. Olver and P. R. Turner. 1989. Level-index arithmetic: An introductory survey. In Numerical Analysis and Parallel Processing: Lectures Given at the Lancaster Numerical Analysis Summer School, 1987, pp. 95–168. Berlin: Springer-Verlag.
  • Hamada, Hozumi. 1987. A new real number representation and its operation. In Proceedings of the Eighth Symposium on Computer Arithmetic, pp. 153–157. Washington, D.C.: IEEE Computer Society Press.
  • Lozier, D. W., and F. W. J. Olver. 1990. Closure and precision in level-index arithmetic. SIAM Journal on Numerical Analysis 27:1295–1304.
  • Lozier, Daniel W. 1993. An underflow-induced graphics failure solved by SLI arithmetic. In Proceedings of the 11th Symposium on Computer Arithmetic, pp. 10–17. Los Alamitos, Calif.: IEEE Computer Society Press.
  • Matsui, Shourichi, and Masao Iri. 1981. An overflow/underflow-free floating-point representation of numbers. Journal of Information Processing 4:123–133.
  • Turner, Peter R. 1991. Implementation and analysis of extended SLI operations. In Proceedings of the 10th Symposium on Computer Arithmetic, pp. 118–126. Los Alamitos, Calif.: IEEE Computer Society Press.





» Post Comment

 

EMAIL TO A FRIEND :

Subscribe to American Scientist