4
\$\begingroup\$

Grade 0: ++

This is so low that it is boring; the operation of grade 0 is incrementing or counting up, for example:

5++ -> 6
8++ -> 9

Grade 1: +

Addition is repeated incrementing:

4 + 3 -> 4++ ++ ++ -> 7
2 + 2 -> 2++ ++ -> 4

Grade 2: *

Multiplication is repeated addition:

3 * 4 -> 3 + 3 + 3 + 3 -> 12
5 * 2 -> 5 + 5 -> 10

...

I may go on but you understand that each operation of grade n + 1 is just a repetition of the operation of grade n, and that something like:

operation_of_order_100(4, 3)

is going to be unimaginably big, so big that it would be impossible to write it as a tower of exponents (exponentiation is a mere grade 3).

Even if computing an operation of order bigger than 5 is pratically impossible, I have gone through the mental exercise of writing a programme that raises the level of a given function and generates functions of a given grade, and I ask you for suggestions:

def increase_order(op):
    def increased(a, b):
        start_a = a
        for _ in range(b-1):
            a = op(a,start_a)
            #print(a)
        return a
    return increased

def add(a, b):
    return a + b

mul = increase_order(add)

assert mul(3,5) == 15
assert mul(7,3) == 21

exp = increase_order(mul)

assert exp(3,2) == 9
assert exp(7,2) == 49

tetract = increase_order(exp)

assert tetract(7,2) == 823543 # 7**7
assert tetract(4,3) == 4294967296 # 4**4**4

pentation = increase_order(tetract)

# print(pentation(4, 2)) :: Very big already

def op_of_order(order, start=add):
    for _ in range(order-1):
        start = increase_order(start)
    return start

BEAST_OPERATION = op_of_order(10**5)
# BEAST_OPERATION(2, 3) :: unimaginably big
\$\endgroup\$
2
  • \$\begingroup\$ How does grade zero fit into what you've done (why not add = increase_order(incr))? \$\endgroup\$
    – jonrsharpe
    May 20, 2015 at 21:06
  • \$\begingroup\$ @jonrsharpe that special case does not work, increment is abnormal because it only takes one argument, I think I would have needed to special case it \$\endgroup\$
    – Caridorc
    May 20, 2015 at 21:09

1 Answer 1

2
\$\begingroup\$

Since this is tagged "functional-programming" I decided to take the functional approach. However, take note that Python isn't necessarily a "functional language," so it's not going to be as efficient as the iterative approach you were using. However, it looks like you're doing this from a theoretical standpoint, so you may find this interesting.

import functools

def iterate(f, x, n):
    """ Applies f n times to x. """
    if n == 0:
        return x
    else:
        return f(iterate(f, x, n - 1))

def iterate_for(f, x, n):
    """ Applies f n times to x, without recursion. """
    for _ in range(n):
        x = f(x)
    return x

def increase_order(f):
    return lambda x, n: iterate(functools.partial(f, x), x, n - 1)

def op_of_order(f, order):
    return iterate(increase_order, f, order)

def test():
    add = lambda x, y: x + y

    mul = increase_order(add)
    assert mul(3,5) == 15
    assert mul(7,3) == 21

    exp = increase_order(mul)
    assert exp(3,2) == 9
    assert exp(7,2) == 49

    tetract = op_of_order(add, 3)
    assert tetract(5,2) == 3125
    #assert tetract(7,2) == 823543
    #assert tetract(4,3) == 4294967296

if __name__ == "__main__":
    test()

The biggest change here was the abstraction of the loop you have in both increase_order and op_of_order into a function called iterate, inspired by Haskell's iterate function. I've provided both a recursive and non-recursive version for understanding and efficiency (Python has a no tail-call optimization) during testing.

In my opinion, both increase_order and op_of_order are much clearer when written this way, making it easier to see just what both functions actually do.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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