Fibonacci-számsorozat és aranymetszés
A természetben (napraforgó-mag, kagylóhéj) is megjelenő aranymetszést két nézetben mutatja be: a napraforgó-mintázat a magok pozícióját az aranyszöggel forgatva helyezi el, az aranyspirál pedig Fibonacci-oldalhosszú négyzetekbe írt negyedköríves ívekből épül fel - mindkettő a szerveren, PHP GD-vel rajzolva.
"Valódi PHP fut": 4 módszer, valódi mért idő
Mind a 4 alábbi PHP-függvény TÉNYLEGESEN lefut a szerveren, minden gombnyomásra újra - az idő nem szimulált, hanem a PHP saját, nanoszekundum-pontos órájával (hrtime) mérve.
Naiv rekurzió
A tankönyvi megoldás: fib(n) = fib(n-1) + fib(n-2), semmilyen gyorsítás nélkül. Ugyanazt a részeredményt sokszor, feleslegesen újraszámolja, ezért exponenciálisan lassul n növelésével.
function naiveRecursive(int $n): int
{
if ($n < 2) {
return $n;
}
return naiveRecursive($n - 1) + naiveRecursive($n - 2);
}Dinamikus programozás
Alulról felfelé építkezve, egyetlen ciklussal számolja ki a sorozatot - minden tagot pontosan egyszer, ezért lineáris (O(n)) idő alatt fut.
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 zárt képlete
Az aranymetszésre épülő zárt matematikai képlet - egyetlen számítással (O(1)) ad eredményt, de lebegőpontos aritmetikával, ezért elég nagy n-nél pontatlanná válik.
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;
}Gyors mátrix-hatványozás
A [[1,1],[1,0]] mátrix n-edik hatványából olvasható ki fib(n) - "négyzetre emeléses" hatványozással O(log n) lépésben, egzakt egész aritmetikával (GMP-vel, ha elérhető a szerveren).
// [[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)