📂Programing

Knuth's Up-Arrow Notation: Why ^ is Used for Exponentiation in Programming

Definition

Knuth’s up-arrow notation is a notation devised to represent large integers.

Addition, Multiplication, and Exponentiation

Addition $x + n$ is defined as follows:

$$ x + n = x + \underbrace{1 + \cdots + 1}_{n \text{ times}} $$

Multiplication $xn$ is defined as follows:

$$ xn = \underbrace{x + \cdots + x}_{n \text{ times}} $$

Exponentiation $x^{n}$ is defined as follows:

$$ \begin{align*} x^{n} =& x \uparrow n \\ =& \underbrace{x \cdots x}_{n \text{ times}} \end{align*} $$

Tetration and Pentation

Tetration $x \uparrow^{2} n$ is defined as follows:

$$ \begin{align*} x \uparrow^{2} n =& x \uparrow \uparrow n \\ =& \underbrace{x \uparrow \cdots \uparrow x}_{n \text{ times}} \end{align*} $$

Pentation $x \uparrow^{3} n$ is defined as follows:

$$ \begin{align*} x \uparrow^{3} n =& x \uparrow \uparrow \uparrow n \\ =& \underbrace{x \uparrow \uparrow \cdots \uparrow \uparrow x}_{n \text{ times}} \end{align*} $$

General Definition

$x \uparrow^{k} n$ is defined as follows¹:

$$ \begin{align*} x \uparrow^{k} n =& x \overbrace{\uparrow \cdots \uparrow}^{k \text{ arrows}} n \\ =& \underbrace{x \overbrace{\uparrow \cdots \uparrow}^{(k-1) \text{ arrows}} \cdots \overbrace{\uparrow \cdots \uparrow}^{(k-1) \text{ arrows}} x}_{n \text{ times}} \end{align*} $$

Explanation

The renowned Donald E. Knuth, a mathematician and computer scientist, made an absolute and unique contribution to the expression of mathematical formulas for humanity by developing $\TeX$. In 1976, he also proposed the up-arrow notation in his paper. While the definition itself may be difficult to understand due to its handling of extremely large numbers, when $k = 1$, i.e., $\uparrow = \uparrow^{1}$, it is within the comprehension of ordinary humans. In particular, the up-arrow $\uparrow$ matches exactly with $x^{n} = x \uparrow n$, which uses the caret symbol ^ in the style of x^n, making this style widespread due to the difficulty of directly inputting the up-arrow on most keyboards.

It is quite interesting to look at some programming languages and their timelines:

• In 1957, Fortran was introduced, using ** for exponentiation.
• In 1972, the C language was introduced, without an exponentiation operator and instead using the pow function from the math.h library.
• In 1976, Knuth published his paper on the up-arrow notation.
• In 1978, Knuth developed $\TeX$, which used ^ for exponentiation.
• In 1984, MATLAB was released, using ^ for exponentiation.
• In 1991, Python was introduced, using ** for exponentiation.
• In 1992, R was introduced, using ^ for exponentiation.
• In 1995, Ruby was introduced, using ** for exponentiation.
• In 1995, Java was introduced, using the pow method from the Math library.
• In 2009, Go was introduced, using the pow function from the math library.
• In 2012, Julia was introduced, using ^ for exponentiation.

The history of exponentiation operators in programming is divided into before and after Knuth. General-purpose languages like Fortran used ** or provided a function in a separate standard library like C, while languages for scientific computing or statistical analysis chose ^. Python is an exception, being a general-purpose language but also widely used in scientific computing.