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
Posted in haskell
5 comments on “Efficiently computing a factorial using binary splitting
  1. Matt Doar says:

    Nice code. Looking at the reference though, isn’t the performance improvement dependent upon using FFT or such like for the multiplication operation?

    ~Matt

  2. Yes, a fast multiply is required, but that’s common nowadays.

  3. paul says:

    I’m looking forward to your Haskell book so I’m cringing at that case statement! Wouldn’t pattern matching be more Haskellish?

  4. 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.

  5. Therefore, a brooker offering this feature will score well when it comes to
    the brokers rating. Before using pivot points practice
    on demo platforms. The potential losses with binary options are substantial.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>