Fib2

using System;
using System.Collections.Generic;

using BigInt = System.Numerics.BigInteger;

namespace FibTest
{
    class Program
    {
        static void Main(string[] args)
        {
            //Test1();
            Test2();
        }

        static void Test1()
        {
            for (int n = 0; n < 356; n++)
            {
                var f = Fib(n);
                var db = Fib_b(n) - f;
                var dx = Fib_x(n) - f;

                Console.WriteLine("{0,3}: {1}", n, f);
                Console.WriteLine(" db: {0:+0}", db);
                Console.WriteLine(" dx: {0:+0}", dx);
                Console.WriteLine();
            }
        }

        static void Test2()
        {
            var iterations = int.MaxValue;
            var ib = 0;
            var ix = 0;
            int n;
            for (n = 0; n < iterations; n++)
            {
                try
                {
                    var f = Fib(n);
                    var b = Fib_b(n);
                    var x = Fib_x(n);
                    if (f != b) ib++;
                    if (f != x) ix++;
                }
                catch (OverflowException)
                {
                    // FP fail
                    break;
                }
            }

            Console.WriteLine("After {0} iterations, total inaccuracies found:", n);
            Console.WriteLine("\tFib_b: {0}", ib);
            Console.WriteLine("\tFib_x: {0}", ix);
        }

        static readonly Dictionary<int, BigInt> memo = new Dictionary<int, BigInt>();
        static BigInt Fib(int n)
        {
            BigInt result;
            if (!memo.TryGetValue(n, out result))
            {
                if (n < 2)
                    memo[n] = result = BigInt.Max(0, n);
                else
                    memo[n] = result = Fib(n - 1) + Fib(n - 2);
            }
            return result;
        }

        static readonly double RAD5 = Math.Sqrt(5);
        static readonly double PHI = (1 + RAD5) / 2;
        static BigInt Fib_b(int n)
        {
            double result = Math.Pow(PHI, n) / RAD5;
            return (BigInt)Math.Round(result);
        }

        struct Complicated
        {
            private BigInt real;
            private BigInt bogus;

            public Complicated(BigInt real, BigInt bogus)
            {
                this.real = real;
                this.bogus = bogus;
            }
            public BigInt Real { get { return real; } }
            public BigInt Bogus { get { return bogus; } }

            public static Complicated Pow(Complicated value, int exponent)
            {
                if (exponent < 0)
                    throw new ArgumentException("only non-negative exponents supported", "exponent");

                Complicated result = 1;
                Complicated factor = value;
                for (int mask = exponent; mask != 0; mask >>= 1)
                {
                    if ((mask & 0x1) != 0)
                        result *= factor;
                    factor *= factor;
                }
                return result;
            }

            public static implicit operator Complicated(int real)
            {
                return new Complicated(real, 0);
            }

            public static Complicated operator -(Complicated l, Complicated r)
            {
                var real = l.real - r.real;
                var bogus = l.bogus - r.bogus;
                return new Complicated(real, bogus);
            }

            public static Complicated operator *(Complicated l, Complicated r)
            {
                var real = l.real * r.real + 5 * l.bogus * r.bogus;
                var bogus = l.real * r.bogus + l.bogus * r.real;
                return new Complicated(real, bogus);
            }
        }

        static readonly Complicated TWO_PHI = new Complicated(1, 1);
        static BigInt Fib_x(int n)
        {
            var x = Complicated.Pow(TWO_PHI, n) - Complicated.Pow(2 - TWO_PHI, n);
            System.Diagnostics.Debug.Assert(x.Real == 0);
            return x.Bogus / BigInt.Pow(2, n);
        }
    }
}