en>Frietjes: cleanup (wikitables, html markup, layout, etc.)

2013-10-07T21:39:05Z

cleanup (wikitables, html markup, layout, etc.)

← Older revision		Revision as of 23:39, 7 October 2013
Line 1:		Line 1:
	~~Hello and welcome~~. ~~My name~~ is ~~Numbers Wunder~~. ~~To collect cash~~ is ~~a factor that I~~'~~m totally addicted~~ to. ~~Years~~ in the ~~past we moved~~ to ~~North Dakota. For many years he's been operating~~ as ~~a receptionist~~.<br><br>~~Look into my site~~: ~~at home std test~~ ([http://www.~~january-yjm~~.~~com~~/xe/~~index.php?mid=video&document_srl=182582 more tips here~~])		In [[computer science]], the '''Tak function''' is a [[Recursion (computer science)\|recursive function]], named after [[Ikuo Takeuchi]] (竹内郁雄). It is defined as follows:

			<math>\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}
			</math>

			<pre>
			def tak( x, y, z)
			if y < x
			tak(
			tak(x-1, y, z),
			tak(y-1, z, x),
			tak(z-1, x, y)
			)
			else
			z
			end
			end
			</pre>

			This function is often used as a [[benchmark (computing)\|benchmark]] for languages with optimization for [[recursion]].<ref>
			{{cite journal \| author=Peter Coffee\| title=Tak test stands the test of time \| journal=PC Week\| year=1996 \| volume=13 \|issue=39 }}
			</ref><ref>
			[http://buildingblocksjava.com/recursive-methods/ "Recursive Methods"]
			by Elliotte Rusty Harold
			</ref>

			==tak() vs. tarai()==
			The original definition by Takeuchi was as follows:

			<pre>
			def tarai( x, y, z)
			if y < x
			tarai(
			tarai(x-1, y, z),
			tarai(y-1, z, x),
			tarai(z-1, x, y)
			)
			else
			y # not z!
			end
			end
			</pre>

			tarai is short for ''tarai mawashi'', "to pass around" 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 \| year=1979 \| issue=3 \| month=December \| pages=6–8 \| doi=10.1145/1411829.1411833}}
			</ref>

			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 by [[lazy evaluation]].
			Though written in exactly the same manner as others, the [[Haskell (programming language)\|Haskell]] code below runs much faster.

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

			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.

			<pre>
			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
			</pre>

			Here is an efficient implementation of tarai() in C:
			<source lang="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;
			}
			</source>
			Note the additional check for (x <= y) before z (the third argument) is evaluated, avoiding unnecessary recursive evaluation.

			==References==
			{{Reflist}}

			==External links==
			*{{mathworld\|title=TAK Function\|urlname=TAKFunction}}
			*[http://www.nue.org/nue/#tak-function TAK Function]

			[[Category:Functions and mappings]]
			[[Category:Special functions]]

130.101.8.66 at 14:19, 26 June 2012

2012-06-26T14:19:44Z

New page

Hello and welcome. My name is Numbers Wunder. To collect cash is a factor that I'm totally addicted to. Years in the past we moved to North Dakota. For many years he's been operating as a receptionist.<br><br>Look into my site: at home std test ([http://www.january-yjm.com/xe/index.php?mid=video&document_srl=182582 more tips here])

ICE table - Revision history

en>Frietjes: cleanup (wikitables, html markup, layout, etc.)

130.101.8.66 at 14:19, 26 June 2012