[Haskell-cafe] Re: MonadFix
Joost Behrends
webmaster at h-labahn.de
Fri Dec 21 09:08:32 EST 2007
apfelmus <apfelmus <at> quantentunnel.de> 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.
And concerning my cycled lists of summands as [2,4] or [2,4,2,4,2,4,2,6,2,6]:
There simply is no function easily yielding primes for your list primes'.
If we use the sieve of Eratosthenes, we must have the whole list
of found primes up to a certain point in memory for proceeding
beyond that certain point. We cannot gain anything by lazy evaluation.
Not with the sieve of Eratosthenes - and there is no other reliable mechanism.
What is more - if we have a list of primes, possibly up to 1,000,000 - what
shall we do for efficiently yielding divisors beyond 1,000,000 ? We would have
to fall back to x -> x+2.
Thus 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. Alternating addition of 2 and 4 to the current divisor can be continued
beyond any bound. And i am not forced to use any of the longer list of
summands - indeed, which of these lists to choose should be adapted to the
size of the number to decompose.
Concerning the State monad:
Yes, i was wrong here completely. Ryan Ingram gave detailed instructions why.
And Albert Y.C. Lai pointed out, that normal recursion for division works
tail recursive too. It didn't on my computer - perhaps i misconfigured
ghci (where i tried it). Let us close discussion of this point.
Cheers, Joost
More information about the Haskell-Cafe
mailing list