<?php
declare(strict_types=1);

/**
 * Optimized fib() function (Assumes F0=0, F1=1, F2=1)
 *
 * @param int $n (Must be >= zero)
 *
 * @return string
 */
function fib(int $n): string
{
    static $cache;

    if (!isset($cache)) {
        $cache = [0 => '0', 1 => '1'];
    }

    if (!isset($cache[$n])) {
        $cache[$n] = bcadd(fib($n - 1), fib($n - 2));
    }

    return $cache[$n];
}
Close Copy