Joost Behrends wrote:
apfelmus writes:
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 .
No. One point in the introduction of DivIter is, that intsqrt dividend is stored there and only recomputed, when a new factor is found.
Yes, I'm sorry, it didn't occur to me that recomputing per actual prime factor (with multiplicities, i.e. p^5 counted 5 times) is better than recomputing per candidate factor (without multiplicities, i.e. p^5 counted only once).
And concerning my cycled lists of summands as [2,4] or [2,4,2,4,2,4,2,6,2,6]:
an easily computable function stepping through all primes can only be a function, which yields primes plus some more odd numbers. This is, what i tried.
Yes, this scheme was my intention, too. The list primes' doesn't need to (and indeed shouldn't) be a list of actual primes, just a good guess like primes' = 2:[3,5] primes' = 2:3:scanl (+) 5 (cycle [2,4]) or something with [2,4,2,4,2,4,2,6,2,6]. So, it's an infinite list of numbers that qualify as candidates for being a prime factor of n (which I called "prime candidates". Not a good name, since they don't need to be actual prime numbers.) What I want to say is that using such an infinite is a nice way to separate the generate-prime-factor-candidates-logic from the test-all-those-candidates-loop. It's not necessary to hard-code it with a predicate like
iterdivisors x | x == 0 = 3 | x == 1 = 5 | otherwise x = iterdivisors (x-1) + ((cycle [2,4]) !! x)
(which, in this particular form, is hopelessly inefficient) or special step functions like
d2 :: DivIter -> DivIter d2 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 2} |otherwise = found x d4 :: DivIter -> DivIter d4 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 4} |otherwise = found x d6 :: DivIter -> DivIter d6 x |dividend x `mod` divisor x > 0 = x { divisor = divisor x + 6} |otherwise = found x
divisions :: DivIter -> DivIter divisions y |or[divisor y == 3, divisor y == 5] = divisions (d2 y) |divisor y <= bound y = divisions (d6$d2$d6$d4$d2$d4$d2$d4 y) |otherwise = y
It's not even necessary to treat 2 in a special way like
twosect :: (Integer,[Integer]) -> (Integer,[Integer]) twosect m |odd (fst m) = m |even (fst m) = twosect (div (fst m) 2, snd m ++ [2])
does, the primes' list handles it all. Regards apfelmus