CODEWITHSUNDEEP
performancehaskellprimesfactorsfactorization
Code-Apprentice
Code-Apprentice

Reputation: 83517

List of divisors of an integer n (Haskell)

I currently have the following function to get the divisors of an integer:

-- All divisors of a number
divisors :: Integer -> [Integer]
divisors 1 = [1]
divisors n = firstHalf ++ secondHalf
    where firstHalf = filter (divides n) (candidates n)
          secondHalf = filter (\d -> n `div` d /= d) (map (n `div`) (reverse firstHalf))
          candidates n = takeWhile (\d -> d * d <= n) [1..n]

I ended up adding the filter to secondHalf because a divisor was repeating when n is a square of a prime number. This seems like a very inefficient way to solve this problem.

So I have two questions: How do I measure if this really is a bottle neck in my algorithm? And if it is, how do I go about finding a better way to avoid repetitions when n is a square of a prime?

Upvotes: 3

Views: 2550

Answers (2)

Will Ness
Will Ness

Reputation: 71070

You needn't test all the elements of reversed second half. You know that if the square root is present, it is the head element there:

          secondHalf = let (r:ds) = [n `div` d | d <- reverse firstHalf]
                       in [r | n `div` r /= r] ++ ds

This assumes n is positive.

A simpler way to handle the sqrt of a number differently is to handle it separately:

divs n = 
  let 
    r = floor $ sqrt $ fromIntegral n 
    (a,b) = unzip $ (1,n) : [(d, q) | d<-[2..r-1], let (q,r)=quotRem n d, r==0]
  in
    if r*r==n
      then a ++ r : reverse b
      else a ++ reverse b

That way we get the second half for free, as a part of producing the first half.

But this could hardly be a bottleneck in your application because the algorithm itself is inefficient. It is usually much faster to generate the divisors from a number's prime factorization. Prime factorization by trial division can be much quicker because we divide out each divisor as it is found, reducing the number being factorized and thus the amount of divisors that are tried (up to the reduced number's square root). For example, 12348 = 2*2*3*3*7*7*7 and no factor above 7 is tried in the process of factorization, whereas in divs 12348 the number 12348 is divided by all numbers from 2 to 110:

factorize n = go n (2:[3,5..])    -- or:  (go n primes)  where
   where                          --  primes = 2 :
     go n ds@(d:t)                --   filter (null.tail.factorize) [3,5..]
        | d*d > n    = [n]
        | r == 0     =  d : go q ds
        | otherwise  =      go n t
            where  (q,r) = quotRem n d

Upvotes: 1

Axioplase
Axioplase

Reputation: 183

To mesure where the bottleneck is, put the three auxiliary definitions (firstHalf, secondHalf, candidates) at the top level, and run your code with the profiler on: ghc -prof --make divisors.hs ./divisors 100 +RTS -p -RTS

Also, you know that the biggest candidate is sqrt n, so instead of doing that many multiplications d*d, just consider [1..floor (sqrt n)]

For better algorithms, you should take a maths book, for it's not a haskell related question… Things you can consider: if "a divides b", then for all divisor d of a, d divides b as well. You'll want to use memoization or dynamic programming to avoid checking multiple times if a given d divides b (for example, if 15 and 27 divide b, then you need to mathematically check only once that 3 divides b. The other times, you just see if 3 is in your table of divisors of b).

Upvotes: 2

Related Questions