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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
