This thread is now in deep hijack, but I thought I'd point out that the (phi^n - (1-phi)^n)/sqrt(5) formula is not great for computation because it requires real number operations and results in a real number, unlike the other algorithms, which can produce a result in essentially any form. If you actually want an integer result or want to know a Fibonacci number mod some integer, then that formula is not suitable for large values of n. (For small values of n, it will work, though.) A better way is the following recursive algorithm. In the interest of being vaguely on-topic at least for this forum, the following is implemented in the "Other Programming Language" Ada.
Specification:
package Fibo_Tools is
subtype Long_Natural is Long_Integer range 0..Long_Integer'Last;
type Mod_Natural is mod 2**31;
function Fibonacci(N: Natural) return Mod_Natural;
end Fibo_Tools;Alternative 1 (tree recursion):package body Fibo_Tools is
function Fibonacci (N: Long_Natural) return Mod_Natural is
begin
if (N = 0) then return 0;
elsif (N = 1) then return 1;
else return Fibonacci(N-1) + Fibonacci(N-2);
end if;
end Fibonacci;
end Fibo_Tools;Alternative 2 (linear iterative):package body Fibo_Tools is
function Fibonacci (N: Long_Natural) return Mod_Natural is
A: Mod_Natural := 0;
B: Mod_Natural := 1;
begin
for K in 1..N loop
B := B + A;
A := B - A;
end loop;
return A;
end Fibonacci;
end Fibo_Tools;Alternative 3 (recursive, repeated "squaring," using the formulas F(2n-1) = F(n-1)^2 + F(n)^2, F(2n) = F(n)(F(n-1) + F(n+1)), F(2n+1) = F(n)^2 + F(n+1)^2):package body Fibo_Tools is
type Fib_State is array (0..2) of Mod_Natural;
procedure Fib_Rec (N: in Long_Natural; X: in out Fib_State) is
begin
if (N > 0) then
Fib_Rec(N/2, X);
X(0..2) := (X(0)**2+X(1)**2, X(1)*(X(0)+X(2)), X(1)**2+X(2)**2);
if (N mod 2 = 1) then X(0..2) := (X(1), X(2), X(1)+X(2));
end if;
end if;
end Fib_Rec;
function Fibonacci (N: Long_Natural) return Mod_Natural is
X: Fib_State := (1, 0, 1);
begin
Fib_Rec(N, X);
return X(1);
end Fibonacci;
end Fibo_Tools;Driver program:with Ada.Text_Io, Ada.Command_Line, Ada.Real_Time, Fibo_Tools;
use Fibo_Tools, Ada.Real_Time;
procedure Fibo is
package Nat_IO is new Ada.Text_IO.Integer_IO(Long_Natural);
package Int_IO is new Ada.Text_IO.Integer_IO(Long_Integer);
N: Long_Natural;
F_N: Mod_Natural;
Start_Time: Ada.Real_Time.Time;
End_Time: Ada.Real_Time.Time;
Ticks: Integer;
begin
if (Ada.Command_Line.Argument_Count < 1) then
Ada.Text_IO.Put_Line(
Ada.Text_IO.Standard_Error,
"Usage: fibo argument");
return;
end if;
declare
Arg1 : String := Ada.Command_Line.Argument(1);
Last : Positive;
begin
Nat_IO.Get(Arg1, N, Last);
end;
Start_Time := Ada.Real_Time.Clock;
F_N := Fibonacci(N);
End_Time := Ada.Real_Time.Clock;
-- (using "-", "/" of Ada.Real_Time)
Ticks := (End_Time - Start_Time)/Ada.Real_Time.Tick;
Int_IO.Put(Long_Integer(F_N), 0);
Ada.Text_IO.New_Line(1);
Int_IO.Put(Long_Integer(Ticks), 0);
Ada.Text_IO.Put(" clock ticks elapsed");
end Fibo;For comparison, compiling with alternative 1 (tree recursion) with argument 40 tends to report around 43,000,000 clock ticks, taking about 43 seconds. Compiling with alternative 2 (linear iterative) tends to report 7 clock ticks for argument 30. The highest possible input argument, 2^31-1, is feasible, but it takes time, reporting around 16,000,000 clock ticks (16 seconds). With alternative 3, every allowable input (0 up to 2^31-1) is handled instantaneously (11-12 clock ticks). In terms of big-O notation, alternative 1 is O(phi^n) time (not O(n^phi), which would be considerably better ;)) and O(n) space; alternative 2 is O(n) time and O(1) space (in practice O(log(n)) space, though); alternative 3 is O(log(n)) time and O(log(n)) space. Basically, each successive implementation is astronomically better than the previous one.
Due to technical difficulties (I'm still learning the language), I didn't include the round(phi^n/sqrt(5)) algorithm, but as I said, it is in a way fundamentally different from the other algorithms and is less flexible.