I recently ran into a tweet saying that if
** denotes exponentiation then // should denote logarithm. With this notation, for example, if we say
3**4 == 81
we would also say
81 // 3 == 4.
This runs counter to convention since
// has come to be a comment marker or a notation for integer division. I assume the original proposal was meant to be funny, or at most semi-serious, but it would have made sense had notation developed that way.
Donald Knuth’s arrow notation for hyperexponentiation works that way. An up arrow denotes repeated exponentiation and a down arrow denotes repeated logarithm.
Up arrow notation
One up arrow denotes repeated multiplication, i.e. exponentiation.
Two up arrows denote repeated exponentiation, i.e. hyperexponentiation.
Three up arrows denotes repeated applications of double arrow, etc.
Here’s how you could calculate
def hyperexp(b, k, n): if n == 0: return 1 if k == 1: return b**n return hyperexp(b, k-1, hyperexp(b, k, n-1))
This function grows shockingly quickly. The first four values of
hyperexp(2, 2, n) starting with n=1 are 2, 4, 16, and 65536. But the fifth value has over 19,000 digits.
Up arrow notation comes up sometimes, for example, in analysis of algorithms.
Down arrow notation
The downarrow notation is less common, and a little more complicated.
The logarithm of a number x base b is the number of times you’d need to multiply b by itself to get x. So if down arrow is the inverse of up arrow, down arrow is logarithm.
Now what should two down arrows represent? It should be the inverse of down up arrows. For example,
and so we should have
That means the double down arrow counts how many times you have to use up arrows to get from 4 to 65536. But notice we’re counting things. We’re assuming there are an integer number of times you can apply up arrows to define the down arrows. In general you can’t do that. What if we change 65536 to 65535 above?
So here’s where there’s a slight complication, an asymmetry between up arrow and down arrow notation. Repeated up arrows count the number of times you have to apply down arrows to get something less than or equal to the base. See MathWorld, for example.
Seems like down arrow notation might be useful in number theory where iterated logs are common. (There’s a joke that asks what sound a number theorist makes when drowning. Answer: log log log ….)
7 thoughts on “Up arrow and down arrow notation”
Why not just grab Unicode ⭡ and ⭣ for this, exactly capturing Knuth’s notation? (Okay, yes, I’m a Perl 6 programmer….)
Unicode # and Unicode # ? In my browser there’s no difference…
It’s fine in my browser (up arrow and down arrow) but that is a difficulty, yes. :)
Pet peeve, you don’t need parentheses after the “if” statement in Python. Just “if n == 0:” will do fine.
@Aaron: Old habits die hard. :)
In Perl, both 5&6,
//is the defined-or operator. Think of
||with a different slant.
Also someone already made a module for up-arrow notation in Perl 6 Math::Arrow
Brad, oh, nice! (Wanders off to try module…)