wa123

You are here:

	FireBoard	Forum Threaded View Rules Help

Welcome, Guest
Please Login or Register. Lost Password?

FireBoard

forum

others

nt factor FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)) (1 viewing) (1) Guests

Favoured: 0

Page:

<< Start < Prev 1 2 3 4 5 Next > End >>

TOPIC: nt factor FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))

Forum Tools

#7892

Steve (Visitor)

nt factor FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))
twice as fast as the haskellwiki code (here) and uses only 1/3 the memory. For the record:

Report to moderator Logged

Logged

The administrator has disabled public write access.

#7893

Will Ness (Visitor)

nt factor FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list This e-mail address is being protected from spam bots, you need JavaScript enabled to view it http://www.haskell.org/mailman/listinfo/haskell-cafe

Report to moderator Logged

Logged

The administrator has disabled public write access.

#7894

Daniel Fischer (Visitor)

nt factor FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))

Her article even adds the primes into the PQ prematurely itself, as soon as the prime is discovered (she fixes that in her ZIP package). With the PQ keeping these prematurely added elements deep inside its guts, the problem might not even manifest itself immediately, but the memory blow-up would eventually hit the wall (having the PQ contain all the preceding primes, instead of just those below the square root of a limit - all the entries above the square root not contributing to the calculation at all). And what we're after here is the insight anyway. Skipping steps of natural development does not contribute to garnering an insight. Most prominent problem with Turner's /code/ _specification_, is the premature start ups, and divisibility testing of primes (as Melissa O'Neill's analysis shows). Fix one, and you get Postponed Filters (which should really be used as a basis reference point for all the rest). Fix the other - and you've got the Euler's sieve: primes = 2: 3: sieve (tail primes) [5,7..] where sieve (p

s) xs = h ++ sieve ps [t `minus` tail [p*p, p*p+2*p..]] where (h,~(_:t)) = span (< p*p) xs Clear, succinct, and plenty efficient for an introductory textbook functional lazy code, of the same order of magnitude performance as PQ code on odds only. Now comparing the PQ performance against _that_ would only be fare, and IMO would only add to its value - it is faster, has better asymptotics, and is greatly amenable to the wheel optimization right away. prime only with its multiples (plus the next composite in the PQ version). In Turner's algorithm, we match each prime with all smaller primes (and each composite with all primes <= its smallest prime factor, but that's less work than the primes). That gives indeed a complexity of O(pi(bound)^2). In the postponed filters, we match each prime p with all primes <= sqrt p (again, the composites contribute less). I think that gives a complexity of O(pi(bound)^1.5*log (log bound)) or O(n^1.5*log (log n)) for n primes produced. Empirically, it was always _below_ 1.5, and above 1.4 , and PQ/merged multiples removal around 1.25..1.17 . I should really stop doing those calculations in my head, it seems I'm getting too old for that. Doing it properly, on paper, the cost for identifying p_k is
... read more »

_______________________________________________ Haskell-Cafe mailing list This e-mail address is being protected from spam bots, you need JavaScript enabled to view it http://www.haskell.org/mailman/listinfo/haskell-cafe

Report to moderator Logged

Logged

The administrator has disabled public write access.

#7895

Will Ness (Visitor)

nt factor FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))

(again, the composites contribute less). I think that gives a complexity of O(pi(bound)^1.5*log (log bound)) or O(n^1.5*log (log n)) for n primes produced. Empirically, it was always _below_ 1.5, and above 1.4 , and PQ/merged multiples removal around 1.25..1.17 . I should really stop doing those calculations in my head, it seems I'm getting too old for that. Doing it properly, on paper, the cost for identifying p_k is pi(sqrt p_k) [trial division by all primes less than
... read more »

Report to moderator Logged

Logged

The administrator has disabled public write access.

#7896

Will Ness (Visitor)

nt factor FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))
.. and that is of course a matter of personal preference. A genius is perfectly capable of making big leaps across chasms. Heck they might even be able to fly _______________________________________________ Haskell-Cafe mailing list This e-mail address is being protected from spam bots, you need JavaScript enabled to view it http://www.haskell.org/mailman/listinfo/haskell-cafe

Report to moderator Logged

Logged

The administrator has disabled public write access.

#7897

Daniel Fischer (Visitor)

nt factor FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))

Using a feeder, i.e. primes = 2:3.sieve feederprimes [5, 7 .. ], where feederprimes are generated as above, to reduce memory pressure and GC impact, that fits pretty well with my measurements of the time to find p_k for several k between 500,000 and 20,000,000. The quesion of a memory blowup with the treefolding merge still remains. For some reason using its second copy for a feeder doesn't reduce the memory (as reported by standalone compiled program, GHCi reported values are useless) - it causes it to increase twice..... I have a partial solution. The big problem is that the feeder holds on to the beginning of comps while the main runner holds on to a later part. Thus the entire segment between these two points must be in memory. So have two lists of composites (yeah, you know that, but it didn't work so far). But you have to force the compiler not to share them: enter -fno-cse. The attached code does that (I've also expanded the wheel), it reduces the memory requirements much (a small part is due to the larger
... read more »

V13Primes.hs
3K
Download

_______________________________________________ Haskell-Cafe mailing list This e-mail address is being protected from spam bots, you need JavaScript enabled to view it http://www.haskell.org/mailman/listinfo/haskell-cafe

Report to moderator Logged

Logged

The administrator has disabled public write access.

Page:
<< Start < Prev 1 2 3 4 5 Next > End >>

Forum List

forum

others

get the latest posts directly to your desktop

Short News

The sea at all help

For several years, a hit in European resorts is a thalasso therapy. This medical treatments and cosmetic advantages of using sea water, salt and algae. Sea beauty salon you can arrange in the bathroom. Put the bath bag of sea salt and immerse yourself in it for half an hour .

Treat yourself to a little sunshine

In spite of the fall weather, you can make your skin has a nice, peach color. Such as in summer, for the miss. Most Polish women loves to sunbathe, I really love the bronze. Why? Since even slightly tanned body looks slender and prettier. It makes you improve mood. Aware that you look more attractive, once you added confidence, just feel happier.

Perfect manicure

Each carefully constructed hands adds beauty. Are both fashionable nails in luscious color and adorned with delicate French manicure. Hands are very "eloquent". Reveal the type of work, health and lifestyle. That the hands were well cared for, require regular treatment. Well done manicure not only adorned with nails, but also help solve some problems. Hide uneven or the plate, deflecting attention from the kins. Instead of cosmetic surgery can make themselves at home - at a convenient time for us and much cheaper.

Green spa

We start from a fifteen-minute bath in a bathtub filled with warm milk, yoghurt and honey dissolved in them, then peeling again using an extract of herbs. Sam puts on his feet smell. And yet, we face wraps with honey and massage using selected essential oil.