Create a gist now

Instantly share code, notes, and snippets.

Functional Programming in 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());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment