Knuth up-arrow notation

Question

I have implemented Knuth up-arrow notation in Python:

from functools import lru_cache


@lru_cache
def kuan(a, b, arrows):
    if arrows == 1:
        return a ** b
    res = a

    for i in range(b):
        res = kuan(a, res, arrows - 1)
    return res

This can calculate kuan(3, 3, 1) pretty quickly. But it slows down for kuan(3, 3, 2). Any suggestions for improving the performance?

Answer 1

There is not much code to review here, but some titbits can be mentioned

Style

• The modern way is to use cache over lru_cache unless you need a cache of a very specific size. For one-off imports I always include the package, however I've seen different opinions on this. Especially for standard libraries
• Include typing hints
• Include a docstring explaining what your code does.
• Include a if __name__ == "__main__" guard if you want to run more examples.
• Better name. It took me far to long to understand that kuan = Knuth's up arrow notation. You are not paid by the number of characters you write; feel free to be a bit verbose.

Implementation

I have no idea what implementation you are using? Looking at Wikipedia it gives me this

$$ a\uparrow^n b= \begin{cases} a^b, & \text{if }n=1; \\ 1, & \text{if }n>1\text{ and }b=0; \\ a\uparrow^{n-1}(a\uparrow^{n}(b-1)), & \text{otherwise } \end{cases} $$

Which, when implemented correctly runs in milliseconds.

import functools


@functools.cache
def arrow(a: int, b: int, arrows: int) -> int:
    """Evaluates numbers using Knuth's up-arrow notation

    Source: http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation)

    arrow(2, 3, 1)
        = 2 * 2 * 2
        = 8

    arrow(2, 3, 2)
        = arrow(2, arrow(2, 2, 1), 1)
        = arrow(2, 4, 1)
        = 2 * 2 * 2 * 2
        = 2 ^ 4
        = 16

    arrow(2, 3, 3)
        = arrow(2, arrow(2, 2, 2), 2)
        = arrow(2, arrow(2, arrow(2, 1, 1), 1), 2)
        = arrow(2, arrow(2, 2, 1), 2)
        = arrow(2, 2 * 2, 2)
        = arrow(2, 4, 2)
        = arrow(2, arrow(2, arrow(2, 2, 1), 1), 1)
        = arrow(2, arrow(2, 4, 1), 1)
        = arrow(2, 2 * 2 * 2 * 2, 1)
        = arrow(2, 16, 1)
        = 2 * ... * 2 (16 times)
        = 2 ^ 16
        = 65536

    Example:
        >>> arrow_notation(2, 3, 1)
        8
        >>> arrow_notation(2, 3, 2)
        16
        >>> arrow_notation(2, 3, 3)
        65536
        >>> arrow_notation(3, 2, 3)
        7625597484987
    """
    if arrows == 1 or b == 0:
        return a ** b
    return arrow(
        a=a,
        b=arrow(a, b - 1, arrows),
        arrows=arrows - 1,
    )


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    # print(arrow_notation(3, 2, 3))

Answer 2

When arrows==1, you're using a different approach, so saying that it's quick in that case doesn't help. You want to test against a larger arrow value. Since k(3,3,2) is slowing down, that means we need to decrease a and/or b. But looking at your approach, you seem to have an extra exponentiation. We should have:

a ^n 1 == a ^(n-1) ( a ^n 0 ) == a ^(n-1) 1 == ... == a ^ 1 == a
# and
a ^n b
== a ^(n-1) a^n (b-1)
...
== a ^(n-1) a ^(n-1) ... a ^(n-1) a ^n 0 # a occurs b+1 times
== a ^(n-1) a ^(n-1) ... a ^(n-1) 1 # a occurs b times
== a ^(n-1) a ^(n-1) ... a # a occurs b times

But you have

kuan(a,1,arrows) == kuan(a,a,arrows-1) # can get big
# and
kuan(a,b,arrows)
== kuan(a,kuan(a,kuan(a,...,kuan(a,a,arrows-1)...,arrows-1),arrows-1),arrows-1)
# kuan occurs b times, a occurs b+1 times

This is easily fixed by using range(b-1) (or range(1,b) as N3buchadnezzar suggested). Also note that a common convention in Python is that ignorable variables such as i are often named _ instead. This helps the coder realize that it's not a mistake that i doesn't appear in the loop.