teideal glic deisbhéalach

Update 2009-05-28: My Haskell code is currently the fastest pidgits implementation, beating even the C code. It's also the briefest submission by a fairly large margin. Nice!

I purposely pay little attention to the Computer Language Benchmarks Game, but I couldn't resist this: Arnaud Payement wrote a nice Haskell implementation of the pidgits benchmark, which was quickly eclipsed by a C implementation.

The speed difference between the two is small, just 23%, so I tried to see if I could improve on Arnaud's code.

import System

pidgits n = 0%(0#(1,0,1)) where
 i%ds
  | i >= n = return ()
  | True = putStrLn (concat h ++ "\t:" ++ show j) >> j%t
  where k = i+10; j = min n k
        (h,t) | k > n = (take (n`mod`10) ds ++ replicate (k-n) " ",[])
              | True = splitAt 10 ds
j#s | n>a || r+n>=d = k#t
    | True = show q : k#(n*10,(a-(q*d))*10,d)
 where k = j+1; t@(n,a,d)=k&s; (q,r)=(n*3+a)`divMod`d
j&(n,a,d) = (n*j,(a+n*2)*y,d*y) where y=(j*2+1)

main = pidgits.read.head =<< getArgs

(Yes, there's some HTML damage in there. Hooray WordPress. Sigh.)

This version is 6% slower than the fastest C implementation, but 35% the amount of code. That seems like a good tradeoff.

I'm amused by the sole difference between the fastest and second fastest C implementations. Each avoids an expensive GMP multiplication via manual strength reduction: the faster one uses multiplication by a power of two followed by an add, while the slower version (which is the same speed as my Haskell version) uses two adds. Alas, while GHC's Integer implementation uses GMP, it doesn't use the multiply-by-a-power-of-two function (mpz_mul_2exp): if it did, I'd probably have performance on par with the fastest C code.