DEV Community

Rafael Bernard Araújo
Rafael Bernard Araújo

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

3 1

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.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay