The Fibonacci recurrence needs only the previous two terms.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | <?php declare(strict_types=1); // Iterative Fibonacci in PHP // // PURPOSE // The Fibonacci recurrence needs only the previous two terms. Keeping those terms avoids // both exponential recursion and a full table. // // METHOD // Maintain F(i) and F(i+1), then advance the pair. Return F(n) after n advances. // // COMPLEXITY // O(n) time and O(1) auxiliary space, under fixed-width arithmetic. // // CONTRACT // n >= 0, with F(0)=0 and F(1)=1. Use n <= 45 for every intermediate value to fit signed // 32-bit integers in this version. // Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex // counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers. // Sorted order, correct tree topology, and caller-owned data-structure invariants are // preconditions; checking them on every query would change query complexity. // Scalar and shape checks are included. Value-range checks are included where needed to // prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000 // workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python // uses arbitrary precision. Native allocation failures propagate. In-place outputs may be // partly updated after arithmetic failure. These are single-threaded, in-memory // implementations. // // LANGUAGE DETAILS // PHP 8.1+ on a 64-bit runtime: packed arrays, strict scalar types, read-only inputs by // value using copy-on-write, references only for outputs, and checked 32-bit arithmetic. // Invalid input and overflow throw exceptions. PHP arrays have higher overhead than native // packed buffers in C/Java. // // EXAMPLE // Expected return: 0. // Run: php example.php // Tests for this exact source artifact run before publication. The accompanying source // archive includes unit cases, runtime results, and source hashes. function alg_require(bool $valid): void { if (!$valid) throw new InvalidArgumentException("invalid algorithm input"); } function alg_checked(int|float $v): int { if ($v < -2147483648 || $v > 2147483647 || floor($v) != $v) throw new OverflowException("32-bit result overflow"); return (int)$v; } function alg_add(int $a,int $b): int { return alg_checked($a+$b); } function alg_sub(int $a,int $b): int { return alg_checked($a-$b); } function alg_mul(int $a,int $b): int { return alg_checked($a*$b); } function alg_size(int $n): int { alg_require($n>=0 && $n<=4000000); return $n; } function fibonacci(int $n): int { alg_require((($n >= 0) && ($n <= 1000000))); alg_require((($n >= 0) && ($n <= 45))); $a = 0; $b = 1; $next_value = 0; $i = 0; while (($i < $n)) { $next_value = alg_add($a, $b); $a = $b; $b = $next_value; $i = alg_add($i, 1); } return $a; } $n = 0; $result = fibonacci($n); echo $result, PHP_EOL; |