Functional Programming in PHP

functional_fibonacci.php

<?php

/**
 * Fibonacci:
 *============================================================================
 * Class for computing fibonacci numbers using functional programming in PHP
 * Uses the formula at: http://jburrows.wordpress.com/2009/12/30/fibonacci/
 */

class fibonacci {
  private $max;

  /**
   * Constructor
   * -----------
   * Takes one parameter that determines the nth fibonacci number to compute
   */
  public function __construct($n) {
    $this->max = $n;
  }

  /**
   * fibonacci::go();
   * ----------------
   * does all the calculation
   */
  public function go() {

    // this computes the factorial of $x recursively
    $factorial = function($x) use(&$factorial) {
      if($x == 0) {
        return 1;
      } else {
        return $x*$factorial($x-1);
      }
    };

    // create a lookup table for factorials up to $n passed to constructor
    $f = array_map($factorial, range(0, $this->max));

    // calculate the sequence
    $fibonacci = array_map( function($x) use($f) {
      // is a number odd?
      $odd = function($n) {
        return ($n&1);
      };

      // sum over an array
      $sum = function ($values) {
        return array_reduce($values, function($u, $v) {
          return $u += $v;
        });
      };

      // calculate the binomial coefficient of term $k of a degree $n polynoial
      $choose = function ($n, $k) use($f) {
        return $f[$n]/($f[$k] * $f[$n-$k]);
      };

      // create a range of terms of a polynomial to be operated upon
      $terms = range(0, $x);
      // filter out the even terms
      $terms = array_filter($terms, $odd);
      // calculate the terms for number $x in the fibonacci sequence
      $terms = array_map( function($i) use($x, $choose) {
          return ($choose($x, $i) * pow(5, ($i-1)/2));
        }, $terms );
      // sum over the terms dividing by proper power term and return the fibonacci number $x
      return ($sum($terms)/pow(2, $x-1));
    }, range(0, $this->max));

    // return all the number in the sequence
    return $fibonacci;

  }

}  

// create instance of fibonacci to calculate first 100 terms
$fibonacci = new fibonacci(99);
// print the resulting array
print_r($fibonacci->go());