Subscribe to
Posts
Comments

Efficiently computing a factorial using binary splitting

April 23rd, 2007 by Bryan O'Sullivan

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

4 Comments »

4 Responses to “Efficiently computing a factorial using binary splitting”

  1. on 04 May 2007 at 14:361 Matt Doar

    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. on 08 Jun 2007 at 15:002 Bryan O'Sullivan

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

  3. on 21 Jun 2007 at 23:003 paul

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

  4. on 21 Jun 2007 at 23:104 Bryan O'Sullivan

    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.

Leave a Reply