Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.javascript > #21226
| From | Stefan Weiss <krewecherl@gmail.com> |
|---|---|
| Newsgroups | comp.lang.javascript |
| Subject | Re: Strawmans prime sieve/filter |
| Date | 2013-09-09 13:45 +0200 |
| Organization | albasani.net |
| Message-ID | <l0kcd7$ol$1@news.albasani.net> (permalink) |
| References | <6e464d33-47e4-41b8-bfda-19511de92915@googlegroups.com> <l0jgv8$g2u$1@news.albasani.net> <a13c125d-e801-43e3-9e12-4355b40e22d2@googlegroups.com> |
On 2013-09-09 06:50, jonas.thornvall@gmail.com wrote:
> ???Can you do a faster better probalistic sieve reading in all
> primes less than 20 millions to an array, i did a little check with others.???
>
> I really look for other noneprobalistic to compare with.
>
> Sieve of Eratosthenes is it not spending to much memory for
> javascript?
>
> You would need to hold 19/20*20000000 where 19/20 is 8 digit 64 bit.
>
> So 19/20*20000000*64=1216000000 bits=152000000 byte=152 MB well it
> seem feasible.
>
> But probably 1/19*20000000*64=1052631 bits=131578 bytes=0,13 MB is
> better, and what worse is for Eratosthenes his algorithm is greedy as
> you go try check primes up 200 million you will have trouble running it
> at your computer without writing to disk. At 2 billion it will be
> impossible. So instead of 19/20 of the naturals upto 200 millions you
> will have to store alot more and you will come closer and closer to
> 20/20 as the numbers raise.
>
> But strawmans approach on the other side just get better, it will be
> alot less then 1/19 for 200 millions. And at real big numbers it becomes
> real beautiful.
>
> But as i said you need a 4 TB disk, 16 GB of memory to really notice
> how great strawmans approach is.
This isn't really my specialty, and I can't give an answer about the
most efficient way to generate prime numbers. I also didn't realize you
were going to calculate 2 billion of them. It looks like Eratosthenes is
not the right way to go for higher numbers.
The reason I asked for your purpose is that, right now, the program
collects prime numbers (with memory usage growing steadily), but you
never read them after putting them in the array. If you just wanted to
know if a number is prime, or find the highest prime number near another
number, there are more efficient ways to do that.
And I'm not sure where the 4 TB comes from. As a test, I just calculated
the numbers up to 200M. There are 11078937 of them, which would require
~44MB of storage (using 4 bytes to store a number). If I went the full
2B, the necessary disk storage would still be less than half a gig. RAM
is a bigger problem, because of the overhead from the scripting engine.
The test took a little over 3 minutes with Node, using the attached
code. It follows your basic approach, minus the function call.
----------------------------------------------------------------
var MAX = 200000000;
var primes = [2];
var t0 = +new Date();
outer:
for (var num = 3; num < MAX; ++num) {
for (var i = 0, stop = Math.sqrt(num) + 1; primes[i] < stop; ++i) {
if (!(num % primes[i])) {
continue outer;
}
}
primes.push(num);
}
console.log("highest prime: " + primes[primes.length - 1]);
console.log("number of primes: " + primes.length);
console.log("time: " + (+new Date() - t0) + " ms");
----------------------------------------------------------------
Like I said, I'm not an expert, so this can probably be improved quite a
bit. One interesting effect was that eliminating all even numbers before
calculating the square root had a negative effect on performance (in Node).
For raw speed, you should also consider a different language than JS.
- stefan
Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 19:09 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 05:57 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 21:22 -0700
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 21:50 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 13:45 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 06:33 -0700
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 06:41 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 18:37 +0200
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 19:54 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 12:46 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 23:25 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 14:58 -0700
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-11 10:39 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-11 02:54 -0700
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-11 12:59 +0200
Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-12 20:17 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 02:27 +0200
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-13 04:03 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-12 19:30 -0700
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 05:15 +0200
Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-13 05:27 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 08:26 -0700
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 08:15 -0700
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 19:13 +0200
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 17:15 -0700
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 01:55 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 04:20 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 06:16 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 12:10 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 12:49 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 15:23 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 21:51 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-15 03:32 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 04:07 +0100
Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-15 18:57 +0200
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 19:24 +0100
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-14 20:37 -0700
Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-14 19:38 +0100
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 22:26 -0700
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-10 22:48 +0100
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-11 00:36 -0700
Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-11 14:47 +0100
Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 22:33 -0700
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2013-09-09 21:08 -0700
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2013-09-10 08:52 -0700
Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-10 19:08 +0100
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-04-10 22:02 -0700
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-05-02 15:39 -0700
Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-05-02 15:54 -0700
csiph-web