Getting Started, Documentation, Tips & Tricks

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.

using C under Cygwin on a i3-2100



is tarai wrong? coz it wont spit 7

oh! sorry oskar, i miss to read the rule, should only be in SGI.. later ill try on my O2 and Octane

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:


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:



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?

hi oskar





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


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:-)

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:

i just got the code from wiki hehe maybe its wrong?

hehe did i mention this machine can finish an infinite loop within a sec

hi vish! hehe strange right? but i try your 2nd implementation and using oskars comment on using z than y, here is my output:



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

hehe good night then! let's just wait for oskar then

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

But then since the code geo and I tried uses the right algorithm shouldn't it be producing the right answer?

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

Octane 360Mhz R12k
MIPSPro 7.4


O2 300Mhz R5k
MIPSPro 7.30

MIPSPro 7.4 on a 600MHz Octane2 running IRIX 6.5.30: