[Haskell-cafe] Re: MonadFix
apfelmus
apfelmus at quantentunnel.de
Fri Dec 21 08:24:26 EST 2007
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
More information about the Haskell-Cafe
mailing list