$RecursionLimit = Infinity;
Fib3[0] = 0;
Fib3[1] = 1;
Fib3[
        n_] := (Fib3[n] = 
            Module[{fib = Fib3[(n/2)]}, fib*(fib + 2*Fib3[(n/2) - 1])]) /; 
        EvenQ[n]
Fib3[
        n_] := (Fib3[n] = Fib3[((n + 1)/2)]^2 + Fib3[((n - 1)/2)]^2) /; 
        OddQ[n]

Timing[res1 = Fib3[1000000];]

Timing[res2 = Fibonacci[1000000];]

res2 - res1