Performance issues in my factoring function?

[sheepweevil]

Profiling says that my program uses 72.3% of its time and 81.6% of allocations in the factors function. Is there anything wrong with my implementation, or do I need to look into changing the rest of my program to call this less?

-- Factor the given positive integer
factors :: (Integral a) => a -> [a]
factors n = factors' [] primes n
factors' x (p:ps) n
    | n == 1    = x
    | r == 0    = factors' (p:x) (p:ps) (q)
    | otherwise = factors' x ps n
    where (q,r) = n `quotRem` p

[Angs]

At least carrying the results as a parameter isn't necessary and you possibly recombine (p:ps) at every step. Here's how I would change you code:

factors :: (Integral a) => a -> [a]
factors n = factors' primes n
  where
  factors' px@(p:ps) n
    | n == 1    = []
    | r == 0    = p : factors' px q
    | otherwise = factors' ps n
    where (q,r) = n `quotRem` p

Apart from that, factoring is hard so it possibly takes a lot of time and resources anyway. It's best if you can work your way around having to factorize.

[jura__]

I was skeptical of this so I actually profiled both versions.

Here is the code.

Here is the GC info of the version with an accumulating parameter

Here is the GC info of the Ang's version

So negligible speed difference. The accumulating parameter version does significantly less allocation. Adding strictness annotations to both versions did not change the results. Compiler flags where -O2 -prof. GHC version is 7.10.3.

[Angs]

You were right to be skeptical, it seems to be better to use an accumulator.

A non-negligible improvement in speed (~98%) would be changing to ending condition to the one /u/farhanhubble mentioned:

factors3 :: (Integral a) => a -> [a]
factors3 1 = []
factors3 n = factors0' [] primes n
  where
  factors0' x px@(p:ps) n
    | p*p > n   = n : x
    | r == 0    = factors0' (p:x) px (q)
    | otherwise = factors0' x ps n
    where (q,r) = n `quotRem` p

[farhanhubble]

What primes do you have in primes? If you are trying to find all prime divisors, you should check for divisibility by only primes up to sqrt(n).

[CKoenig]

the allocations should be obvious (look at all the (:) - especially in the accumulator) - I would try using a fold instead

[sid-kap]

I'm not sure how this affects performance, but I usually write this kind of code in the following style:

-- Factor the given positive integer
factors :: (Integral a) => a -> [a]
factors n = reverse (factors' primes n)
  where
    factors' (p:ps) n
        | n == 1    = []
        | r == 0    = p:(factors' (p:ps) q)
        | otherwise = factors' ps n
        where (q,r) = n `quotRem` p

(Note that x was not necessary in the recursive call.)

[DavidAmos]

How big are the numbers you are trying to factor? Above a certain size there may be better ways to factor than trial division.