Fib

using System;
using System.Collections.Generic;

using BigInt = System.Numerics.BigInteger;

namespace FibTest
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int n = 0; n < 136; n++)
            {
                var f = Fib(n);
                //var b = Fib_b(n);
                var b = Fib_x(n);
                Console.WriteLine("{0,3}: ({1,14}) {2,28} {3,28}", n, b - f, f, b);
                Console.WriteLine();
            }
        }

        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 Ext
        {
            private BigInt a;
            private BigInt b;

            public Ext(BigInt a, BigInt b)
            {
                this.a = a;
                this.b = b;
            }
            public BigInt A { get { return a; } }
            public BigInt B { get { return b; } }

            // twoPhi = Ext 1 1
            public static readonly Ext TWO_PHI = new Ext(1, 1);

            // fromInteger a = Ext a 0
            public static implicit operator Ext(BigInt a)
            {
                return new Ext(a, 0);
            }

            // negate (Ext a b) = Ext (-a) (-b)
            public static Ext operator -(Ext x)
            {
                return new Ext(-x.a, -x.b);
            }

            // (Ext a b) + (Ext c d) = Ext (a+c) (b+d)
            public static Ext operator +(Ext x, Ext y)
            {
                return new Ext(x.a + y.a, x.b + y.b);
            }

            // just in case
            public static Ext operator -(Ext x, Ext y)
            {
                return x + -y;
            }

            // (Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c)
            public static Ext operator *(Ext x, Ext y)
            {
                return new Ext(x.a + y.a + 5*x.b*y.b, x.a*y.b + x.b*y.a);
            }

            public static Ext operator ^(Ext x, int p) // "exponent"
            {
                // just apply across both parts of Ext?
                return new Ext(BigInt.Pow(x.a, p), BigInt.Pow(x.b, p));
            }
        }

        static BigInt Fib_x(int n)
        {
            // fib n = divide $ twoPhi^n - (2-twoPhi)^n

            Ext x = (Ext.TWO_PHI ^ n) - (((BigInt)2 - Ext.TWO_PHI) ^ n);
            //    subtraction needed? ^             ^

            return divide(x, n);
        }

        static BigInt divide(Ext x, int n)
        {
            // divide (Ext 0 b) = b `div` 2^n
            //             ^ divide only if 0?
            //               or a "don't care" value?

            return x.B / BigInt.Pow(2, n);
        }
    }
}