Hyperoperation via F#

When I first learned multiplication, I learned it in terms of addition.

3 * 3 = the sum of three 3s = 3 + 3 + 3

Then after exponents settled in, in terms of multiplication, I thought “hmmm, if 3*3 = 3+3+3 and 3³ = 3*3*3, what’s next?”. At the time, I envisioned “super-exponents”, 3superEx3= 3 ^ 3 ^ 3, but left it at that.

Years passed.

On a recent flight, I pulled up the FSharp-Interactive REPL to try to model this recursion. Let’s start by defining addition; for now we’ll cheat and use the built-in + operator.

let add x y =
    x + y

Well that was easy. Now we want to define multiplication in terms of addition as described above.

//e.g. mult 3 3 = 3 + 3 + 3
let mult x n =
    //initialize an array of 3's of length 3
    let seed = Array.init n (fun i -> x)
    //add each 3 to the result, start with 0
    seed |> Array.fold add 0
> mult 3 3;;
val it : int = 9

And on to exponentiation, which is defined in terms of multiplication, which is defined in terms of addition.

3³ = 3 * 3 * 3 = (3 + 3 + 3) + (3 + 3 + 3) + (3 + 3 + 3) = 27

let exp x n = 
    //e.g. initialize an array of 3s of length 3   
    let seed = Array.init n (fun i -> x)  
    //mult each 3 to the result, start with 1  
    seed |> Array.fold mult 1
> exp 3 3;;
val it : int = 27

Note that if we dial this up a bit and try larger input we’ll blow out our int.

> exp 10 10;;
val it : int = 1410065408 

The result should have been 10,000,000,000; to give us a little more room to work, let’s use modify our set of functions to use Int64. While we’re at it let’s switch F# Interactive to 64-bit, which will increase our stack space. In VS you can do this at Tools -> Options -> F# Tools -> F# Interactive -> 64-bit F# Interactive.

So our new exponentiation function is:

let exp (x:int64) (n:int64) =
   let seed = Array.init (int n) (fun i -> x)
   Array.fold mult 1L seed
> exp 10L 10L;;
val it : int64 = 10000000000L

Well hey now, this looks an awful lot like the mult function, except the fold operator has changed from add to mult, and the starting value has changed from 0 to 1, since 1 is the identity value for multiplication. Let’s hold that thought for a minute while we explore what I was calling “super-exponentiation”, and for which the proper term is tetration.

Tetration:

3 tet 3
= 3 ^ 3 ^ 3 = 3 ^ (27) 
= (3*3*3)*(3*3*3)*(3*3*3) 
  + 24 more “*(3*3*3)”s 
= (((3+3+3)+(3+3+3)+(3+3+3))
  +((3+3+3)+(3+3+3)+(3+3+3))
  +((3+3+3)+(3+3+3)+(3+3+3))) 
  + 282,429,536,478 more “((3+3+3)+(3+3+3)+(3+3+3))”s
= 7,625,597,484,987 . 

That escalated quickly. Note that exponentiation is right-associative: 3 tet 3= 3^(3 ^ 3), not (3 ^ 3) ^ 3. So we’ll use foldBack here instead of fold. And because we’re starting our fold with x, we can leave one instance of x out of the array; thus we’ll init the array with n-1 x’s.

//tetration
let tet x n =
   let seed = Array.init (int (n - 1L)) (fun i -> x)
   Array.foldBack exp seed x
tet 3L 3L;;
val it : int64 = 7625597484987L

OK! Same pattern as before, with the fold function as exp and the start value as x. Upward and onward to pentation:

let pent x n =
    let seed = Array.init (int (n-1L)) (fun i -> x)
    seed |> Array.fold tet x
> pent 3L 3L;;
System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown. 
at FSI_0013.mult(Int64 x, Int64 n) in C:\Users\cdutcher\Documents\Visual Studio 2015\Projects\Scratch\Scratch\Tetration.fsx:line 56 
at Microsoft.FSharp.Collections.ArrayModule.Fold[T,TState](FSharpFunc`2 folder, TState state, T[] array) 
at Microsoft.FSharp.Collections.ArrayModule.FoldBack[T,TState](FSharpFunc`2 folder, T[] array, TState state) 
at Microsoft.FSharp.Collections.ArrayModule.Fold[T,TState](FSharpFunc`2 folder, TState state, T[] array) 
at <StartupCode$FSI_0016>.$FSI_0016.main@()
Stopped due to error

Well. We’ve exhausted our available memory. Turns out that pentation is extremely powerful. Nonetheless, the pattern is clear, and we can combine all into one generic function that takes an extra “level” parameter, where level 0 is addition, 1 is multiplication, 2 is exponentiation, 3 is tetration, 4 is pentation, and onwards.

let rec hyper level x n = 
    let startValue =
        function
        | 0-> 0.0
        | 1-> 1.0
        | _ -> x
    match level with
    | 0 -> 
        add x n
    | _ ->
        let seed = Array.init n (fun i -> x)
        seed
        |> Array.fold (hyper(level-1)) (startValue(level - 1))

And checking some results:

> hyper 0 3L 2L;; //addition
val it : int64 = 5L
> hyper 1 3L 2L;; //multiplication
val it : int64 = 6L
> hyper 2 3L 2L;; //exponentiation
val it : int64 = 9L
> hyper 3 3L 2L;; //tetration
val it : int64 = 19683L  //3 ^ (3 ^ 2)
> hyper 3 3L 3L;; //tetration example 2
val it : int64 = 7625597484987L // 3 ^ (3 ^ 3)
> hyper 4 3L 2L;; //pentation
System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown.
at FSI_0002.hyper(Int32 l, Int64 x, Int64 n) in C:\Users\Cole\Documents\GitHub\InContactBridge\InContactBridge\InContactBridge\Tetration.fsx:line 37
at Microsoft.FSharp.Collections.ArrayModule.Fold[T,TState](FSharpFunc`2 folder, TState state, T[] array)
at Microsoft.FSharp.Collections.ArrayModule.Fold[T,TState](FSharpFunc`2 folder, TState state, T[] array)
at <StartupCode$FSI_0010>.$FSI_0010.main@()
Stopped due to error

It works!….mostly.

That memory issue really puts a damper on things, but we can refactor a bit to permit tail-recursion and avoid scaling the memory usage.

The nest function takes a function and applies it n-times to its input x.

let rec nest n f x =
    if n=0L then x
    else nest (n-1L) f (f x)

We can define addition in terms of the single-variabled succession function:

let add1 x =
    x + 1L
//0
let addn x n =
    x |> nest n add1

Working up the levels we have:

//1
let multn x n =
    x |> nest (n - 1L) (addn x)
//2
let expn x n =
    x |> nest (n - 1L) (multn x)
//3
let tet x n =
    x |> nest (n - 1L) (expn x)
//4
let pent x n =
    x |> nest (n - 1L) (tet x)
let rec hyper level x n =
    match level with
    | 0L -> addn x n
    | _ ->
        let f = hyper(level - 1L) x
        nest (n - 1L) f x

The nest function and our hyper function are very similar; the latter just defines some base cases. If we modify hyper to cover all base cases, including the succession function we have:

let rec hyper level a b =
    match level, b with
    | 0L, _ -> b + 1L
    | 1L, 0L -> a
    | 2L, 0L -> 0L
    | _ , 0L -> 1L
    | _ ->
        hyper (level - 1L) a (hyper level a (b - 1L))
> hyper 4L 3L 3L;;
val it : int = 7625597484987L

This is the proper hyperoperation function. While we’ve avoided the memory problems, this function is still extremely inefficient. Some resulting values for tetration (level=4 in our new succesion-zeroed function) are in the table below, and we know that our function ultimately starts at 0 and counts by 1 up to the result, so it should take a while for a,b> 3.

Tetration — source: Wikipedia

This tremendous growth actually makes hyperoperation very special. The function is total recursive, which, in short, means that it will definitely complete (eventually), but it is not primitive recursive. If it were primitive recursive, it could be written with a bounded for-loop, where the bound is set in advance. While other functions exist which are known to be total recursive, but not primitive recursive, they are generally derived from or closely related to the hyperoperation function. The most popular of these is Ackermann’s function:

//simple
let rec ackermann m n = 
    match m, n with
    | 0, n -> n + 1
    | m, 0 -> ackermann (m - 1) 1
    | m, n -> ackermann (m - 1) ackermann m (n - 1)
//using tail-recursion
let ackermann M N =
    let rec acker (m, n, k) =
       match m,n with
        | 0, n -> k(n + 1)
        | m, 0 -> acker ((m - 1), 1, k)
        | m, n -> 
            acker (m, (n - 1), (fun x -> acker ((m - 1), x, k)))
    acker (M, N, (fun x -> x))
//source: http://rosettacode.org/wiki/Ackermann_function

which can be built from hyperoperation:

A(m,n) = hyper(m,2,n+3)-3.

The tremendous growth in necessary recursive steps of Ackermann’s function, for increasing values of m and n, makes it very useful for testing the efficiency of a compiler’s code generation for function calls. See here and here.

I’ll sign off here, but if you’re interested in digging further check out:

Notation Systems for Hyperoperations: Knuth Up-Arrow Notation, Conway Chains

Tetration over Complex Numbers -> Extension to complex bases

Graham’s Number (<- this post is really great, as are many from WaitButWhy)