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