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

#7886

Daniel Fischer (Visitor)

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

Am Dienstag 29 Dezember 2009 14:58:10 schrieb Will Ness: If I realistically needed primes generated in a real life setting, I'd probably had to use some C for that. If you need the utmost speed, then probably yes. If you can do with a little less, my STUArray bitsieves take about 35% longer than the equivalent C code and are roughly eight times faster than ONeillPrimes. I can usually live well with that. Wow! That's fast! (that's the code from haskellwiki's primes page, right?) No, it's my own code. Nothing elaborate, just sieving numbers 6kï¿½1, 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.

#7887

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.

#7888

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.

#7889

Daniel Fischer (Visitor)

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

especially the claim that going by primes squares is a pleasing but minor optimization , Which it is not. It is a major optimisation. It reduces the algorithmic complexity *and* reduces the constant factors significantly. D'oh! Thinko while computing sum (takeWhile (<= n) primes) without paper. It doesn't change the complexity, and the constant factors are reduced far less than I thought. The huge performance differences I had must have been due to cache misses (unless you use a segmented sieve, starting at the square reduces the number of cache misses significantly).

_______________________________________________ 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.

#7890

Will Ness (Visitor)

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

Am Dienstag 29 Dezember 2009 20:16:59 schrieb Daniel Fischer: especially the claim that going by primes squares is a pleasing but minor optimization , Which it is not. It is a major optimisation. It reduces the algorithmic complexity *and* reduces the constant factors significantly. D'oh! Thinko while computing sum (takeWhile (<= n) primes) without paper. It doesn't change the complexity, and the constant factors are reduced far less than I thought. I do not understand. Turner's sieve is primes = sieve [2..] where sieve (p

s) = p : sieve [x | x<-xs, x `mod` p /= 0] and the Postponed Filters is primes = 2: 3: sieve (tail primes) [5,7..] where sieve (p

s) xs = h ++ sieve ps [x | x<-t, x `rem` p /= 0] where (h,~(_:t)) = span (< p*p) xs Are you saying they both exhibit same complexity? I was under impression that the first shows O(n^2) approx., and the second one O(n^1.5) (for n primes produced). _______________________________________________ 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.

#7891

Daniel Fischer (Visitor)

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

primes produced). In Turner/postponed filters, things are really different. Actually, Ms. O'Neill is right, it is a different algorithm. In the above, we match each 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.

_______________________________________________ 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.