Prompted by a post on Catalan numbers in Qilang,

I got into looking at ordinal numbers as defined by

John von Neumann - see http://en.wikipedia.org/wiki/Ordinal_numbers

0 = {}

1 = {0} = {{}}

2 = {0,1} = {{}, {{}}}

3 = {0,1,2} = {{}, {{}}, {{}, {{}}}}

The Qi (see www.lambdassociates.org) definition is

(define ord

{number --> ordinal}

0 -> []

N -> (let O (ord (- N 1)) (append O [O])))

which uses [] for {} and maps any natural number to its

ordinal representation.

(1-) (ord 0)

[]

(2-) (ord 1)

[[]]

(3-) (ord 2)

[[] [[]]]

(4-) (ord 3)

[[] [[]] [[] [[]]]]

The datatype definition of ordinal needed is

(datatype ordinal

_________

[ ] : ordinal;

O : ordinal;

______________________

(append O [O]) : ordinal;)

This makes ord type secure.

Now my friend Willi is a C++ programmer and he wrote the program

in C++. Here it is.

// cardtst.cpp - Von Neumann Numbers

// W.O. Riha - 09/05/06

// edited - 10/05/06 00:41

#include "leda.h"

string card1(int n) // auxiliary function to avoid unnecessary

recomputation

{

if (n<=1) return "O";

string s = card1(n-1);

return s + ", {" + s + "}";

}

string card(int n)

{

if (n==0) return "O";

return "{"+ card1(n) + "}";

}

int main()

{

cout << "\nVon Neumann Numbers ...\n\n";

for (;;) {

int n = read_int("\nEnter n: ");

cout << card(n)<< endl;

}

}

We found that the Qi program was much faster at computing

solutions than the C++ program. Hence Willi came back with

a counter challenge.

"I have therefore written a function in C++ which will print

the result for any n, without actually computing it. ....

For n = 3 it should produce something like {O {O} {O {O}}}

..... In C++ it is only three lines."

Well, the old dog! I wonder what his solution is?

Some challenges

1. If you're a C++ programmer can you rewrite Willi's original

program to compute faster than the original Qi program?

Ignore the time taken to print the result. Here is a result

using 2.6Ghz & 500Mb main memory.

(define test

N -> (time (do (ord N) ok!)))

(53-) (test 1000)

Real time: 0.1702448 sec.

Run time: 0.1702448 sec.

Space: 4004000 Bytes

GC: 6, GC time: 0.150216 sec.ok!

2. Can you reproduce or better Willi's secret 3 line solution?

Mark

www.lambdassociates.org