Tak (function)
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, the Tak function is a recursive function, named after Ikuo Takeuchi [ja]. It is defined as follows:
τ(x,y,z)={τ(τ(x−1,y,z),τ(y−1,z,x),τ(z−1,x,y))if y<xzotherwise
def tak(x: int, y: int, z: int) -> int: if y < x: return tak( tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y) ) else: return zThis function is often used as a benchmark for languages with optimization for recursion.[1][2][3][4]
tak() vs. tarai()
edit edit sourceThe original definition by Takeuchi was as follows:
def tarai(x: int, y: int, z: int) -> int: if y < x: return tarai( tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y) ) else: return y # not z!tarai is short for たらい回し (tarai mawashi, "to pass around") in Japanese.
John McCarthy named this function tak() after Takeuchi.[5]
However, in certain later references, the y somehow got turned into the z. This is a small, but significant difference because the original version benefits significantly from lazy evaluation.
Though written in exactly the same manner as others, the Haskell code below runs much faster.
tarai :: Int -> Int -> Int -> Int tarai x y z | x <= y = y | otherwise = tarai (tarai (x-1) y z) (tarai (y-1) z x) (tarai (z-1) x y)One can easily accelerate this function via memoization yet lazy evaluation still wins.
The best known way to optimize tarai is to use a mutually recursive helper function as follows.
def laziest_tarai(x: int, y: int, zx: int, zy: int, zz: int) -> int: if not y < x: return y else: return laziest_tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(zx, zy, zz)-1, x, y) def tarai(x: int, y: int, z: int) -> int: if not y < x: return y else: return laziest_tarai( tarai(x-1, y, z), tarai(y-1, z, x), z-1, x, y)Here is an efficient implementation of tarai() in C:
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; }Note the additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
References
edit edit source- ^ Peter Coffee (1996). "Tak test stands the test of time". PC Week. 13 (39).
- ^ "Recursive Methods" by Elliotte Rusty Harold Wikipedia revision 1301932557, retrieved 2026-11-18
- ^ Johnson-Davies, David (June 1986). "Six of the Best Against the Clock". Acorn User. pp. 179, 181–182. Retrieved 28 October 2020.
- ^ Johnson-Davies, David (November 1986). "Testing the Tak". Acorn User. pp. 197, 199. Retrieved 28 October 2020.
- ^ John McCarthy (December 1979). "An Interesting LISP Function". ACM Lisp Bulletin (3): 6–8. doi:10.1145/1411829.1411833. S2CID 31639459.
External links
edit edit source- Weisstein, Eric W. "TAK Function". MathWorld.
- TAK Function Archived 2007-09-12 at the Wayback Machine
- Hierarchical INTegration (HINT)
- NBench (CPU, memory)
- Adjusted Peak Performance (nuclear weapon simulation)
- AnTuTu (ARM)
- BogoMips (Linux)
- Coremark (embedded systems)
- iCOMP (index) (Intel)
- Novabench (Windows and macOS)
- Phoronix Test Suite (Linux)
- Performance Rating (AMD)
- Sysinfo & SysSpeed (Motorola 68k)
- WorldBench (Windows)
Text derived from https://en.wikipedia.org/w/index.php?oldid=1301932557 under CC BY-SA 4.0; modifications have been made.