DEV Community

Rafael Bernard Araújo
Rafael Bernard Araújo

Posted on • Originally published at rafael.bernard-araujo.com on

High-performance Fibonacci numbers generator in PHP

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);
}
Enter fullscreen mode Exit fullscreen mode

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);
        }
    }
}
Enter fullscreen mode Exit fullscreen mode
Benchmark 10 run: 163,754/sec or 0.0061067210571955ms/op
Benchmark 20 run: 1,351/sec or 0.74019245003701ms/op
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)