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