Efficiently computing a factorial using binary splitting

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