(* Recursive Computation *)

fiba[1] = fiba[2] = 1;
fiba[n_] := fiba[n-1] + fiba[n-2]

(* Dynamic Programming *)

fibb[1] = fibb[2] = 1;
fibb[n_] := fibb[n] = fibb[n-1] + fibb[n-2]

(* Schleife *)

fibc[n_] :=
	Module[{fi = 1, fi1 = 0},
		Do[ {fi, fi1} = {fi + fi1, fi}, {n - 1} ];
		fi
	]

(* Symbolic Computation *)

With[{ a2 = 1/Sqrt[5], a1 = -(1/Sqrt[5]),
       e2 = (1 + Sqrt[5])/2, e1 = (1 - Sqrt[5])/2},
    fibd[n_] := Expand[ a1 e1^n + a2 e2^n ]
]

(* Numerical Computation *)

With[{ a2 = 1/Sqrt[5], e2 = (1 + Sqrt[5])/2},
    fibe[n_] :=
	Module[{digits, approx},
		digits = N[Log[10, a2] + n Log[10, e2]];
		digits = Ceiling[digits] + 10;
		approx = N[a2, digits] N[e2, digits]^n;
		Round[approx]
	]
]

(* Fast Powers *)

fibf[n_] :=
	Module[{result = IdentityMatrix[2], nn = n-1, s = {{1, 1}, {1, 0}}},
		While[ nn > 1,
			If[OddQ[nn], result = result . s];
			s = s . s;
			nn = Floor[nn/2];
		];
		result = result . s;
		result[[1, 1]]
	]

(* Avoidance of unnecessary computations at the end *)

fibg[n_] :=
	Module[{result = IdentityMatrix[2], nn = n-1, s = {{1, 1}, {1, 0}}},
		While[ nn > 1,
			If[OddQ[nn], result = result . s];
			s = s . s;
			nn = Floor[nn/2];
		];
		result[[1,1]] s[[1,1]] + result[[1,2]] s[[2,1]]
	]

(* Use of symmetries *)

fibh[n_] :=
	Module[{r11 = 1, r12 = 0, r22 = 1, s11 = 1, s12 = 1, s22 = 0,
	       nn = n-1},
		While[ nn > 1,
			If[OddQ[nn], 
				{r11, r22} = r12 s12 + {r11 s11, r22 s22};
				r12 = r11 - r22
			  ];
			{s11, s22} = s12^2 + {s11^2, s22^2};
			s12 = s11 - s22;
			nn = Quotient[nn, 2]
		];
		r11 s11 + r12 s12
	]

(* Fast powers from left to right *)

fibi[n_] :=
	Module[{r11 = 1, r12 = 0, r22 = 1, digits = IntegerDigits[n-1, 2], i},
		Do[ {r11, r22} = r12^2 + {r11^2, r22^2};
		    r12 = r11 - r22;
		    If[digits[[i]] == 1, 
		       {r11, r12, r22} = {r11 + r12, r11, r12}
		      ],
		   {i, Length[digits]}
		  ];
		r11
	]

(* The same with one multiplication less *)

fibj[n_] :=
	Module[{r11 = 1, r12 = 0, r22 = 1, digits = IntegerDigits[n-1, 2], i, t},
		Do[ If[ digits[[i]] == 1, (* odd *)
		        {r11, r22} = {r11(r11 + 2r12), r12(r11 + r22)};
		        r12 = r11 - r22
		      ,  (* else even *)
		        t = r12(r11 + r22);
		        {r11, r12} = {r11(r11 + 2r12) - t, t};
		        r22 = r11 - r12
		      ],
		   {i, Length[digits]-1}
		  ];
		If[ digits[[-1]] == 1,
		    r11(r11 + 2r12),                 (* odd  *)
		    r11(r11 + r22) - (-1)^((n-1)/2)  (* even *)
		]
	]
