# High-performance Fibonacci numbers generator in PHP

###
Rafael Bernard Araújo
*
Originally published at
rafael.bernard-araujo.com
on
*
・2 min read

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.

## dev.to/you

### Claim your page on DEV before someone else does

### Join DEV Now

Open source

Free forever

Level up every day

🤝