Getting Started, Documentation, Tips & Tricks

A friendly contest - sort of :-)

Possibly some of you are familiar with McCarthy's "91 function" and Takeuchi's function - Gabriel [1985] had used several variants of the latter in checking the performance of Lisp systems.

To be sure, neither of these functions is of any practical importance; yet, both functions are quite instructive and make excellent examples for exploring recursion. So, I'd be interested to know - in terms of performance - how much we have progressed in the last 25+ years. The only rule of this amicable contest is that you do it on an SGI box. Otherwise, use any language you are most familiar with [whether compiled or interpreted]. Just state your timings and environment. However, for better comparison, if you try Takeuchi, call it with (18,12,6) - the result should be 7.

_________________
For aliens we're aliens.
using C under Cygwin on a i3-2100

Code:
[10:35][blahblehblih]$ ./oskar.exe 99 18 12 6
mc91: 91
timespent: 0.000000

tarai: 18
timespent: 0.000000


is tarai wrong? coz it wont spit 7 :(

_________________
:Octane: (Sakura) :O2: (Sasuke) :1600SW: (Naruto) ... lil Jesse! (O2 laptop)
“Imagination is more important than knowledge.“ – A. Einstein
oh! sorry oskar, i miss to read the rule, should only be in SGI.. later ill try on my O2 and Octane ;)

_________________
:Octane: (Sakura) :O2: (Sasuke) :1600SW: (Naruto) ... lil Jesse! (O2 laptop)
“Imagination is more important than knowledge.“ – A. Einstein
geo wrote:
is tarai wrong? coz it wont spit 7 :(

Thanks for trying! Don't know what "tarai" in your experiment is, but I do have a possible explanation why it didn't spit out 7.

Takeuchi's *original* function is:

Code:
t(x,y,z) = if x <= y then y
else t(t(x - 1,y,z), t(y - 1,z,x), t(z - 1,x,y))

But here is an example of even big minds erring. When the Computer Science Department at Stanford University obtained the first couple of Xerox Dolphins, John McCarthy and Richard Gabriel wanted to benchmark the machines. John tried to remember the Takeuchi function - but he misremembered it, like this:

Code:
g( x,y,z) = if x <= y then z
else g(g(x - 1,y,z), g(y - 1,z,x), g(z - 1,x,y))


This subtle lapse wasn't discovered until much later, but by then [the second version, dubbed TAK in Gabriel's 1985 book] had already become one of the standards for testing LISP systems - so it stuck...

Can you please try again (18,12,6) with the second version?

_________________
For aliens we're aliens.
hi oskar :)

Oskar45 wrote:
Thanks for trying! Don't know what "tarai" in your experiment


Quote:
tarai is short for tarai mawashi, "to pass around" in Japanese.
John McCarthy named this function tak() after Takeuchi.[3]
;)

hmm after changing the y to z, i got this:

Code:
[13:51][blah]$ cc oskar.c -o oskar
[13:51][blah]$ ./oskar.exe 99 18 12 6
mc91: 91
timespent: 0.000000

tarai: 6
timespent: 0.000000

now its 6 hehe near to 7 already

_________________
:Octane: (Sakura) :O2: (Sasuke) :1600SW: (Naruto) ... lil Jesse! (O2 laptop)
“Imagination is more important than knowledge.“ – A. Einstein
geo wrote:
Code:
tarai: 6
timespent: 0.000000

now its 6 hehe near to 7 already
Curious incidence? Upon (18,12,6), your first trial returned 18, your second 6 - the first and third argument, respectively...

And considering your timespent, you must have boxes working like hell:-)

_________________
For aliens we're aliens.
Well I did it with two different implementations of the tarai function that I dl'ed from the Internet, and they both give me 18 as the answer too: :shock:

Code:
#include <iostream>
#include <cstdlib>

int tarai(int x, int y, int z);

int main(int argc, char * argv[])
{
int myInt = 0;
int int1 = atoi(argv[1]);
int int2 = atoi(argv[2]);
int int3 = atoi(argv[3]);
myInt = tarai(int1, int2, int3);

std::cout << int1 << std::endl;
std::cout << int2 << std::endl;
std::cout << int3 << std::endl;

std::cout << myInt << std::endl;
return 0;
}

/*
int tarai(int x, int y, int z)
{
while (x > y)
{
int oldx = x, oldy = y;
x = tarai(x - 1, y, z);
y = tarai(y - 1, z, oldx);
if (x <= y) break;
z = tarai(z - 1, oldx, oldy);
}
return y;
}
*/

int tarai(int x, int y, int z)
{
if (x <= y) {
return y;
}
else {
return tarai(tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y));
}
}

_________________
Project:
Movin' on up, toooo the east side
Plan:
World domination! Or something...
Oskar45 wrote:
Curious incidence? Upon (18,12,6), your first trial returned 18, your second 6 - the first and third argument, respectively..
i just got the code from wiki hehe maybe its wrong?

Oskar45 wrote:
And considering your timespent, you must have boxes working like hell:-)
hehe did i mention this machine can finish an infinite loop within a sec :shock: :mrgreen:

vishnu wrote:
Well I did it with two different implementations of the tarai function that I dl'ed from the Internet, and they both give me 18 as the answer too:
hi vish! hehe strange right? but i try your 2nd implementation and using oskars comment on using z than y, here is my output:

Code:
[13:14][blah]$ cc oskar.c -o oskar.exe
[13:16][blah]$ ./oskar.exe 98 18 12 6
mc91: 91
timespent: 0.000000

tarai_ret_y: 18
timespent: 0.000000

tarai_ret_z: 6
timespent: 0.000000

tarai_vishnu_ret_y: 18
timespent: 0.094000

tarai_vishnu_ret_z: 7
timespent: 0.000000


i guess your 2nd implementation is the best but need to change y to z.. but why? :)

_________________
:Octane: (Sakura) :O2: (Sasuke) :1600SW: (Naruto) ... lil Jesse! (O2 laptop)
“Imagination is more important than knowledge.“ – A. Einstein
geo wrote:
vishnu wrote:
Well I did it with two different implementations of the tarai function that I dl'ed from the Internet, and they both give me 18 as the answer too:
hi vish! hehe strange right? but i try your 2nd implementation and using oskars comment on using z than y, here is my output:

Code:
[13:14][blah]$ cc oskar.c -o oskar.exe
[13:16][blah]$ ./oskar.exe 98 18 12 6
mc91: 91
timespent: 0.000000

tarai_ret_y: 18
timespent: 0.000000

tarai_ret_z: 6
timespent: 0.000000

tarai_vishnu_ret_y: 18
timespent: 0.094000

tarai_vishnu_ret_z: 7
timespent: 0.000000


i guess your 2nd implementation is the best but need to change y to z.. but why? :)


Well that little trick gives Oskar's "right answer" but who knows why? It's too late in the evening for me to look at the math tonight... :lol:

_________________
Project:
Movin' on up, toooo the east side
Plan:
World domination! Or something...
vishnu wrote:
It's too late in the evening for me to look at the math tonight...
hehe good night then! let's just wait for oskar then ;)

_________________
:Octane: (Sakura) :O2: (Sasuke) :1600SW: (Naruto) ... lil Jesse! (O2 laptop)
“Imagination is more important than knowledge.“ – A. Einstein
@geo & vishnu: Bingo, gentlemen :-) But, really, there's no trick involved here. True, the original (recursive) 1978 Takeuchi function t(x,y,z) has "if x <= y then y else ...". However, by the hint I'd already given you above, when John McCarthy wanted to test newly arrived Xerox machines, he remembered the function wrongly and had "if x <=y then z else ..." instead [yes, even giants are not infallible]; this version stuck and Richard Gabriel in his 1985 book, "Performance and Evaluation of Lisp Systems" used it - as TAK - to benchmark 130+ configurations. Indeed, Donald Knuth, in his 1991 paper, "Textbook Examples of Recursion", after discussions of the "91 function" and the original Takeuchi, also elaborates on a class of recursive functions he calls "False Takeuchi Functions", of which McCarthy's/Gabriel's version certainly is a member. And, IIRC, Ilan Vardi, in his 1991 book, "Computational Recreations in Mathematica" discusses the running time of TAK as well.

Anyway, could you please supply some information regarding your SGI box/compiler etc. for comparison? Thanx.

_________________
For aliens we're aliens.
But then since the code geo and I tried uses the right algorithm shouldn't it be producing the right answer? :shock:

_________________
Project:
Movin' on up, toooo the east side
Plan:
World domination! Or something...
vishnu wrote:
But then since the code geo and I tried uses the right algorithm shouldn't it be producing the right answer? :shock:
Nope, the then part matters [since it can be considered as a function e(x,y,z), there are infinitely many right answers - although infinitely many will loop forever as well]... ;)

_________________
For aliens we're aliens.
Oskar45 wrote:
Anyway, could you please supply some information regarding your SGI box/compiler etc. for comparison? Thanx.

Octane 360Mhz R12k
MIPSPro 7.4
Code:
mc91: 91
timespent: 0.000000

tarai_ret_y: 18
timespent: 0.000000

tarai_ret_z: 6
timespent: 0.000000

tarai_vishnu_ret_y: 18
timespent: 1.100000

tarai_vishnu_ret_z: 7
timespent: 0.000000


O2 300Mhz R5k
MIPSPro 7.30
Code:
mc91: 91
timespent: 0.000000

tarai_ret_y: 18
timespent: 0.000000

tarai_ret_z: 6
timespent: 0.000000

tarai_vishnu_ret_y: 18
timespent: 1.400000

tarai_vishnu_ret_z: 7
timespent: 0.000000

_________________
:Octane: (Sakura) :O2: (Sasuke) :1600SW: (Naruto) ... lil Jesse! (O2 laptop)
“Imagination is more important than knowledge.“ – A. Einstein
MIPSPro 7.4 on a 600MHz Octane2 running IRIX 6.5.30:

Code:
System call summary:
Average     Total
Name           #Calls  Time(ms)  Time(ms)
-----------------------------------------
execve             13      0.04      0.53
write               5      0.04      0.18
stat                3      0.05      0.15
sigreturn           1      0.01      0.01
syssgi              1      0.00      0.00
prctl               1      0.00      0.00
exit                1      0.00      0.00

_________________
Project:
Movin' on up, toooo the east side
Plan:
World domination! Or something...