Large Numbers
First page . . . Forward to page 3 . . . Last page (page 11)
The Knuth -yllion Notation
Donald Knuth created a system that extends much further than the standard Latin-based system. In the essay Supernatural Numbers[43] he wrote:
When we stop to examine our conventional numbers, it is immediately apparent that these names are "Menschenwerk"; they could have been designed much better. For example, it would be better to forget about thousands entirely, and to make a myriad (104) the next unit after hundreds.
So in this system the word "thousand" is not used, and instead everything up to 9999 is named using the traditional names for numbers up to 99 plus "hundred", and no comma is used. For example:
127 = One hundred twenty-seven
1000 = Ten hundred
1356 = Thirteen hundred fifty-six
3000 = Thirty hundred
4192 = Forty-one hundred ninety-two
104 is called "myriad", a name that originally comes from ancient Egypt. It is written 1,0000 — note that the comma is added to separate the lowest four digits, not three. Numbers up to 9999,9999 are named like so:
1,2345 = One myriad twenty-three hundred forty-five
10,0000 = Ten myriad
26,0044 = Twenty-six myriad forty-four
100,0000 = One hundred myriad
1000,0000 = Ten hundred myriad
1400,2054 = Fourteen hundred myriad twenty hundred fifty-four
4309,8127 = Forty-three hundred nine myriad eighty-one hundred twenty-seven
108 is called "myllion" (pronounced "mile-yun") and is written 1;0000,0000. Notice a new punctuation mark is used to represent "myllion". Numbers up to 9999,9999;9999,9999 are named as in these examples:
9;0000,0000 = Nine myllion
100;0001,0000 = One hundred myllion one myriad
2000;0000,1234 = Twenty hundred myllion twelve hundred thirty four
4,0006;5020,0100 = Four myriad six myllion fifty hundred twenty myriad one hundred
Then 1016 is called "byllion", and a new punctuation mark is used. Knuth points out the advantage of avoiding the long scale vs. short scale confusion. Notice each punctuation mark can be read exactly when it appears so it's easy to read off these numbers in words:
1844:6744,0737;0955,1616 = Eighteen hundred forty-four byllion sixty-seven hundred forty-four myriad seven hundred thirty-seven myllion nine hundred fifty-five myriad sixteen hundred sixteen
Each new number name is the square of the previous one — therefore, each new name allows us to name numbers with twice as many digits. This gives us a lot more mileage out of each name. Knuth continues borrowing the traditional names changing "illion" to "yllion" on each one. "vigintyllion" ends up being 104194304, a bit beyond the upper limit of class-2 numbers.
In the same article [43], Knuth reports that Hsu Yo (living near the end of the Han dynasty) used the names wan=104, i=108, chao=1016 and ching=1032 as part of a nomenclature system for large numbers. The names descended into the present-day Chinese wàn, yì, zhào and jing respectively. Usage of the names zhào and jing for 1016 and 1032 respectively is the "higher degree system" reported by [50], but this usage did not continue into the present (see Wikipedia's Chinese numerals article). The ancient usage corresponds directly to myirad, myllion, byllion and tryllion in Knuth's system, including the ordering of words to make the names of arbitrary large numbers. A specific example showing the recursive grouping, with Chinese spelling, phonetic pronunciation and translation into more familiar numeric notation is shown in [50] figure 21.41 (page 278). The Chinese names continue with gai which would be 1064, all the way up to zài=104096 (which is Knuth's decyllion), but usage of the larger ones has only ever been "theoretical" — no actual usage is known.
Upper Limit of Class 2
As with class-0 and class-1, the limit for class-2 numbers is subjective. I defined class 2 numbers as those that "can be represented in exact form using place-value notation", and this depends on where and how the digits are recorded, which in turn depends on what you want to do with the number. If you just want to store the exact value of a number and not do anything with it, you can keep it on a tape or disk, which has much more capacity — perhaps as much as 1012 digits. For some simpler algorithms, such as squaring a number and adding together all the digits of the result, the limit might be quite large — say a billion digits.
In the article "A Theorem for Knuth-Arrows" [61], Sbiis Saibian defines the same concept by the criterion its full decimal form can be feasibly be stored in memory, calling such numbers "trivially large"; anything larger (i.e. class 3 and above) is "non-trivially large" or "remote", with additional superlatives for class 4 and higher.
For algorithms involving many intermediate results, lookup tables or auxiliary data, or when many iterations of calculation are needed to get a useful result, the practical limit might be lower — perhaps as few as 1000 or 10000 digits. Perhaps the limit for "class 2" should be anywhere from 103 to 1012 digits, depending on the desired operation. It is convenient to just continue the pattern and specify that "class 2" ends at 1 million digits, i.e. numbers up to 101000000 or 10106. That's what we'll use here and in the following discussion.
Class-3 Numbers
Class-3 numbers are those that can be represented inexactly using scientific notation, to within a given percentage of error. Numbers about the size of Googolplex are class-3 numbers, although Googolplex itself can be represented exactly. Class-3 numbers include (almost) all combinatoric enumerations of physical systems (i.e. the number of possible states of a system containing as many particles as the observable universe, see my googolplex notes). The limit of class-3 numbers depends on the limit of class-2 numbers and the base. As I suggested above. For convenience and to continue the pattern (see the class 2 introduction), we'll say that class-3 goes from 10106 to about 10101000000.
Class-3 numbers are the largest which can effectively be compared to see if they are of comparable magnitude. For example, the following two numbers are class-3 (and are at the low end, as class-3 numbers go) :
A = 279641170620168673833
B = 350247984153525417450
Which is larger?
We cannot compute the exact values of these two numbers and compare directly — they have way too many digits to store the values on a computer. That is the nature of class-3 numbers. However, we can represent both in scientific notation with 10 digits of accuracy. This is accomplished in much the same way that your computer or a scientific calculator would do it. Starting with the logarithm of 2 (or 3), multiply by the exponent, then divide by the logarithm of 10, separating the integer from the fractional part, and use the fractional part to determine the first few digits of the answer. In this case we get:
A = 5.0760252191 × 1023974381246463762439
B = 5.0760252191 × 1023974381246463762439
Now you begin to see the problem. Using 10 decimal places, both values seem to be the same. (We know they are not, because one is a power of 2 and must be even, and the other, being a power of 3 is odd). As it turns out, you need at least 20 decimal places to see that B is slightly larger.
Bowers' Named Numbers
Jonathan Bowers 10, about whom we'll discuss a lot more further below, has invented many names for special numbers in this area: myrillion=1030003, micrillion=103000003 (same as Henkle's milli_millillion), killillion=103×103000+3, megillion=103×103000000+3, and likewise with higher SI prefixes. He then extends the SI prefixes with the one of many ad-hoc naming systems discussed in my ad-hoc Googolisms article elsewhere. There are also a few ad-hoc Chuquet extensions that attempt to reach up into this area.
Class-4 Numbers
Now we move on to Class-4 numbers and higher classes. You may have already seen a pattern here; we'll just continue the pattern:
class-4 numbers are those numbers that are larger than class-3, and whose logarithm can be represented as a class-3 number.
Now we have another problem as before. Which of the following class-4 numbers is larger?
C = 22283
D = 33352
as before we take the logarithm of both but this time we must do it twice, and we find
ln(ln(C)) = ln(ln(2)) + [ln(2) * 9671406556917033397649408]
= 6703708186976009930559261.24579...
ln(ln(D)) = ln(ln(3)) + [ln(3) * 6461081889226673298932241]
= 7098223961595389530659098.10481...
so D is larger.
Skewes' Numbers
These numbers occur in the study of prime numbers, and particularly the frequency of occurrence of prime numbers. Gauss' well-known estimate of the number of prime numbers less than N is
oo / | 1 Li(n) = | ----- du ~= u/(ln(u)-1) | ln(u) / u=2For all values of n up to 1022 (which is as far as we've been able to compute so far) Li(n) is an overestimate. Littlewood showed that above some value of n it becomes an underestimate, then at an even higher value of n it becomes an overestimate again and so on. In 1933 Skewes showed that (if the Riemann Hypothesis is true) the first crossing cannot be greater than eee79. This is the first or "Riemann true" Skewes' Number; it is class-4. Converted to base 10, the value is normally approximated as 101010^34; a more accurate approximation is 10108.852142×1033 or 10108852142197543270606106100452735038.55.
Since then, others have improved the estimate dramatically. Conway and Guy (The Book of Numbers, page 61) cite the result of Lehman, who in 1966 gave an upper bound of about 101167. According to Eric W. Weisstein and Wikipedia, in 1987 H. J. J. te Riele reduced the upper bound of the first crossing to ee(27/4), a class 2 number approximately equal to 8.185×10370. In 2000 Bays and Hudson found an actual crossover point using numerical techniques — around 1.39822×10316. Most recently, in 2005 Patrick Demichel found a smaller crossover point near 1.397162914×10316. In any case, the original Skewes' Number is now just an interesting part of history.
In 1955 Skewes also defined an upper bound if the Riemann Hypothesis is false: 1010101000. This is the "second Skewes' Number"; it is much larger, but still class-4.
Class 5 and Higher
In a similar way, we can define higher classes:
class-5 numbers are those numbers that are larger than class-4, and whose logarithm can be represented as a class-4 number.
class-N numbers are those numbers that are larger than class N-1, and whose logarithm can be represented as a class N-1 number.
but as it turns out, these higher classes aren't too useful for representing the large numbers of abstract mathematics. Once we get into the really big numbers like the ones discussed below, exponents are so unwieldy that they are no longer used directly — instead faster-growing functions like the hyper4 function are used.
Here is a summary of what has been covered so far:
|
Uncomputably Larger and Uncomparable
At this point it is useful to define the concept of uncomputably larger.
Uncomputably Larger: A is Uncomputably Larger than B if A is larger than B, but the difference does not show up when the numbers are expressed in the same system of representation (with a given standard number of digits).
A system of representation is any system of digits and/or symbols used to express numbers in a standard form that lends itself well to seeing which is bigger. Two examples are integers with a limited number of digits (like a calculator that overflows above 99999999) and standard scientific notation. There are some other computer-oriented examples on my Alternative Number Formats page. Mathematical formulas in general do not count (but they are addressed by the less precise concept of uncomparable, see below).
If A is a class 3 number number and K is class 2 or smaller, it is easy to distinguish A×K from A, but hard to distinguish A+K from A. So A+K is "uncomputably larger" than A.
For an example of this, imagine A has trillions of digits. If you add some small number to it, only the last few digits will change — and all of the digits would have to be stored and examined to tell the difference. On the other hand, multiplying A by a small number N will change all the digits, and you can distinguish the difference by comparing the logarithm of A to that of A×N
If A is a class 4 number and K is class 3 or smaller, it is easy to distinguish AK from A, but hard to distinguish A×K from A. A×K is uncomputably larger than A.
If A is a class 5 number and K is class 4 or smaller, it is easy to distinguish A④K from A, but hard to distinguish AK from A. (④ is the hyper4 operator). AK is uncomputably larger than A.
This pattern does not continue with higher operators, because the "class" system is based on exponents. For example, if A is a class 10 number and K is class 9 or smaller, it is still easy to distinguish A④K from A, and hard to distinguish AK from A.
I also define the term uncomparable:
Uncomparable: A and B are said to be Uncomparable if it is unknown how to distinguish which is larger. (This is a made-up word, and is not intended to be the antonym of "comparable".)
Notice that this definition depends not only on A and B but also on one's knowledge and/or ability. As you go to higher and higher operators and functions it becomes quite difficult to determine which values are larger than others (I refer to this later in my discussion of superclass 5). It is easy to see that Skewes' Number is bigger than googolplex, but not nearly so easy to figure out which of the "Graham-Rothschild number" and the Moser is bigger.
The "Graham-Rothschild number" and the Moser are defined with different systems of representation, and the two systems cannot be readily converted into each other. They would be called uncomparable until the two systems are studied and a method is developed to show which number is larger. Once such a method was developed, and it was determined which is larger, they are no longer "uncomparable".
To clarify all of this, here are examples of pairs of numbers as classified by the definitions computably larger and uncomparable:
|
Power Towers
A tower of exponents like eee79 mentioned above in the discussion of Skewes' numbers is often called a power tower. Notice how in the examples of class-3 numbers there are three numbers in the power tower, and in the class-4 examples there are 4 numbers in the power tower. But this isn't necessarily always the case, for example 2222} is a power tower with 4 numbers but its value is 65536, a class-1 number.
Problem : Start with the 3-level power tower 2210. Consider two different ways to make it bigger: Increase the bottom-most number, making it H210 where H is something really huge like 1000000, or make the power tower higher by making it S2210, where S is something really small like 1.001. Determine which is biggest: the original power tower X = 2210, or the two altered versions, A = 1000000210 or B = 1.0012210 ?
First we show that A and B are both bigger than X. A>X is obvious. For B it's less obvious. We're comparing:
B = 1.0012210 ⋛ 2210 = X
Convert both to a power of 2, by taking the log base 2 of 1.001, and repeat. We get:
B = (20.001442)2210 ⋛ 2210 = X
B = 2(0.001442 × 2210) ⋛ 2210 = X
log2B = 0.001442 × 2210 ⋛ 210 = log2X
log2B = 2(-9.4377 + 210) ⋛ 210 = log2X
log2(log2B) = -9.4377 + 210 ⋛ 10 = log2(log2X)
log2(log2B) is about 1014.56, much bigger than log2(log2X) which is 10. So B>X.
Now we need to compare A to B. Let's rewrite A as a power of 1.001:
A = (1.001(log1.0011000000))210 = 1.001(log1.0011000000) × (210)
Then it is a question of which of these is larger: A' = log1.0011000000 × 210 or B' = 2210. Substituting 210 = 1024, we're comparing A' = (log1.0011000000)×1024 to B' = 2^1024, so A'/B' = (log1.0011000000)×1024 / 21024. Cancelling powers of 2, we remove 1024 from the numerator and reduce the denominator to 21014: A'/B' = log1.0011000000 / 2^1014. log1.0011000000 is pretty large (it's a little over 13822) but 2^1014 is much much larger! So B' is larger, and therefore B is the biggest of our three power towers.
We could have used any really big number H in place of 1000000 and any small number S in place of 1.001 and B would still be the biggest, as long as logSH is less than 21014. 21014 is about 1.7556×10305, a class 2 number. To show how extreme this is, let H be a googol and S be 1+1/googol. logSH would be ln(10)×100×googol = 2.3026×10102, still much less than 21014. So even with this really huge H and really small S, the power tower S2210 is still bigger than H210.
In general, if you have a tower of exponents and you want to make it larger, you'll make it much larger by adding another exponent to the bottom than by increasing the size of the bottom exponent, as long as the tower of exponents has something fairly big at the top and the numbers involved are all class 1 or on the lower end of class 2. This leads to the (somewhat nonintuitive) result that if you're comparing two towers of exponents, you can look at how many exponents are in the tower and know right away which is larger. For example,
1.11.11.11000
is much larger than
100010001000
and
1.11.11.11.11.11.11.11000
(which has 7 levels of exponents with 1000 at the top) is much larger than
1000100010001000100010001000
(which has 6 levels of exponents).
A similar phenomenon, the power tower paradox, causes two power towers to be effectively the same if the numbers at the top are the same, even if the numbers near the bottom are different. For example, 271010100 is almost exactly the same as 101010100
If you're interested in trying some of these out, my Perl-based calculator program can handle everything discussed so far, up to power towers thousands of numbers high.
First page . . . Forward to page 3 . . . Last page (page 11)
Japanese readers should see: 巨大数論 (from @kyodaisuu on Twitter)
If you like this you might also enjoy my numbers page.
s.30