Tak is a recursive mathematical function defined as
def tak( x, y, z) unless y < x z else tak( tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y) ) endend
It is often used as a benchmark for languages with optimization for recursion.
tak() vs. tarai()
Its original definition by Ikuo Takeuchi (竹内郁雄), however was as follows;
def tarai( x, y, z) unless y > x y # not z! else tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) ) endend
tarai is short for "tarai mawashi", "to pass around" in Japanese.
John McCarthy attributed this function as tak() to commemorate Takeuchi but the y somehow got turned into the z.
This is a small, but significant difference because the original version benefits significantly by lazy evaluation.
Though written in exactly the same manner as others, the Haskell code below runs much faster.
tarai :: Int -> Int -> Int -> Inttarai x y z x <= y = y otherwise = tarai(tarai (x-1) y z) (tarai (y-1) z x) (tarai (z-1) x y)
You can easily accelerate this function via memoization yet lazy evaluation still wins.
The best known way to optimize tarai is to use mutually recursive helper function as follows.
def laziest_tarai(x, y, zx, zy, zz) unless y < x y else laziest_tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(zx, zy, zz)-1, x, y) endend
def tarai(x, y, z) unless y < x y else laziest_tarai(tarai(x-1, y, z), tarai(y-1, z, x), z-1, x, y) endend
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 an additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
External links
* [http://mathworld.wolfram.com/TAKFunction.html Wolfram] * [http://www.nue.org/nue/#tak-function TAK Function]
Tak — may refer to:Linguistics * Cahn Tak Big God * Tak , the Danish word for Thank you! * Tak , the Polish word for Yes * Tak , the Dutch word for branch * Tak , the Norwegian word for Roof * Tak , the Ukrainian word meaning Yes and so . Also, it was… … Wikipedia
Tak (Funktion) — Die Tak Funktion ist eine rekursiv definierte Funktion, die folgendermaßen definiert ist: Einfacher ausgedrückt: Sie wird oft als Benchmark für Programmiersprachen verwendet, die auf Rekursion optimiert s … Deutsch Wikipedia
Fonction d'Ackermann — Dans la théorie de la récursivité, la fonction d Ackermann (aussi appelée fonction d Ackermann Péter), est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la… … Wikipédia en Français
List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie … Wikipedia
Benchmark (computing) — This article is about the use of benchmarks in computing, for other uses see benchmark. In computing, a benchmark is the act of running a computer program, a set of programs, or other operations, in order to assess the relative performance of an… … Wikipedia
tactics — /tak tiks/, n. 1. (usually used with a sing. v.) the art or science of disposing military or naval forces for battle and maneuvering them in battle. 2. (used with a pl. v.) the maneuvers themselves. 3. (used with a sing. v.) any mode of procedure … Universalium
Starships in Stargate — This is a list of starships in the Stargate franchise.Ancient starshipsThe Ancients are one of the most technologically advanced races in Stargate , and this is reflected in their starships. Duplicates of these ships are utilized by their nanite… … Wikipedia
Malay language — This article is about the language which forms the basis of standard Indonesian and Malaysian. For the different Malay variants and dialects, see Malay languages. Malay Bahasa Melayu بهاس ملايو Spoken in Malaysia (as Malaysian and local Malay)… … Wikipedia
List of Star Trek races — This is a list of sentient species and races from the fictional universe of the Star Trek media franchise. Contents A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Notes … Wikipedia
