Large numbers

From Wikipedia, the free encyclopedia

"Big numbers" redirects here. For the comic book series, see Big Numbers. For the V'ənen Taut people and language, see Big Nambas.

For the naming of large numbers in English, see names of large numbers.

Large numbers are numbers that are significantly larger than those ordinarily used in everyday life, for instance in simple counting or in monetary transactions. The term typically refers to large positive integers, or more generally, large positive real numbers, but it may also be used in other contexts.

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

1 Using scientific notation to handle large and small numbers
2 Large numbers in the everyday world
3 Astronomically large numbers
4 Computers and computational complexity
5 Practical Examples
6 Standardized system of writing very large numbers
7 Accuracy
- 7.1 Accuracy for very large numbers
8 Large numbers in some noncomputable sequences
9 Infinite numbers
10 Notations
11 See also

[edit] Using scientific notation to handle large and small numbers

See also: scientific notation, logarithmic scale, and orders of magnitude

Scientific notation was created to handle the wide range of values which occur in scientific study. 1.0 × 10⁹, for example, means one billion, a 1 followed by nine zeros: 1 000 000 000, and 1.0 × 10⁻⁹ means one billionth, or 0.000 000 001. Writing 10⁹ instead of nine zeros saves readers the effort and hazard of counting a long series of zeros to see how large the number is.

Adding a 0 at the end of a number multiplies it by 10: 100 is 10 times 10. In scientific notation, however, the exponent only increases by one, from 10¹ to 10².

[edit] Large numbers in the everyday world

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

the number of bits on a computer hard disk (as of 2006, typically about 10¹², 125 GB)
the number of cells in the human body (more than 10¹⁴)
the number of neuronal connections in the human brain (estimated at 10¹⁴)
Avogadro's number (i.e. the number of atoms in 12 grams of carbon-12, approximately 6.022 × 10²³)

[edit] Astronomically large numbers

Other large numbers, as regards length and time, are found in astronomy and cosmology. For example, the current Big Bang model of the Universe suggests that it is 13.7 billion years (4.3 × 10¹⁷ seconds) old, and that the observable universe is 78 billion light years across (7.4 × 10²⁶ metres), and contains about 5 × 10²² stars, organized into around 80 billion galaxies.

Combinatorial processes rapidly generate even larger numbers. The factorial function, which defines the number of permutations on a set of fixed objects, grows very rapidly with the number of objects. Stirling's formula gives a precise asymptotic expression for this rate of growth.

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.

[edit] Computers and computational complexity

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 to expect can reasonably be formulated. Also, there are certain theoretical results which show that some problems are inherently beyond the reach of complete computational solution, no matter how powerful or fast the computation; see N-body problem.

Between 1980 and 2000, hard disk sizes increased from about 10 megabytes (1 × 10⁷) to over 100 gigabytes (10¹¹ bytes). A 100 gigabyte disk could store the given 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 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 such a dictionary would require.

Still, computers can easily be programmed to start creating and displaying all possible 40-character passwords one at a time. Such a program could be left to 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. 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 displaying all 40-character passwords, but computing all 50 character passwords would outstrip the estimated computational potential of the entire universe.

Problems like this grow exponentially in the number of computations they require, and are one reason why exponentially difficult problems are called "intractable" in computer science: for even small numbers like the 40 or 50 characters described earlier, 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 are an advantage in cryptography, since any cipher-breaking technique which requires more than, say, the 10¹²⁰ operations mentioned before will never be feasible. Such ciphers must be broken by finding efficient techniques unknown to the cipher's designer. Likewise, much of the research throughout all branches of computer science focuses on finding 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 2005 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 have practical and theoretical challenges which may never be overcome.

See also: computation, computational complexity theory, algorithmic information theory, computability theory, and big O notation

[edit] Practical Examples

Googol = $1010$ (10,000,000,000)
googol = $10100$ (10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000)
googolplex = $10^{\mbox{googol}}=10^{\,\!10^{100}}=\mbox{googol}^{10^{98}}=2^{\,\!3.32*10^{100}}$ It is the number of states a system can be in that consists of $1098$ particles, each of which can be in googol states. Alternatively, it is the number of states a system can be in that consists of a googol particles, each of which can be in 10 states, or a system of 3.32 googol particles, each of which has 2 possible 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 roughly 1.6 × 10¹⁸ bits; therefore the contents can be represented by a number which is roughly $2^{1.6 \times 10^{18}}\approx 10^{4.8 \times 10^{17}}$

Compare:

$1.1^{\,\!1.1^{1.1^{1000}}} \approx 10^{10^{1.02*10^{40}}}$
$1000^{\,\!1000^{1000}}\approx 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). In comparing the magnitude of each successive exponent in the last number with $10^{\,\!10^{10}}$ , we find a difference in the magnitude of effect on the final exponent. In the number 3000.48, the final exponent, The overall magnitude of the final exponent is donated by the 2^nd exponent (1000). The 1^st exponent only adds a factor of 3 to the mix ( $1000\times 3$ ). The base number only supports a factor of 1.00016 in the final exponent ( $1000\times 3\times 1.00016=3000.48$ ). This clearly shows the importance of the highest exponent in the stack.

[edit] 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 a regular number at the top, possibly in scientific notation, e.g. $10^{\,\!10^{10^{10^{10^{4.829\times 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\times 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\times 10^6)$ is in ASCII ((10^)^183)3.12e6; a proposed simplification is 10^^183@3.12e6; the notations 10^^1@3.12e6 and 10^^0@3.12e6 are not needed, one can just write 10^3.12e6 and 3.12e6.

Thus googolplex = 10^^2@100 = 10^^3@2 = 10^^4@0.301; 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^^2@23.8 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). 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 (n) one has to take the $l o g 10$ to get a number between 1 and 10. Thusly, the number is between $10\uparrow\uparrow n$ and $10\uparrow\uparrow (n+1)$

An obvious property that is 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\times 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\times 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\times 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 Graham's number and Steinhaus' Mega and Megiston, Moser's number.

[edit] Accuracy

Note that for a number $10 n$ , one unit change in n 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 seems like extremely poor accuracy, but for such a large number it may be considered fair (a large error in a large number may be relatively small and therefore acceptable).

[edit] Accuracy for very large numbers

With extremely large numbers, the relative error may be large, yet there may still be a sense in which we want to consider the numbers as "close in magnitude". For example, consider

1010

and

109

The relative error is

$1 - \frac{10^9}{10^{10}} = 1 - \frac{1}{10} = 90\%$

a large relative error. However, we can also consider the relative error in the logarithms; in this case, the logarithms (to base 10) are 10 and 9, so the relative error in the logarithms is only 10%.

The point is that exponential functions magnify relative errors greatly – if a and b have small relative error,

10 a

and

10 b

may not have small relative error, and

$10^{10^a}$ and $10^{10^b}$

will have even larger relative error. The question then becomes: on which level of iterated logarithms do we wish to compare two numbers? There is a sense in which we may want to consider

$10^{10^{10}}$ and $10^{10^9}$

to be "close in magnitude". The relative error between these two number is large, and the relative error between their logarithms is still large; however, the relative error in their second-iterated logarithms is small:

$\log_{10}(\log_{10}(10^{10^{10}})) = 10$ and $\log_{10}(\log_{10}(10^{10^9})) = 9$

Such comparisons of iterated logarithms are common, e.g., in analytic number theory.

[edit] Large numbers in some noncomputable sequences

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⁸⁶⁵.

Some of the work by Harvey Friedman also involve sequences that grow faster than any computable function. [1]

[edit] Infinite numbers

Main article: cardinal number

See also: large cardinal, Mahlo cardinal, and totally indescribable cardinal

Although all these numbers above are very large, they are all still finite. Certain fields of mathematics define infinite and transfinite numbers. For example, aleph-null is the cardinality of the infinite set of natural numbers, and aleph-one is the next greatest cardinal number. $\mathfrak{c}$ is the cardinality of the reals. The proposition that $\mathfrak{c} = \aleph_1$ is known as the continuum hypothesis.

[edit] 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.
Jonathan Bowers' array notation allows considerably larger numbers to be represented than with Knuth's up-arrow notation.

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.

Categories: Mathematical notation | Large numbers

Large numbers

From Wikipedia, the free encyclopedia

Contents

[edit] Using scientific notation to handle large and small numbers

[edit] Large numbers in the everyday world

[edit] Astronomically large numbers

[edit] Computers and computational complexity

[edit] Practical Examples

[edit] Standardized system of writing very large numbers

[edit] Accuracy

[edit] Accuracy for very large numbers

[edit] Large numbers in some noncomputable sequences

[edit] Infinite numbers

[edit] Notations

[edit] See also

Views

Navigation

interaction

Search

In other languages