Based on the article High-performance Fibonacci numbers generator in Go I wrote my version using PHP. Despite the differences between PHP and Go architectures reflected in response times, we can face a huge performance difference when using an optimized function. We may notice that we can have the same results, but the quality of the written code can change lots of things.
Recursive approach
function fibonacci(int $n):int {
if ($n <= 1) {
return $n;
}
return fibonacci($n-1) + fibonacci($n-2);
}
Benchmark and test
function test_fibonacci() {
$data = [
[0,0], [1,1], [2,1], [3,2], [4,3], [5,5], [6,8], [10,55], [42,267914296]
];
foreach($data as $test) {
$result = fibonacci($test[0]);
if ($result !== $test[1]) {
throw new \UnexpectedValueException("Error Processing Request. N: {$test[0]}, got: {$result}, expected: {$test[1]}", 1);
}
}
echo "Tests - Success.".PHP_EOL;
}
/**
* From https://gist.github.com/blongden/2352583
*/
function benchmark($x)
{
$start = $t = microtime(true);
$total = $c = $loop = 0;
while (true) {
$x();
$c++;
$now = microtime(true);
if ($now - $t > 1) {
$loop++;
$total += $c;
list($t, $c) = array(microtime(true), 0);
}
if ($now - $start > 2) {
return round($total / $loop);
}
}
}
Benchmark 10 run: 163,754/sec or 0.0061067210571955ms/op
Benchmark 20 run: 1,351/sec or 0.74019245003701ms/op
As we can see, calculations of 20 Fibonacci numbers takes 123 times longer than 10 Fibonacci numbers. Not well performed at all! The explanation can be found in the linked article.
Sequential approach
function fibonacci_tuned(int $n):float {
if ($n <= 1) {
return $n;
}
$n2 = 0;
$n1 = 1;
for ($i = 2; $i < $n; $i++) {
$n2_ = $n2;
$n2 = $n1;
$n1 = ($n1 + $n2_);
}
return $n2 + $n1;
}
function test_fibonacci_tuned() {
$data = [
[0,0], [1,1], [2,1], [3,2], [4,3], [5,5], [6,8], [10,55], [42,267914296]
];
foreach($data as $test) {
$result = fibonacci_tuned($test[0]);
$float_test_value = (float) $test[1];
if ($result !== $float_test_value) {
throw new \UnexpectedValueException("Error Processing Request. N: {$test[0]}, got: {$result}, expected: {$float_test_value}", 1);
}
}
echo "Tests - Success.".PHP_EOL;
}
Results:
Benchmark 10 tuned run: 3,345,999/sec or 0.00029886440492062ms/op
Benchmark 20 tuned run: 2,069,100/sec or 0.00048330191870862ms/op
As a much better scenario, calculate 20 numbers takes almost 2 times longer than 10 numbers. Makes sense. And performs well!
Considering the two approaches, the recursive approach runs 10 Fibonacci numbers operations 20 times longer than sequential one and 1,824 times longer for 20 Fibonacci numbers.
Fibonacci implementation in PHP can be found at https://github.com/rafaelbernard/php-fibonacci.
Top comments (0)