ordinal number programming challenge

[Mark Tarver]

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

 

[Alf P. Steinbach]

* Mark Tarver:

> [off-topic]

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)
[[]]

According to the definition above, shouldn't (ord 1) be

[] [[]]

?

[snip]

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.

That's off topic in clc++, sorry.

Follow up set [comp.programming].

 

[tragomaskhalos]

#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) + "}";
}

When you get into the teens for n these strings start getting huge -
dunno what this leda thing is but with a common-or-garden string class,
all that recursive string concatenation is going to kill performance.
Tried messing about in VC++ using ostringstream instead but it just
made it worse.
This is probably a job for a special-purpose string concatenator
(Wilson's "Imperfect C++" has one for example if I remember rightly),
it'd be interesting to see what difference that would make.

 

[Markus Schoder]

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."

A program that "prints the result without actually computing it". Care
to explain what that is supposed to mean? If a program prints a result
it has by definition computed it.

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.

This is not a well-defined challenge. It is totally dependent on what I
choose to represent an ordinal number internally. Qi seems to be one of
these functional languages so the internal representation is probably a
nested list. Now if I choose to represent the n-th ordinal number by
the integer value n the ord function becomes trivial and all the work
is done in the print function.

 

[Richard Herring]

Mark Tarver wrote: [...]

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."

A program that "prints the result without actually computing it". Care
to explain what that is supposed to mean? If a program prints a result
it has by definition computed it.

Just a guess here: maybe he used template magic, so the _compiler_
computed it before the program ever ran?