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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
