Posts Tagged ‘sieve’

Programming Praxis – Sieving For Totients

July 10, 2012

In today’s Programming Praxis exercise, our goal is to calculate the totients of a given range of numbers using a sieve. Let’s get started, shall we?

Due to the way I structured my code, Data.Map is a little more convenient than Data.Vector (since Data.Vector lacks the equivalent of the adjust function).

import qualified Data.Map as M

The sieving can be solved easily with two folds. The outer one to check all the elements in the list, and the inner one to update all the multiples of a given index. One space-saving trick is to realize that you don’t need to treat i and its multiples differently, since i * (1 – 1/i) = i – i/i = i – 1. This saves a separate insert call.

totients :: Integral a => a -> [a]
totients n = M.elems $ foldl (\m i -> if m M.! i == i
    then foldr (M.adjust (\x -> div (x*(i-1)) i)) m [i,2*i..n] else m)
    (M.fromList $ zip [0..n] [0..n]) [2..n]

A test to see if everything is working properly:

main :: IO ()
main = print $ totients 100

Programming Praxis – Sieve Of Euler

February 25, 2011

In today’s Programming Praxis exercise, our goal is to implement the Sieve of Euler to generate primes. Let’s get started, shall we?

Some imports:

import Data.List.Ordered
import Data.Time.Clock

Euler’s sieve is pretty simple: just filter out all remaining multiples of each successive prime number. We add the minor optimization of only considering odd numbers.

primes_euler :: [Integer]
primes_euler = 2 : euler [3,5..] where
    euler ~(x:xs) = x : euler (minus xs $ map (* x) (x:xs))

To compare, we use the Sieve of Eratosthenes implementation found here:

primes_eratosthenes :: [Integer]
primes_eratosthenes = 2 : 3 : sieve (tail primes_eratosthenes) 3 [] where
    sieve ~(p:ps) x fs = let q=p*p in
        foldr (flip minus) [x+2,x+4..q-2] [[y+s,y+2*s..q] | (s,y) <- fs]
        ++ sieve ps q ((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])

A quick and dirty benchmarking function:

benchPrimes :: Num a => [a] -> IO ()
benchPrimes f = do start <- getCurrentTime
                   print . sum $ take 10000 f
                   print . flip diffUTCTime start =<< getCurrentTime

Time to run the benchmarks.

main :: IO ()
main = do benchPrimes primes_eratosthenes
          benchPrimes primes_euler

The sieve of Eratosthenes runs in about 0.02 seconds, while Euler’s sieve takes around 6.6 seconds, which means this implementation of Euler’s Sieve is about 300-400 times slower. Clearly you don’t want to use this version in practice.