エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

ラムダ計算と無限ラムダ多項式(18)

たらい回し関数の調査

たらい回し関数は変数を使わない例には使えそうにないですが、調査を継続します。「wikipedia:竹内関数」に書かれている高速化をやってみます。C# で書いた以下のプログラムについて考えます。

        public static string Test()
        {
            int count = 0;
            int tarai(int x, int y, int z)
            {
                count++;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y));
                }
            }
            return $"{tarai(12, 6, 0)}, count = {count}";
        }

普通に  \mathrm{tarai}(12, 6, 0) を実行すると結果は以下のようになります。

12, count = 12604861

呼ばれている回数は 12604861 回となります。

遅延評価

 x \le y のときは  z を計算する必要はないので、 zクロージャー化すると呼び出し回数を減らすことができます。

        public static string Test()
        {
            int count = 0;
            int tarai(int x, int y, Func<int> zf)
            {
                count++;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    return tarai(tarai(x - 1, y, zf), tarai(y - 1, zf(), () => x), () => tarai(zf() - 1, x, () => y));
                }
            }
            return $"{tarai(12, 6, () => 0)}, count = {count}";
        }

結果

12, count = 109

呼び出し回数は 109 回になりました。

メモ化

Dictionary に  (x, y, z) の組を保存し、同じ組に対しては一度しか計算をしないようにします。

        public static string Test()
        {
            Dictionary<(int, int, int), int> dic = new Dictionary<(int, int, int), int>();
            int count = 0;
            int tarai(int x, int y, int z)
            {
                count++;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    if (dic.ContainsKey((x, y, z)))
                    {
                        return dic[(x, y, z)];
                    }
                    else
                    {
                        int val = tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y));
                        dic[(x, y, z)] = val;
                        return val;
                    }
                }
            }
            return $"{tarai(12, 6, 0)}, count = {count}";
        }

結果

12, count = 449

呼び出し回数は 449 回になりました。