Online Encyclopedia

Large numbers

For information on how large numbers are named in English, see names of large numbers.

Large numbers are numbers that are large compared with the numbers used in everyday life. Very large numbers often occur in fields such as mathematics, cosmology and cryptography. Sometimes people refer to numbers as being "astronomically large". However, mathematically it is easy to define numbers that are much larger than occur even in astronomy.

Contents

1 Writing and thinking about large numbers

2 Large numbers in the everyday world

3 Large numbers and computers

4 "Astronomically large" numbers

5 Even larger numbers

5.1 Examples

6 Standardized system of writing very large numbers

7 Accuracy

8 Approximate arithmetic for very large numbers

9 Uncomputably large numbers

10 Infinite numbers

11 Notations

12 See also

13 External links

Writing and thinking about large numbers

Large numbers are often found in science, and scientific notation was created to handle both these large numbers and also very small numbers. 1.0 × 10⁹, for example, means one billion, a 1 followed by nine zeros: 1,000,000,000, and 1.0 × 10^-9 means one billionth, or 0.0000000001. Writing 10⁹ instead of nine zeros saves the reader the effort and hazard of counting a long string of zeros to see how large the number is.

Adding a 0 to a large number multiplies it by ten: 100 is ten times 10. In scientific notation, however, the exponent only increases by one, from 10¹ to 10². Remember then, when reading numbers in scientific notation, that small changes in the exponent equate to large changes in the number itself: 2.5 × 10⁵ dollars ($250,000) is a common price for new homes in the U.S., while 2.5 × 10¹⁰ dollars ($25 billion) would make you one of the world's richest people.

Large numbers in the everyday world

Some large numbers apply to things in the everyday world.

Examples of large numbers describing everyday real-world objects are:

cigarettes smoked in the United States in one year, on the order of 10¹² (one trillion)
bits on a computer hard disk (typically 10¹² to 10¹³)
number of cells in the human body > 10¹⁴
number of neuron connections in the human brain, 10¹⁴ (estimated)
Avogadro's number, approximately 6.022 × 10²³

Other examples are given in Orders of magnitude (numbers).

Large numbers and computers

Moore's Law, generally speaking, estimates that computers double in speed about every 18 months. This sometimes leads people to believe that eventually, computers will be able to solve any mathematical problem, no matter how complicated. This is not the case; computers are fundamentally limited by the constraints of physics, and certain upper bounds on what we can expect can be reasonably formulated.

First, a rule of thumb for converting between scientific notation and powers of two, since computer-related quantities are frequently stated in powers of two. Since the logarithm of 10 in base 2 is a little more than 3, multiplying a scientific notation exponent by 3 gives its approximate value as an exponent with a base of 2. For example, 10³ (1000) is somewhere in the neighborhood of 2⁹ (512). (But remember that when dealing with very large numbers, such "neighborhoods" will themselves be quite large).

Between 1980 and 2000, hard disk sizes increased from about 10 megabytes (1 × 10⁷) to over 100 gigabytes (1 × 10¹¹). A 100 gigabyte disk could store the names of all of Earth's six billion inhabitants without using data compression. But what about a dictionary-on-disk storing all possible passwords containing up to 40 characters? Assuming each character equals one byte, there are about 2³²⁰ such passwords, which is about 2 × 10⁹⁶. This paper http://arxiv.org/abs/quant-ph/0110141 points out that if every particle in the universe could be used as part of a huge computer, it could store only about 10⁹⁰ bits, less than one millionth of the size our dictionary would require.

Of course, even if computers can't store all possible 40 character strings, they can easily programmed to start creating and displaying them one at a time. As long as we don't try to store all the output, our program could run indefinitely. Assuming a modern PC could output 1 billion strings per second, it would take one billionth of 2 × 10⁹⁶ seconds, or 2 × 10⁸⁷ seconds to complete its task, which is about 6 × 10⁷⁹ years. By contrast, the universe is estimated to be 13.7 billion (1.37 × 10¹⁰) years old. Of course, computers will presumably continue to get faster, but the same paper mentioned before estimates that the entire universe functioning as a giant computer could have performed no more than 10¹²⁰ operations since the big bang. This is trillions of times more computation than is required for our string-displaying problem, but simply by raising the stakes to printing all 50 character strings instead of all 40 character strings we can outstrip the estimated computational potential of even the universe itself.

Problems like our simple string-displaying example grow exponentially in the number of computations they require, and are one reason why exponentially difficult problems are called "intractible" in computer science: for even small numbers like the 40 or 50 characters we used in our example, the number of computations required exceeds even theoretical limits on mankind's computing power. The traditional division between "easy" and "hard" problems is thus drawn between programs that do and do not require exponentially increasing resources to execute.

Such limits work to our advantage in cryptography, since we can safely assume that any cipher-breaking technique which requires more than, say, the 10¹²⁰ operations mentioned before will never be feasible. Of course, many ciphers have been broken by finding efficient techniques which require only modest amounts of computing power and exploit weaknesses unknown to the cipher's designer. Likewise, much of the research throughout all branches of computer science focuses on finding new, efficient solutions to problems that work with far fewer resources than are required by a naïve solution. For example, one way of finding the greatest common divisor between two 1000 digit numbers is to compute all their factors by trial division. This will take up to 2 × 10⁵⁰⁰ division operations, far too large to contemplate. But the Euclidean algorithm, using a much more efficient technique, takes only a fraction of a second to compute the GCD for even huge numbers such as these.

As a general rule, then, PCs in 2004 can perform 2⁴⁰ calculations in a few minutes. A few thousand PCs working for a few years could solve a problem requiring 2⁶⁴ calculations, but no amount of traditional computing power will solve a problem requiring 2¹²⁸ operations (which is about what would be required to break the 128-bit SSL commonly used in web browsers, assuming the underlying ciphers remain secure). Limits on computer storage are comparable. Quantum computers may allow certain problems to become feasible, but as of 2004 it is far too soon to tell.

"Astronomically large" numbers

Other large numbers are found in astronomy:

number of atoms in the visible universe, perhaps 10⁷⁹ to 10⁸¹, see Mass, Size, and Density of the Universe http://www.sunspot.noao.edu/sunspot/pr/answerbook/universe.html#q70
for astronomical numbers related to distance and time, see:
- orders of magnitude (length)
- orders of magnitude (time)

Large numbers are found in fields such as mathematics and cryptography.

The MD5 hash function generates 128-bit results. There are thus 2¹²⁸ (approximately 3.402×10³⁸) possible MD5 hash values. If the MD5 function is a good hash function, the chance of a document having a particular hash value is 2^-128, a value that can be regarded as equivalent to zero for most practical purposes. (But see birthday paradox.)

However, this is still a small number compared with the estimated number of atoms in the Earth, still less compared with the estimated number of atoms in the observable universe.

Even larger numbers

Combinatorial processes rapidly generate even larger numbers. The factorial function, which defines the number of permutations of a set of unique objects, grows very rapidly with the number of objects.

Combinatorial processes generate very large numbers in statistical mechanics. These numbers are so large that they are typically only referred to using their logarithms.

Gödel numbers, and similar numbers used to represent bit-strings in algorithmic information theory are very large, even for mathematical statements of reasonable length. However, some pathological numbers are even larger than the Gödel numbers of typical mathematical propositions.

Examples

googol = $10100$
googolplex = $10^{\mbox{googol}}=10^{\,\!10^{100}}=\mbox{googol}^{10^{98}}$ It is the number of states a system can be in that consists of $1098$ particles which can each be in googol states.

centillion = $10303$ or $10600$ , depending on number naming system
Skewes' numbers: the first is ca. $10^{\,\!10^{10^{34}}}$ , the second $10^{\,\!10^{10^{1000}}}$

The total amount of printed material in the world is 1.6 × 10¹⁸ bits, therefore the contents can be represented by a number which is ca. $2^{1.6 \times 10^{18}}\approx 10^{4.8 \times 10^{17}}$

For a "power tower", the most relevant for the value are the height and the last few values. Compare with googolplex:

$10^{\,\!100^{10}}=10^{10^{20}}$
$100^{\,\!10^{10}}=10^{10^{10.3}}$

Also compare:

$1.1^{\,\!1.1^{1.1^{1000}}}=10^{10^{1.02*10^{40}}}$
$1000^{\,\!1000^{1000}}=10^{10^{3000.48}}$

The first number is much larger than the second, due to the larger height of the power tower, and in spite of the small numbers 1.1 (however, if these numbers are made 1 or less, that greatly changes the result). Comparing the last number with $10^{\,\!10^{10}}$ , in the number 3000.48, the 1000 originates from the third number 1000 in the original power tower, a factor 3 comes from the second number 1000, and the minor term 0.48 comes from the first number 1000.

A very large number written with just three digits and ordinary exponentiation is $9^{\,\!9^9} \approx 10^{369,693,100}$ .

Standardized system of writing very large numbers

A standardized way of writing very large numbers allows them to be easily sorted in increasing order, and one can get a good idea of how much larger a number is than another one.

Tetration with base 10 can be used for very round numbers, each representing an order of magnitude in a generalized sense.

Numbers in between can be expressed with a power tower of numbers 10, with at the top a regular number, possibly in scientific notation, e.g. $10^{\,\!10^{10^{10^{10^{4.829*10^{183230}}}}}}$ , a number between $10\uparrow\uparrow 7$ and $10\uparrow\uparrow 8$ (if the exponent quite at the top is between 10 and $1010$ , like here, the number like the 7 here is the height).

If the height is too large to write out the whole power tower, a notation like $(10\uparrow)^{183}(3.12*10^6)$ can be used, where $(10\uparrow)^{183}$ denotes a functional power of the function $f (n) = 10 n$ (the function also expressed by the suffix "-plex" as in googolplex, see the Googol family).

Various names are used for this representation:

base-10 exponentiated tower form
tetrated-scientific notation
incomplete (power) tower

The notation $(10\uparrow)^{183}(3.12*10^6)$ is in ASCII ((10^)^183)3.12e6; a proposed simplification is 10^^[email protected]; the notations 10^^[email protected] and 10^^[email protected] are not needed, one can just write 10^3.12e6 and 3.12e6.

Thus googolplex = 10^^2@100 = 10^^3@2 = 10^^[email protected]; which notation is chosen may be considered on a number-by-number basis, or uniformly. In the latter case comparing numbers is sometimes a little easier. For example, comparing 10^^[email protected] with 10^6e23 requires the small computation 10^.8=6.3 to see that the first number is larger.

To standardize the range of the upper value (after the @), one can choose one of the ranges 0-1, 1-10, or 10-1e10:

In the case of the range 0-1, an even shorter notation is (here for googolplex) like 10^^3.301 (proposed by William Elliot http://groups.google.com/groups?hl=en&lr=&newwindow=1&safe=off&selm=200204110321
13.I50801-100000%40agora.rdrop.com ). This is not only a notation, it provides at the same time a generalisation of 10^^x to real x>-2 (10^^4@0=10^^3, hence the integer before the point is one less than in the previous notation). This function may or may not be suitable depending on required smoothness and other properties; it is monotonically increasing and continuous, and satisfies 10^^(x+1) = 10^(10^^x), but it is only piecewise differentiable. The inverse function is a super-logarithm or hyper-logarithm, defined for all real numbers, also negative numbers. See also Extension of tetration to real numbers.
The range 10-1e10 brings the notation closer to ordinary scientific notation, and the notation reduces to it if the number is itself in that range (the part "10^^0@" can be dispensed with).

Another example:

$2\uparrow\uparrow\uparrow 4 = \begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}}\\ \qquad\quad\ \ \ 65,536\mbox{ copies of }2 \end{matrix}\approx (10\uparrow)^{65,531}(6.0 \times 10^{19,728})$ (between $10\uparrow\uparrow 65,533$ and $10\uparrow\uparrow 65,534$ )

The "order of magnitude" of a number (on a larger scale than usually meant), can be characterized by the number of times (say n) one has to take the $l o g 10$ to get a number between 1 and 10. Then the number is between $10\uparrow\uparrow n$ and $10\uparrow\uparrow (n+1)$

An obvious property that is yet worth mentioning is:

$10^{(10\uparrow)^{n}x}=(10\uparrow)^{n}10^x$

I.e., if a number x is too large for a representation $(10\uparrow)^{n}x$ we can make the power tower one higher, replacing x by $l o g 10 x$ , or find x from the lower-tower representation of the $l o g 10$ of the whole number. If the power tower would contain one or more numbers different from 10, the two approaches would lead to different results, corresponding to the fact that extending the power tower with a 10 at the bottom is then not the same as extending it with a 10 at the top (but, of course, similar remarks apply if the whole power tower consists of copies of the same number, different from 10).

If the height of the tower is not exactly given then giving a value at the top does not make sense, and a notation like $10\uparrow\uparrow(7.21*10^8)$ can be used.

If the value after the double arrow is a very large number itself, the above can recursively be applied on that value.

Examples:

$10\uparrow\uparrow 10^{\,\!10^{10^{3.81*10^{17}}}}$ (between $10\uparrow\uparrow\uparrow 2$ and $10\uparrow\uparrow\uparrow 3$ )

$10\uparrow\uparrow 10\uparrow\uparrow (10\uparrow)^{497}(9.73*10^{32})$ (between $10\uparrow\uparrow\uparrow 4$ and $10\uparrow\uparrow\uparrow 5$ )

Some large numbers which one may try to express in such standard forms include:

External link: Notable Properties of Specific Numbers http://home.earthlink.net/~mrob/pub/math/numbers-14.html (last page of a series which treats the numbers in ascending order, hence the largest numbers in the series)

Accuracy

Note that for a number $10 p$ , one unit change in p changes the result by a factor 10. In a number like $10^{\,\!6.2 \times 10^3}$ , with the 6.2 the result of proper rounding, the true value of the exponent may be 50 less or 50 more. Hence the result may be a factor $1050$ too large or too small. This is seemingly an extremely poor accuracy, but for such a large number it may be considered fair. The idea that it is the relative error that counts (a large error in a large number may be relatively small and therefore acceptable), is taken a step further here: the number is so large that even a large relative error may be acceptable. Perhaps what counts is the relative error in the exponent.

Approximate arithmetic for very large numbers

In this context approximately equal may for example mean that two numbers are both written $10^{\,\!10^{10^{10^{10^{4.829*10^{183230}}}}}}$ , with the true values instead of 4.829 being e.g. 4.8293 and 4.8288.

The sum and the product of two very large numbers are both approximately equal to the larger one.
$(10^a)^{\,\!10^b}=10^{a 10^b}=10^{10^{b+\log _{10} a}}$

Hence:

A very large number raised to a very large power is approximately equal to the larger of the following two values: the first value and 10 to the power the second. For example, for very large n we have $n^n\approx 10^n$ (see e.g. the computation of mega) and also $2^n\approx 10^n$ . Thus $2\uparrow\uparrow 65536 > 10\uparrow\uparrow 65533$ , see table.

Uncomputably large numbers

The busy beaver function Σ is an example of a function which grows faster than any computable function. Its value for even relatively small input is huge. The values of Σ(n) for n = 1, 2, 3, 4 are 1, 4, 6, 13. Σ(5) is not known but is definitely ≥ 4098. Σ(6) is at least 1.29×10⁸⁶⁵.

Infinite numbers

See main article cardinal number

Although all these numbers above are very large, they are all still finite. Some fields of mathematics define infinite and transfinite numbers.

aleph-null is the cardinality of the infinite set of the integers
aleph-one is the next highest cardinal number.
C is the cardinality of the reals. The proposition that C=Aleph-one is known as the continuum hypothesis.
Mahlo cardinals
Indescribable cardinal s

Beyond all these, Georg Cantor's conception of the Absolute Infinite surely represents the absolute largest possible concept of "large number".

Notations

Some notations for extremely large numbers:

Knuth's up-arrow notation / hyper operators / Ackermann function, including tetration
Conway chained arrow notation
Steinhaus-Moser notation; apart from the method of construction of large numbers, this also involves a graphical notation with polygons; alternative notations, like a more conventional function notation, can also be used with the same functions.

These notations are essentially functions of integer variables, which increase very rapidly with those integers. Ever faster increasing functions can easily be constructed recursively by applying these functions with large integers as argument.

Note that a function with a vertical asymptote is not helpful in defining a very large number, although the function increases very rapidly: one has to define an argument very close to the asymptote, i.e. use a very small number, and constructing that is equivalent to constructing a very large number, e.g. the reciprocal.

External links

"Large Numbers" and "Notable Properties of Specific Numbers" - Robert Munafo http://home.earthlink.net/~mrob/pub/math/largenum.html
Big numbers - Susan Stepney http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm
Hamlet is a Big Number - Jim Blowers (1) http://jimvb.home.mindspring.com/hamlet.htm , (2) http://jimvb.home.mindspring.com/ComNum.htm
How to calculate with large numbers - Dave L. Renfro http://groups.google.com/groups?selm=28ae5e5e.0204081449.3b8479c4%40posting.goog
le.com&output=gplain
Graham's number and rapidly growing functions - Dave L. Renfro http://mathforum.org/discuss/sci.math/m/394644/394645
Discussion and modification of notation http://groups.google.com/groups?hl=en&lr=&newwindow=1&safe=off&threadm=28ae5e5e.
0204081449.3b8479c4%40posting.google.com&rnum=1&prev=/groups%3Fnum%3D100%26hl%3D
en%26lr%3D%26newwindow%3D1%26safe%3Doff%26q%3D%2B%2522tetration%2522%2B%253A%2B%
2522scientific%2Bnotation%2522
Ackermann’s function and new arithmetical operations - Rubtsov and Romerio http://www.rotarysaluzzo.it/filePDF/Iperoperazioni%20(1).pdf (pdf)
wiki:ReallyBigNumbers
http://michaelhalm.tripod.com/mathematics_beyond_the_googol.htm (various terminology for large numbers; contains errors)

Categories: Mathematical notation

Last updated: 02-03-2005 14:38:47

Last updated: 02-26-2005 05:11:48

Your Online Encyclopedia

Online Encylopedia and Dictionary Research Site