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

COMPUTING SCIENCE

The Higher Arithmetic

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

Brian Hayes

On the Level

The third scheme I want to mention here addresses the problem of overflow. If you are trying to maximize the range of a number system, an idea that pops up quite naturally is to replace mere exponents with towers of exponents. If 2N can’t produce a number large enough for your needs, then try


 Towers of exponents

(Whatever the mathematical merits of such expressions, they are a typographical nightmare, and so from here on I shall replace them with a more convenient notation, invented by Donald E. Knuth of Stanford University: 2222N is equivalent to the last of the three towers shown above. It is to be evaluated from right to left, just as the tower is evaluated from top to bottom.)

Number systems based on iterated exponentiation have been proposed several times; for example, they are mentioned by Matsui and Iri and by Hamada. But one particular version of the idea, called the level-index system, has been worked out with such care and thoughtful analysis that it deserves closer attention. Level-index arithmetic is a lost gem of computer science. It may never make it into the CPU of your laptop, but it shouldn’t be forgotten.

The scheme was devised by Charles W. Clenshaw and Frank W. J. Olver, who first worked together (along with Alan Turing) in the 1940s at the National Physical Laboratory in Britain. They proposed the level-index idea in the 1980s, writing a series of papers on the subject with several other colleagues, notably Turner and Daniel W. Lozier, now of the National Institute of Standards and Technology (NIST). Clenshaw died in 2004; Olver is now at the University of Maryland and NIST, and is co-editing with Lozier a new version of the Handbook of Mathematical Functions by Abramowitz and Stegun.

Iterated exponentials can be built on any numeric base; most proposals have focused on base 2 or base 10. Clenshaw and Olver argue that the best base is e, the irrational number usually described as the base of the natural logarithms or as the limiting value of the compound-interest formula (1+1/n)n; numerically e is about 2.71828. Building numbers on an irrational base is an idea that takes some getting used to. For one thing, it means that almost all numbers that have an exact representation are irrational; the only exceptions are 0 and 1. But there’s no theoretical difficulty in constructing such numbers, and there’s a good reason for choosing base e.

In the level-index system a number is represented by an expression of the form ee em, where the m at the end of the chain is a fractional quantity analogous to the mantissa of a logarithm. The number of up-arrows—or in other words the height of the exponential tower—depends on the magnitude of the number being represented.

To convert a positive number to level-index form, we first take the logarithm of the number, then the logarithm of the logarithm, and so on, continuing until the result lies in the interval between 0 and 1. Counting the successive logarithm operations gives us the level part of the representation; the remaining fraction becomes the index, the value of m in the expression above. The process is defined by the function f(x):

if 0 ≤ x < 1 then f(x) = x
else f(x) = 1 + f(ln(x)).

Here’s how the procedure applies to the national-debt amount shown in the photograph at the beginning of this piece:

ln(10,659,204,157,341) = 29.9974449
ln(29.9974449) = 3.40111221
ln(3.40111221) = 1.22410249
ln(1.22410249) = 0.20220791

We’ve taken logarithms four times, so the level is 4, and the fractional amount remaining becomes the index. Thus the level-index form of the national debt is 4.20220791 (which seems a lot less worrisome than $10,659,204,157,341).

The level-index system accommodates very large numbers. Level 0 runs from 0 to 1, then level 1 includes all numbers up to e. Level 2 extends as far as ee, or about 15.2. Beyond this point, the growth rate gets steep. Level 3 goes up to eee, which is about 3,814,273. Continuing the ascent through level 4, we soon pass the largest 64-bit floating-point number, which has a level-index value of about 4.63. The upper boundary of level 4 is a number with 1.6 million decimal digits. Climbing higher still puts us in the realm of numbers where even a description of the size is hopelessly impractical. Just seven levels are enough to represent all distinguishable level-index numbers. Thus only three bits need to be devoted to the level; the rest can be used for the index.

What about the other end of the number scale—the very small numbers? The level-index system is adequate for many purposes in this region, but a variation called symmetric level-index provides additional precision close to zero. In this scheme a number x between 0 and 1 is denoted by the level-index representation of 1/x.

Apart from its wide range, the level-index system has some other distinctive properties. One is smoothness. For floating-point numbers, a graph of the magnitudes of successive numbers is a jointed sequence of straight lines, with an abrupt change of slope at each power of 2. The corresponding graph for the level-index system is a smooth curve. For iterated exponentials this is true only in base e, which is the reason for choosing that base.

Olver also points out that level-index arithmetic is a closed system, like arithmetic with real numbers. How can that be? Since level-index numbers are finite, there must be a largest member of the set, and so repeated additions or multiplications should eventually exceed that bound. Although this reasoning is unassailable, it turns out that the system does not in fact overflow. Here’s what happens instead. Start with a number x, then add or multiply to generate a new larger x, which is rounded to the nearest level-index number. As x grows very large, the available level-index values become sparse. At some point, the spacing between successive level-index values is greater than the change in x caused by addition or multiplication. Thereafter, successive iterations of x round to the same level-index value.

This is not a perfect model of unbounded arithmetic. In particular, the process is not reversible: A long series of x + 1 operations followed by an equal number of x – 1s will not bring you back to where you started, as it would on the real number line. Still, the boundary at the end of the number line seems about as natural as it can be in a finite system.




comments powered by Disqus
 

EMAIL TO A FRIEND :

Of Possible Interest

Spotlight: Briefings

Computing Science: Belles lettres Meets Big Data

Technologue: Quantum Randomness

Subscribe to American Scientist