2
\$\begingroup\$

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?

\$\endgroup\$
5
  • \$\begingroup\$ You know you are trying to compute, very very large numbers right? Python is not meant for that. Nor is any language by increasing the number of arrows \$\endgroup\$ Jan 27 at 15:37
  • \$\begingroup\$ I'm trying to make a simple implementation. I do not expect it to handle super large numbers like kuan(100, 100, 100). The problem is, it is very slow for (relatively) small inputs like kuan(3, 3, 2) \$\endgroup\$
    – Bgil Midol
    Jan 27 at 15:39
  • \$\begingroup\$ That's why I posted it here. \$\endgroup\$
    – Bgil Midol
    Jan 27 at 15:43
  • 1
    \$\begingroup\$ kuan(a,b,1) uses a completely different method than higher arrows, so saying you can calculate that pretty quickly doens't help. Have you checked your validity elsewhere? By my math, your kuan(3,3,2) has about 3.3e12 digits. I wouldn't call that relatively small. You seem to be ending up with an extra exponentiation. \$\endgroup\$
    – Teepeemm
    Jan 28 at 3:45
  • \$\begingroup\$ @Teepeemm changing from for i in range(b): to for _ in range(1, b): fixes the code. Feel free to leave this as an answer =) \$\endgroup\$ Jan 28 at 8:28

2 Answers 2

5
\$\begingroup\$

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))
\$\endgroup\$
2
  • \$\begingroup\$ One problem, cache is specific to 3.9+, and I'm using 3.8. \$\endgroup\$
    – Bgil Midol
    Jan 27 at 19:51
  • \$\begingroup\$ @BgilMidol Benchmark your code on logical inputs. I am actually very unsure if cache provides any tangible / measurable benefits in the numberrange we are able to test. E.g numbers grow so quickly that for small inputs our cache might be slower. Again feel free to test this \$\endgroup\$ Jan 27 at 20:16
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.