フィボナッチ数列を割と速く算出スル方法(C#)

フィボナッチ数列を求めるアルゴリズムを書くと、普通に挑むとすごい時間がかかってしまいます。（下記のFibonacciクラス）

ちょっとしたキャッシュを入れてやるだけで、n = 139までは割と素早く算出することができます。（下記のFibonacciWithCacheクラス）
139以上は、decimalがoverflowするので、それ以上はC#で普通にやると求められません。

Program.cs

namespace FibonacciOnConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            var fib = new FibonacciCUI();
            fib.Calc(new FibonacciWithCache());
        }
    }
}

FibonacciCUI.cs

using System;
using System.Diagnostics;

namespace FibonacciOnConsole
{
    public class FibonacciCUI
    {
        public void Calc(IFibonacciStrategy strategy)
        {
            ConsoleKeyInfo cki;
            Console.TreatControlCAsInput = true;
            do
            {
                Console.WriteLine("Please input fibonacci number.");
                Console.WriteLine("Press ESC key if you want to finish this console.");
                var inputtedString = Console.ReadLine();

                var inputtedNum = default(decimal);
                if (decimal.TryParse(inputtedString, out inputtedNum))
                {
                    inputtedNum = (inputtedNum >= 139) ? 139 : inputtedNum;

                    Console.WriteLine("Begin process.");
                    for (decimal i = 0; i < inputtedNum; i++)
                    {
                        var sw = new Stopwatch();
                        sw.Start();
                        var ret = strategy.Calc(i);
                        sw.Stop();
                        var ts = sw.Elapsed;
                        Console.WriteLine(string.Format("{0, 4} Fibonacci={1, 30} Time:{2}", i, ret, ts));
                    }
                    Console.WriteLine("End process.");
                }
                else
                {
                    Console.WriteLine("Please input number.");
                }

                cki = Console.ReadKey();
                Console.Clear();

            } while (cki.Key != ConsoleKey.Escape);
        }
    }
}

Fibonacci.cs

using System.Collections.Generic;

namespace FibonacciOnConsole
{

    public interface IFibonacciStrategy
    {
        decimal Calc(decimal i);
    }

    public class Fibonacci : IFibonacciStrategy
    {
        public decimal Calc(decimal i)
        {
            if( i == 0 )
            {
                return 0;
            }
            if( i == 1 )
            {
                return 1;
            }
            return Calc(i - 1) + Calc(i - 2);
        }


    }

    public class FibonacciWithCache : IFibonacciStrategy
    {
        Dictionary<decimal, decimal> _cache = new Dictionary<decimal, decimal>();

        public decimal Calc(decimal i)
        {
            if (i == 0)
            {
                return 0;
            }
            if (i == 1)
            {
                return 1;
            }
            decimal cachedValue = 0;
            if (_cache.TryGetValue(i, out cachedValue))
            {
                return cachedValue;
            }

            var ret = Calc(i - 1) + Calc(i - 2);
            _cache.Add(i, ret);
            return ret;
        }

    }
}

再帰の場合、処理時間を考慮する必要はありますね。
GitHubにもあげてあります。
https://github.com/Koki-Shimizu/Fibonacci.git