In mathematics , the arrow notation is a method that Donald Ervin Knuth developed in 1976 to write very large numbers. It is closely related to the Ackermann function . The idea is based on repeated exponentiation, just as exponentiation is repeated multiplication and multiplication is repeated addition.
introduction
The multiplication of a natural number can be defined as repeated addition :
For example:
A natural number as an exponent can be defined as repeated multiplication:
For example:
This inspired Knuth to define a "double arrow" operator for repeated exponents:
For example:
This operator is right-associative , which means it is evaluated from right to left.
According to this definition is
-
(Writing out this number in full would take up about 1.37 terabytes of storage space, namely bits)
- etc.
This already leads to some very large numbers, but Knuth expanded his notation even further. He introduced a "triple arrow operator" to represent repeated use of the "double arrow":
followed by a "quadruple arrow operator":
and so on. The general rule is that a -fold arrow operator becomes a -fold repetition of a -fold arrow operator:
Examples:
notation
In expressions such as , the exponent is usually written superscript in relation to the base . However, many environments - for example programming languages and plain text such as e-mail - do not allow such two-dimensional layouts. The notation was used here . The arrow should be read as 'increasing the exponent'. If the environment does not allow an arrow, the circumflex ^ is used instead .
The superscript spelling does not lend itself to a generalization. That is why Knuth chose the arrow notation, which can be written in one line instead.
In some programming languages the ^ character is used for another operator, for example in Python for XOR . Here ** is sometimes used as an alternative to , as is also the case in the Very High Speed Integrated Circuit Hardware Description Language (VHDL) and Fortran . The repeated spelling is also used here, which is intended to mean repeated use of the individual operator. So it would be possible to use *** as an equivalent to the double arrow , but this is not common.
definition
The arrow notation is formally defined by
for all natural numbers for which applies .
means here adjacent arrows (e.g. ).
All arrow operators (normal exponent notation is considered here ) are right-associative operators , i.e. if there are several operators, the expression is evaluated from right to left. For example, in general:, not ; for example is not
There is a good reason for this legal associativity. Evaluating from left to right would do the same as , so that would not result in a new operator. See also potency tower .
The definition can be extended to a few whole numbers . So you can, for example , and set. However, caution is required when choosing the initial condition for , because then (unlike for larger ones ): and .
See also
literature
- Donald E. Knuth: Coping With Finiteness . In: Science . tape 194 , no. 4271 , December 1976, p. 1235-1236 .
- Guido Walz (Red.): Arrow notation . In: Lexicon of Mathematics . 4. Moo to Sch. Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-0436-3 .