Friday, September 25, 2009

Fun with the Fibonacci Sequence in PHP



function getPi($n) {
for($i = 1; $i <= $n; $i++)
$sum = bcadd($sum, bcdiv('1',bcmul($i,$i)));
return bcsqrt(bcmul($sum, '6'));
}

function fib($n) {
global $PI;
if($n < 2) return $n;
$onePlusSqrt5 = bcadd('1', bcsqrt('5'));
$numeratorleft = bcmul('0.5', $onePlusSqrt5);
$numeratorright = bcdiv('2', $onePlusSqrt5);
return bcround(bcdiv(bcmul(bcsub(bcpow($numeratorleft, $n), bcpow($numeratorright, $n)), cos(bcmul($PI,$n))), bcsqrt('5')));
}

function bcround($strval, $precision = 0) {
if (false !== ($pos = strpos($strval, '.')) && (strlen($strval) - $pos - 1) > $precision) {
$zeros = str_repeat('0', $precision);
return bcadd($strval, '0.{$zeros}5', $precision);
} else {
return $strval;
}
}

function bcdechex($dec, $digits = false) {
$hex = '';
$positive = $dec < 0 ? false : true;

while($dec) {
$hex .= dechex(abs(bcmod($dec, '16')));
$dec = bcdiv($dec, '16', 0);
}
if($digits) {
while(strlen($hex) < $digits)
$hex .= '0';
}

if($positive)
return strrev($hex);

for($i = 0; $isset($hex[$i]); $i++)
$hex[$i] = dechex(15 - hexdec($hex[$i]));
for($i = 0; isset($hex[$i]) && $hex[$i] == 'f'; $i++)
$hex[$i] = '0';
if(isset($hex[$i]))
$hex[$i] = dechex(hexdec($hex[$i]) + 1);
return strrev($hex);
}


function ff_initialize($scale = 10) {
bcscale($scale);
getPi($scale);
}

function ff_maxfiboflen($n) {
for($i = 1; $n > 0; $i++) {
echo "$i ...\r";
if(strlen($f = fib($i)) > $n)
return fib($i-1);
}
}

function ff_maxhexfiboflen($n) {
for($i = 1; $n > 0; $i++) {
echo "$i ...\r";
if(strlen($f = bcdechex(fib($i))) > $n)
return "0x".strtoupper(bcdechex(fib($i-1)));
}
echo "error";
}

ff_initialize();

echo "max hex value of length 10:\n";
echo ff_maxhexfiboflen(10)."\n";

echo "max dec value of length 10:\n";
echo ff_maxfiboflen(10)."\n";