# 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 with1

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.

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

letrecackermann m n =

matchm, nwith

|0, n -> n +1

| m,0-> ackermann(m -1)1

| m, n -> ackermann(m -1)ackermann m(n -1)

//using tail-recursionletackermann M N =

letrecacker(m, n, k)=

matchm,nwith

|0, n -> k(n +1)

| m,0-> acker((m -1),1, k)

| m, n ->

acker(m,(n -1),(funx -> acker((m -1), x, k)))

acker(M, N,(funx -> 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)