Project Euler Problem 381

Project Euler Problem 381 is easy problem. Using Wilson theorem

Haskell source code using monad par

import Data.List
import Data.Numbers.Primes
import Control.Monad.Par
import GHC.Conc.Sync

--use wilson theorem ( p - 1 ) ! = -1 mod p 

prime = drop 2 . takeWhile ( < 10 ^ 8 ) $ primes

extendedGcd :: Int -> Int -> ( Int , Int )                 
extendedGcd a b
   | b == 0 = ( 1 , 0 )
   | otherwise = ( t , s - q * t ) where
        ( q , r ) = quotRem a b
        ( s , t ) = extendedGcd b r


modInv :: Int -> Int -> Int
modInv  a b
   | gcd a b /= 1 = error " gcd is not 1 "
   | otherwise = d where
        d = until ( > 0 ) ( + b  ) . fst.extendedGcd a $ b


computeFinal :: Int -> Int
computeFinal p = computeS ( p - 1 ) 0 1 where
     computeS inv ret cnt
        | cnt >= 5 = mod ( ret + inv ) p
        | otherwise = computeS ( mod ( inv * inv' ) p  )  ( mod ( ret + inv ) p )  ( cnt + 1 )   where
         inv' = modInv ( p - cnt ) p

chunk :: [ Int ] -> Int -> [ [ Int ] ]
chunk xs n = ret where
    tot = numCapabilities
    brk = div n tot
    ret = unfoldr fun ( xs , 1 ) where
    fun ( xs' , cnt )
     | null xs' = Nothing
     | cnt >= tot = Just ( xs' , ( [] , cnt ) )
     | otherwise = Just ( a , ( b , cnt + 1 ) ) where
        ( a , b ) = splitAt brk xs'

ans =   ret'  where
  ret = runPar $ parMap ( map computeFinal )  ( chunk prime len )
  len = length prime
  ret' = sum . map sum $ ret


main = do
   print ans

Compile it “ghc-7.4.1 -O2 -rtsopts -threaded -fforce-recomp Euler_381.hs” and run it with as many cores you have. My run time is
[mukesh@user Euler]$ time ./Euler_381 +RTS -A16M -H2G -N8 -RTS
139602943319822

real 0m28.473s
user 0m58.204s
sys 0m21.713s

About these ads