Chowla numbers: Difference between revisions
Content added Content deleted
m (→{{header|Haskell}}: use STM TChan vs Chan. Significant performance improvement.) |
|||
Line 1,520: | Line 1,520: | ||
Uses arithmoi Library: https://hackage.haskell.org/package/arithmoi-0.11.0.0 |
Uses arithmoi Library: https://hackage.haskell.org/package/arithmoi-0.11.0.0 |
||
compiled with "-O2 -threaded -rtsopts"<br/> |
compiled with "-O2 -threaded -rtsopts"<br/> |
||
<lang haskell>import Control.Concurrent (setNumCapabilities |
<lang haskell>import Control.Concurrent (setNumCapabilities) |
||
import Control. |
import Control.Monad.Par (runPar, get, spawnP) |
||
import Control.Monad (join, (>=>)) |
|||
import Control.Monad (forever, replicateM_, replicateM) |
|||
import Data.List.Split (chunksOf) |
import Data.List.Split (chunksOf) |
||
import Data.List (intercalate, mapAccumL, genericTake, genericDrop) |
import Data.List (intercalate, mapAccumL, genericTake, genericDrop) |
||
Line 1,537: | Line 1,536: | ||
f = (-) =<< pred . product . fmap sumFactor . factorise |
f = (-) =<< pred . product . fmap sumFactor . factorise |
||
sumFactor (n, e) = foldr (\p s -> s + unPrime n^p) 1 [1..e] |
sumFactor (n, e) = foldr (\p s -> s + unPrime n^p) 1 [1..e] |
||
⚫ | |||
chowlas [] = [] |
|||
chowlas xs = runPar $ join <$> |
|||
(mapM (spawnP . fmap ((,) <*> chowla)) >=> mapM get) (chunksOf (10^6) xs) |
|||
chowlaPrimes :: [(Word, Word)] -> (Word, Word) -> (Word, Word) |
chowlaPrimes :: [(Word, Word)] -> (Word, Word) -> (Word, Word) |
||
Line 1,548: | Line 1,552: | ||
chowlaPerfects :: [(Word, Word)] -> [Word] |
chowlaPerfects :: [(Word, Word)] -> [Word] |
||
chowlaPerfects = fmap fst . filter isPerfect |
chowlaPerfects = fmap fst . filter isPerfect |
||
where |
where |
||
isPerfect (1, _) = False |
isPerfect (1, _) = False |
||
isPerfect (n, c) = c == pred n |
isPerfect (n, c) = c == pred n |
||
Line 1,554: | Line 1,558: | ||
commas :: (Show a, Integral a) => a -> String |
commas :: (Show a, Integral a) => a -> String |
||
commas = reverse . intercalate "," . chunksOf 3 . reverse . show |
commas = reverse . intercalate "," . chunksOf 3 . reverse . show |
||
⚫ | |||
chowlaWorker input output = forever (atomically (readTChan input) >>= |
|||
atomically . writeTChan output . ((,) <*> chowla)) |
|||
main :: IO () |
main :: IO () |
||
Line 1,564: | Line 1,564: | ||
setNumCapabilities cores |
setNumCapabilities cores |
||
printf "Using %d cores\n" cores |
printf "Using %d cores\n" cores |
||
allChowlas <- parallelChowlas cores |
|||
mapM_ (uncurry (printf "chowla(%2d) = %d\n")) $ take 37 allChowlas |
mapM_ (uncurry (printf "chowla(%2d) = %d\n")) $ take 37 allChowlas |
||
mapM_ (uncurry (printf "There are %8s primes < %10s\n")) |
mapM_ (uncurry (printf "There are %8s primes < %10s\n")) |
||
(chowlaP |
(chowlaP |
||
[ (1, 10^2) |
[ (1, 10^2) |
||
, (succ $ 10^2, 10^3) |
, (succ $ 10^2, 10^3) |
||
Line 1,577: | Line 1,575: | ||
, (succ $ 10^6, 10^7) ]) |
, (succ $ 10^6, 10^7) ]) |
||
⚫ | |||
mapM_ (printf "%10s is a perfect number.\n" . commas) perfects |
mapM_ (printf "%10s is a perfect number.\n" . commas) perfects |
||
printf "There are %2d perfect numbers < 35,000,000\n" $ length perfects |
printf "There are %2d perfect numbers < 35,000,000\n" $ length perfects |
||
where |
where |
||
chowlaP |
chowlaP = fmap (bimap commas commas) . snd |
||
. mapAccumL (\total (count, max) -> (total + count, (total + count, max))) 0 |
. mapAccumL (\total (count, max) -> (total + count, (total + count, max))) 0 |
||
. fmap (chowlaPrimes $ take (10^7) |
. fmap (chowlaPrimes $ take (10^7) allChowlas) |
||
⚫ | |||
allChowlas = chowlas [1..35*10^6]</lang> |
|||
parallelChowlas cores = do |
|||
inputChan <- atomically newTChan |
|||
outputChan <- atomically newTChan |
|||
replicateM_ cores (forkIO $ chowlaWorker inputChan outputChan) |
|||
mapM_ (atomically . writeTChan inputChan) [1..35*10^6] |
|||
replicateM (35*10^5) (atomically (readTChan outputChan))</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Using 4 cores |
<pre>Using 4 cores |