[Haskell-cafe] Re: MonadFix

[apfelmus]

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