Am Freitag, 21. Dezember 2007 11:33 schrieb apfelmus:
> Joost Behrends wrote:
> > apfelmus writes:
> >> How about separating the candidate prime numbers from the recursion
> >>
> >> factorize :: Integer -> [Integer]
> >> factorize = f primes'
> >> where
> >> primes' = 2:[3,5..]
> >> f (p:ps) n
> >>
> >> | r == 0 = p : f (p:ps) q
> >> | p*p > n = [n]
> >> | otherwise = f ps n
> >>
> >> where
> >> (q,r) = n `divMod` p
> >
> > (besides: p < intsqrt n must stay, otherwise you have
> > the expensive p*p at every step)
>
> Huh? p < intsqrt n is evaluated just as often as p*p > n , with
> changing n . Why would that be less expensive? Btw, the code above
> test for r==0 first, which means that the following p*p > n is
> tested exactly once for every prime candidate p .
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. Since usually the number of prime factors is minuscule
compared to the number of candidates to be tested, that's indeed faster for
most inputs (in my tests ~28.5% less run time).
Some speed is also gained by using quotRem instead of divMod (pace, Henning, I
agree divMod is preferable, but quotRem is a primitive).
But of course, the most could be gained from a better algorithm.
>
> Regards,
> apfelmus
>
Cheers,
Daniel
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
