Definitions

mathematical function

Tak (function)

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

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

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

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

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

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

Search another word or see mathematical functionon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;