[Haskell-cafe] haskell.org

[Ertugrul Söylemez]

> Leave the example. But change the blurb to say:
> This is inspired by the Sieve of Eratosthenes. For a true Sieve of
> Eratosthenes, see [link to O'Neil].

Unfortunately trial division is in no way inspired by the SoE.  It's
about the most bruteforcy way to find primes.  Basically all it does is
to perform a full primality test for every single candidate.  The only
advantage of the example code is that it uses laziness and sharing to
keep a list of the primes found so far to make this trial division
slightly less expensive.

In fact it can be improved quadratically and still wouldn't be a sieve.
On my current machine in 1 second the following code finds the first
60000 primes while the homepage example finds only 3700 primes, both
specialised to [Int]:

    primes = 2 : filter isPrime [3..]
        where
        isPrime x =
            all (\p -> mod x p /= 0) .
            takeWhile (\p -> p*p <= x) $ primes

The SoE on the other hand exploits the global structure of the
distribution of a prime's multiples.  Without any division at all it
simply deduces that after each crossing operation the smallest remaining
integer *must* be prime.

This is pretty much the same improvement the quadratic sieve makes to
Dixon's factoring method and the number field sieve makes to the index
calculus method.  It gets rid of primality tests and uses the
distributions of multiples.  Thus it finds lots and lots of relations in
one go rather than testing every single relation.  It would be equally
wrong to call Dixon's method or index calculus sieves.

How about simply changing `sieve` to `trialDiv`?  It's not that I don't
like the given example, because it gives a very small use case for
laziness that is difficult enough to reproduce in an eagerly evaluated
language.  And with the new name for the local function it stops turning
the stomach of a number theoretician.


Greets,
Ertugrul
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 472 bytes
Desc: not available
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150421/391293f3/attachment.sig>