[Haskell-cafe] Re: MonadFix
apfelmus
apfelmus at quantentunnel.de
Sat Dec 22 16:38:48 EST 2007
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
More information about the Haskell-Cafe
mailing list