I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem:
$$P(n) = \sum_{k=1}^n (-1)^{k+1} \left[ P\left( n - \frac{k\left(3k-1\right)}{2} \right) + P\left( n - \frac{k\left(3k+1\right)}{2} \right) \right]$$
To get it to complete on large-ish inputs (say, 60,000 or so) on a reasonable time , I used a mutable vector, internally. (This cut the time by about half from using an immutable vector, and by a ... very large amount, I forget how much, from using "pure" memoization.) It now calculates \$p(60000)\$ in about 8 seconds or so on my machine, which is reasonable for my purposes. (Though three times slower than a C++ equivalent.)
I wondered if anyone had any suggestions for getting similar performance, but without using mutable state?
{-# LANGUAGE BangPatterns #-}
import Control.Monad (when, forM_, forM)
import Data.STRef
import Control.Monad.ST
import qualified Data.Vector.Generic.Mutable as GM
import Data.Vector.Generic.Mutable ( write )
import qualified Data.Vector.Mutable as VM
main :: IO ()
main = do
print $ part 60000
fint :: (Num b, Integral a) => a -> b
fint = fromIntegral
part :: Int -> Integer
part n = runST $ do
vec <- VM.replicate (n+1) (-3)
write vec 0 1
result <- newSTRef (-1)
forM_ [1..n] $ \i' -> do
let i = ((fromIntegral i') :: Integer)
!sR <- newSTRef 0
let -- loop :: Integer -> ST s ()
loop k = do
let f = (fint (i - k * (3 * k - 1) `div` 2))
when (not (f < 0)) $ do
if k `mod` 2 /= 0
then do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s + vec_f)
else do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s - vec_f)
let f = (fint (i - k * (3 * k + 1) `div` 2))
let xx = f :: Int
when (not (f < 0)) $ do
if k `mod` 2 /= 0
then do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s + vec_f )
else do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s - vec_f)
loop (k + 1)
loop 1 -- k starts at 1
!s <- readSTRef sR
write vec i' s
when (i' == n) $
writeSTRef result s
readSTRef result