Tak (function)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 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 . It is defined as follows: \tau (x,y,z) = \begin{cases} \tau (\tau (x-1,y,z) ,\tau (y-1,z,x) ,\tau (z-1,x,y) ) & \text{if } y def tak(x: int, y: int, z: int) -> int: if y This function is often used as a benchmark for languages with optimization for recursion.

In computer science, the Tak function is a recursive function, named after . It is defined as follows: \tau (x,y,z) = \begin{cases} \tau (\tau (x-1,y,z) ,\tau (y-1,z,x) ,\tau (z-1,x,y) ) & \text{if } y def tak(x: int, y: int, z: int) -> int: if y This function is often used as a benchmark for languages with optimization for recursion.

tak() vs. tarai()

The original definition by Takeuchi was as follows: def tarai(x: int, y: int, z: int) -> int: if y tarai is short for in Japanese. John McCarthy named this function tak() after Takeuchi. 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 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 int: if not 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 Note the additional check for ( x ) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.

References

External links

TAK Function

Text derived from https://en.wikipedia.org/w/index.php?oldid=1301932557 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.