Tak (function): Difference between revisions

Content deleted Content added

Inline

Latest revision as of 21:12, 24 October 2024

In computer science, the Tak function is a recursive function, named after Ikuo Takeuchi [ja]. 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<x\\z&{\text{otherwise}}\end{cases}}$

def tak(x, y, z):
    if y < x:
        return tak( 
            tak(x-1, y, z),
            tak(y-1, z, x),
            tak(z-1, x, y)
        )
    else:
        return z

This function is often used as a benchmark for languages with optimization for recursion.^[1]^[2]^[3]^[4]

tak() vs. tarai()

The original definition by Takeuchi was as follows:

def tarai(x, y, z):
    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, y, zx, zy, zz):
    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, y, z):
    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

^ Peter Coffee (1996). "Tak test stands the test of time". PC Week. 13 (39).
^ "Recursive Methods" by Elliotte Rusty Harold
^ 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

[1] Peter Coffee (1996). "Tak test stands the test of time". PC Week. 13 (39).

[2] "Recursive Methods" by Elliotte Rusty Harold

[acornuser198606-3] Johnson-Davies, David (June 1986). "Six of the Best Against the Clock". Acorn User. pp. 179, 181–182. Retrieved 28 October 2020.

[acornuser198611-4] Johnson-Davies, David (November 1986). "Testing the Tak". Acorn User. pp. 197, 199. Retrieved 28 October 2020.

[5] John McCarthy (December 1979). "An Interesting LISP Function". ACM Lisp Bulletin (3): 6–8. doi:10.1145/1411829.1411833. S2CID 31639459.

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
+{{Short description|Recursive function}}
-In [[computer science]], the '''Tak function''' is a [[Recursion (computer science)|recursive function]], named after [[Ikuo Takeuchi]] (竹内郁雄). It is defined as follows:
+In [[computer science]], the '''Tak function''' is a [[Recursion (computer science)|recursive function]], named after {{Interlanguage link|Ikuo Takeuchi|ja|竹内郁雄|WD=}}. It is defined as follows:
-<math>\tau (x,y,z) = \begin{cases}
+<math display="block">
+\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 < x \\
  z & \text{otherwise}
@@ Line 7: / Line 9: @@
  </math>
-<syntaxhighlight lang="ruby">
+<syntaxhighlight lang="python">
-def tak( x, y, z)
+def tak(x, y, z):
-  if y < x
+    if y < x:
-    tak(
+        return tak(
-         tak(x-1, y, z),
+            tak(x-1, y, z),
-         tak(y-1, z, x),
+            tak(y-1, z, x),
-         tak(z-1, x, y)
+            tak(z-1, x, y)
-       )
+        )
-  else
+    else:
-    z
+        return z
-  end
-end
 </syntaxhighlight>
@@ Line 26: / Line 26: @@
 [http://buildingblocksjava.com/recursive-methods/ "Recursive Methods"]
 by Elliotte Rusty Harold
-</ref><ref name="acornuser198606">{{ cite news | url=https://archive.org/details/AcornUser047-Jun86/page/n180/mode/1up | title=Six of the Best Against the Clock | work=Acorn User | date=June 1986 | accessdate=28 October 2020 | last1=Johnson-Davies | first1=David | pages=179,181-182 }}</ref><ref name="acornuser198611">{{ cite news | url=https://archive.org/details/AcornUser052-Nov86/page/n198/mode/1up | title=Testing the Tak | work=Acorn User | date=November 1986 | accessdate=28 October 2020 | last1=Johnson-Davies | first1=David | pages=197,199 }}</ref>
+</ref><ref name="acornuser198606">{{ cite news | url=https://archive.org/details/AcornUser047-Jun86/page/n180/mode/1up | title=Six of the Best Against the Clock | work=Acorn User | date=June 1986 | accessdate=28 October 2020 | last1=Johnson-Davies | first1=David | pages=179, 181–182 }}</ref><ref name="acornuser198611">{{ cite news | url=https://archive.org/details/AcornUser052-Nov86/page/n198/mode/1up | title=Testing the Tak | work=Acorn User | date=November 1986 | accessdate=28 October 2020 | last1=Johnson-Davies | first1=David | pages=197, 199 }}</ref>
 ==tak() vs. tarai()==
+{{more sources|section|date=September 2023}}
 The original definition by Takeuchi was as follows:
-<syntaxhighlight lang="ruby">
+<syntaxhighlight lang="python">
-def tarai( x, y, z)
+def tarai(x, y, z):
-  if y < x
+    if y < x:
-    tarai(
+        return tarai(
-         tarai(x-1, y, z),
+            tarai(x-1, y, z),
-         tarai(y-1, z, x),
+            tarai(y-1, z, x),
-         tarai(z-1, x, y)
+            tarai(z-1, x, y)
-       )
+        )
-  else
+    else:
-    y          # not z!
+        return y  # not z!
-  end
-end
 </syntaxhighlight>
-tarai is short for たらい回し ''tarai mawashi'', "to pass around" in Japanese.
+tarai is short for {{Nihongo krt|"to pass around"|たらい回し|tarai mawashi}} in Japanese.
 [[John McCarthy (computer scientist)|John McCarthy]] named this function tak() after Takeuchi.<ref>
-{{cite journal | author=John McCarthy | title=An Interesting LISP Function  | journal=ACM Lisp Bulletin |date=December 1979 | issue=3  | pages=6–8 | doi=10.1145/1411829.1411833}}
+{{cite journal | author=John McCarthy | title=An Interesting LISP Function  | journal=ACM Lisp Bulletin |date=December 1979 | issue=3  | pages=6–8 | doi=10.1145/1411829.1411833| s2cid=31639459 }}
 </ref>
-However, in certain later references, the y somehow got turned into the z.
+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]].
-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 (programming language)|Haskell]] code below runs much faster.
@@ Line 59: / Line 59: @@
 tarai x y z
     | x <= y    = y
-    | otherwise = tarai(tarai (x-1) y z)
+    | otherwise = tarai (tarai (x-1) y z)
-                       (tarai (y-1) z x)
+                        (tarai (y-1) z x)
-                       (tarai (z-1) x y)
+                        (tarai (z-1) x y)
 </syntaxhighlight>
-You can easily accelerate this function via [[memoization]] yet lazy evaluation still wins.
+One 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.
+The best known way to optimize tarai is to use a mutually recursive helper function as follows.
 <syntaxhighlight lang="ruby">
-def laziest_tarai(x, y, zx, zy, zz)
+def laziest_tarai(x, y, zx, zy, zz):
-  unless y < x
+    if not y < x:
-    y
+        return y
-  else
+    else:
+        return laziest_tarai(
-    laziest_tarai(tarai(x-1, y, z),
-                  tarai(y-1, z, x),
+            tarai(x-1, y, z),
-                  tarai(zx, zy, zz)-1, x, y)
+            tarai(y-1, z, x),
+            tarai(zx, zy, zz)-1, x, y)
-  end
-end
-def tarai(x, y, z)
+def tarai(x, y, z):
-  unless y < x
+    if not y < x:
-    y
+        return y
-  else
+    else:
+        return laziest_tarai(
-    laziest_tarai(tarai(x-1, y, z),
-                  tarai(y-1, z, x),
+            tarai(x-1, y, z),
-                  z-1, x, y)
+            tarai(y-1, z, x),
+            z-1, x, y)
-  end
-end
 </syntaxhighlight>
@@ Line 104: / Line 102: @@
 }
 </syntaxhighlight>
-Note the additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
+Note the additional check for (<code>x <= y</code>) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.
 ==References==
@@ Line 114: / Line 112: @@
 {{Benchmark}}
 [[Category:Functions and mappings]]
 [[Category:Special functions]]