Fibonacci sequence and the golden ratio
The golden ratio also shows up in nature (sunflower seeds, seashells) - this demo has two views: the sunflower pattern places each seed by rotating it by the golden angle, while the golden spiral is built from quarter-circle arcs inscribed in squares with Fibonacci side lengths. Both are drawn on the server with PHP GD.
"Real PHP runs": 4 methods, real measured time
All 4 PHP functions below ACTUALLY run on the server, freshly on every click - the time is not simulated, it is measured with PHP's own nanosecond-precision clock (hrtime).
Naive recursion
The textbook solution: fib(n) = fib(n-1) + fib(n-2), with no speedup at all. It recomputes the same subresults over and over, so it slows down exponentially as n grows.
function naiveRecursive(int $n): int
{
if ($n < 2) {
return $n;
}
return naiveRecursive($n - 1) + naiveRecursive($n - 2);
}Dynamic programming
Builds the sequence bottom-up in a single loop - every term is computed exactly once, so it runs in linear (O(n)) time.
function dynamicProgramming(int $n): int
{
if ($n < 2) {
return $n;
}
$prev = 0;
$curr = 1;
for ($i = 2; $i <= $n; $i++) {
[$prev, $curr] = [$curr, $prev + $curr];
}
return $curr;
}Binet's closed formula
A closed-form formula built on the golden ratio - gives a result in a single computation (O(1)), but uses floating-point arithmetic, so it becomes imprecise at sufficiently large n.
function binetFormula(int $n): float
{
$sqrt5 = sqrt(5.0);
$phi = (1.0 + $sqrt5) / 2.0;
$psi = (1.0 - $sqrt5) / 2.0;
return ($phi ** $n - $psi ** $n) / $sqrt5;
}Fast matrix exponentiation
fib(n) can be read off the n-th power of the matrix [[1,1],[1,0]] - exponentiation by squaring gets there in O(log n) steps, with exact integer arithmetic (using GMP where available).
// [[1,1],[1,0]]^n = [[F(n+1),F(n)],[F(n),F(n-1)]]
$result = [[1, 0], [0, 1]]; // egységmátrix
$base = [[1, 1], [1, 0]];
while ($n > 0) {
if ($n & 1) $result = matMul($result, $base);
$base = matMul($base, $base);
$n >>= 1;
}
return $result[0][1]; // F(n)