I don’t intend for this blog to become a dumping ground for code snippets, but sometimes the temptation is too strong. Here’s a simple but fast function for computing a factorial, using the binary splitting algorithm from this page.
factorial :: Integral a => a -> a
factorial n = split n 0
where split a b = let d = a - b
in if d < 0
then 0
else case d of
0 -> 1
1 -> a
2 -> a * (a - 1)
3 -> a * (a - 1) * (a - 2)
_ -> let m = (a + b) `div` 2
in split a m * split m b
Nice code. Looking at the reference though, isn’t the performance improvement dependent upon using FFT or such like for the multiplication operation?
~Matt
Yes, a fast multiply is required, but that’s common nowadays.
I’m looking forward to your Haskell book so I’m cringing at that case statement! Wouldn’t pattern matching be more Haskellish?
The case statement is pattern matching. It just happens that it’s doing so on integer patterns. Trying to hoist the pattern match up to the function definition level would make the code longer, weirder, or both. Try it and see.
Just wondering why the base case for 2 and 3 has been included. Can’t those be captured by the 0 and 1 cases?
Regarding why the base cases were included:
If you recurse all the way to the leaves of the tree it looks like this:
split(a,b):
if( … ) { base case 1 }
elif( … ) { base case 2 }
else { return split(a, (a+b)/2) * split((a+b)/2, b); }
This just changes the order in which the multiplications are performed; it’s no different than f(n) = n*f(n-1).
You can see this behavior if you print out the number of calls to split -vs- the simple recursive factorial.
For n == 0..3 split is called once and f is called {1,1,2,3} times
For n == 4..6 split is called 3 times & f {4,5,6} times, respectively
…
For n == 8..12 split is called 7 times & f {8,9,10,11,12} times
Each time the tree adds another row split will “catch up” to f for # of calls. Assuming both used the same multiplication algorithm, if there’s a significant improvement in speed it would be from fewer branch instructions.