Here are a handful (with test code). No fancy maths: partly out of pity for onion2k (who isn't reading this thread); partly because there wouldn't really be any point - the obvious algorithm is already O(n), and if I could think of anything to reduce that I strongly suspect it would bog down in its own overhead. So, all of the variation is at the coding level.
function recurse_factorial($i)
{
if($i==0) return 1;
return bcmul($i,recurse_factorial($i-1));
}
function plain_loop_factorial($i)
{
$f = 1;
for($j=1; $j<=$i; ++$j)
$f = bcmul($f,$j);
return $f;
}
function plain_loop_with_breakover_factorial($i)
{
$f = 1;
for($j=1; $j<=$i; ++$j)
if($j<12)
$f*=$j;
else
$f = bcmul($f,$j);
return $f;
}
function memoised_factorial($i)
{
// Uses memoisation to avoid repeated calculation over multiple calls.
static $memo=array(1);
if(!isset($memo[$i]))
{
$set = array_keys($memo);
$j = count($set)-1; // The largest factorial we have is $j!.
while($j>0 && $set[$j]>$i) --$j;
for($k=$set[$j]+1; $k<=$i; ++$k)
{
// Breakover to string storage and bcmul computation
// if ints are too small.
// Could go up into doubles but not by much
// (around $k==20 or so)
if($k>12)
$memo[$k] = bcmul($k,$memo[$k-1]);
else
$memo[$k] = $k*$memo[$k-1];
}
}
return $memo[$i];
}
function no_loops_factorial_aka_the_one_liner($i)
{
return array_reduce(range(1,$i), 'bcmul', 1);
}
$keys = array_rand(range(1,5000), 50); // The keys are good enough,
shuffle($keys); // if they're in a random order
$t0 = microtime(true);
$recurse = array_map('recurse_factorial', $keys);
$t1 = microtime(true);
$plain = array_map('plain_loop_factorial', $keys);
$t2 = microtime(true);
$breakover = array_map('plain_loop_with_breakover_factorial', $keys);
$t3 = microtime(true);
$memo = array_map('memoised_factorial', $keys);
$t4 = microtime(true);
$loop = array_map('no_loops_factorial_aka_the_one_liner', $keys);
$t5 = microtime(true);
echo "Computing the factorials for the given integers in the given order: ";
echo join(', ', $keys),"\n";
echo 'Recursion: ', $t1-$t0, " seconds\n";
echo 'Plain: ', $t2-$t1, " seconds\n";
echo 'Plain with breakover: ', $t3-$t2, " seconds\n";
echo 'Memoised: ', $t4-$t3, " seconds\n";
echo 'One-liner ', $t5-$t4, " seconds\n";
Guess which one I'm submitting 🙂
