Daniel Fischer wrote:
apfelmus writes:
| r == 0 = p : f (p:ps) q | p*p > n = [n] | otherwise = f ps n
However, when you do the sensible thing (which Joost did) and have the intsqrt a parameter of the function, like in
factorize :: Integer -> [Integer] factorize n = f n (intsqrt n) primes' where primes' = something more or less clever here f m sr (p:ps) | r == 0 = p:f q (intsqrt q) (p:ps) | p > sr = if m == 1 then [] else [m] | otherwise = f m sr ps where (q,r) = m `quotRem` p
, then you only have the expensive intsqrt for each prime factor, and the test for each candidate is only one comparison instead of one multiplication and one comparison.
Ah thanks, sorry for not seeing it earlier. My thinking was that intsqrt q is calculated multiple times (for q , q/p, q/p^2, ...) per prime candidate p when n is divisible by a large power of p . But I didn't see that, in return, intsqrt q stays the same for candidates that aren't factors of n . Compared to that, p*p is only calculated once per candidate, but then for every candidate. The former is clearly preferable to the latter. In fact, thanks to lazy evaluation, the above code (test r==0 before p > sr) evaluates intsqrt q at most once per prime candidate and thus combines both advantages. Regards, apfelmus