Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #21215 > unrolled thread

Strawmans prime sieve/filter

Back to article view | Back to comp.lang.javascript

Contents

  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

Page 1 of 3  [1] 2 3  Next page →

#21215 — Strawmans prime sieve/filter

It writes all 1 270608 primes less then 20 000 004 into an array in 17 seconds by comparing the natural with the value read into the array, but bigger then 20 million there is to many primes to compare with and it gets slow. I only compare the values in prime array upto square of the natural.

That makes 1,337942150529510281691914422072e-5 per prime (i know they are small)
It's a weird algorithm because without the previous primes it does nothing, but i could write them to a 4 TB HDD but would i gain something?

But i was thinking the prime get less and less so for very big primes it will skip alot of trial division just using primes.

Can i improve this code further without probalistic approach.
Here is the code.  

<!DOCTYPE html>
<html>
<head></head>

<script type="text/javascript">

var prime = new Array();
prime[0] = 2;
prime[1] = 3;
prime[2] = 5;
prime[3] = 7;




function isPrime(n)
{
   p = true;
   k = 0;
   test = Math.sqrt(n) + 1;
   //document.write("Sqrt=",test,"<BR>");
   test = Math.round(test);
   //document.write("Roundedsqrt=",test,"<BR>");
   while (test>= prime[k])
   {
   // document.write("N=",n," MOD",prime[k],"<BR>");
      if  ((n % prime[k]) == 0) { p = false; break; document.write("break"); }
      k ++ ;
   }
   if (p == true)
   {
      t = prime.length;
      prime[t] = n;
   }
}




//*MAIN*

var start = new Date().getTime();
y=1;
n = 4;
while(n < 20000000)
{
 n=y*10+1;
 isPrime(n);
 n=y*10+3;
 isPrime(n);
 n=y*10+7;
 isPrime(n);
 n=y*10+9;
 isPrime(n);
 y++;
   
}
var end = new Date().getTime();
var time = end - start;
alert('Execution time: ' + time);
x=prime.length;
document.write("Last prime in array=",prime[x-1]," There is ",x," primes in array ->finished<BR>")
//x=0;
//while (x<prime.length){document.write(prime[x],","); x++;}
</script>
<body>
</body>
</html>

[toc] | [next] | [standalone]

#21217

On 2013-09-09 04:09, jonas.thornvall@gmail.com wrote:
> It writes all 1 270608 primes less then 20 000 004 into an array in
> 17 seconds by comparing the natural with the value read into the array, but
> bigger then 20 million there is to many primes to compare with and it
> gets slow. I only compare the values in prime array upto square of the
> natural.

I didn't look very closely, but from what I can see, you're not using
the sieve at all, you're just doing dumb trial division.

Read this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Algorithms aside, is there a point to what you're doing, or is it just
recreational? No disrespect, I also like mathematical puzzles and tasks,
but if you actually need the prime numbers for something, you could just
download them.

- stefan

[toc] | [prev] | [next] | [standalone]

#21218

Den måndagen den 9:e september 2013 kl. 05:57:27 UTC+2 skrev Stefan Weiss:
> On 2013-09-09 04:09, jonas.thornvall@gmail.com wrote:
> 
> > It writes all 1 270608 primes less then 20 000 004 into an array in
> 
> > 17 seconds by comparing the natural with the value read into the array, but
> 
> > bigger then 20 million there is to many primes to compare with and it
> 
> > gets slow. I only compare the values in prime array upto square of the
> 
> > natural.
> 
> 
> 
> I didn't look very closely, but from what I can see, you're not using
> 
> the sieve at all, you're just doing dumb trial division.
> 
> 
> 
> Read this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
> 
> 
> 
> Algorithms aside, is there a point to what you're doing, or is it just
> 
> recreational? No disrespect, I also like mathematical puzzles and tasks,
> 
> but if you actually need the prime numbers for something, you could just
> 
> download them.
> 
> 
> 
> - stefan

It is recreational.

Well it is a strawman sieve, as in a filter? I thought that was what a sieve was? Certainly there is more sieves then Eratosthenes isn't there a Newton sieve?


I only trial division with *primes*, those are primes the upto the SQRT of the natural. No other trial division needed.

And before i start by reducing the range of the naturals by 60 percent in main.
So the script start with only 40% of all naturals, creating an array with primes and trial divide the elements of the array with the natural coming up next so it would need a 4 TB HDD to store primes and a 16 GB memory to read in to work with primes a little bigger. To be honest the approach probably more for some big organisation storing all consecutive primes and want to know the next one in smallest amount of time. As the primes thin out there will be gains?

Interestingly enough it seem by just chosing a higher base you can reduce more, i just asked the guys at sci.math what the reductio ratio would be using base 16 or 2048. Because each base will have its own reductio ratio.

[toc] | [prev] | [next] | [standalone]

#21219

Den måndagen den 9:e september 2013 kl. 05:57:27 UTC+2 skrev Stefan Weiss:
> On 2013-09-09 04:09, jonas.thornvall@gmail.com wrote:
> 
> > It writes all 1 270608 primes less then 20 000 004 into an array in
> 
> > 17 seconds by comparing the natural with the value read into the array, but
> 
> > bigger then 20 million there is to many primes to compare with and it
> 
> > gets slow. I only compare the values in prime array upto square of the
> 
> > natural.
> 
> 
> 
> I didn't look very closely, but from what I can see, you're not using
> 
> the sieve at all, you're just doing dumb trial division.
> 
> 
> 
> Read this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
> 
> 
> 
> Algorithms aside, is there a point to what you're doing, or is it just
> 
> recreational? No disrespect, I also like mathematical puzzles and tasks,
> 
> but if you actually need the prime numbers for something, you could just
> 
> download them.
> 
> 
> 
> - stefan

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

[toc] | [prev] | [next] | [standalone]

#21226

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

[toc] | [prev] | [next] | [standalone]

#21228

Den måndagen den 9:e september 2013 kl. 13:45:42 UTC+2 skrev Stefan Weiss:
> 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

Well i just think that being 10 times faster then  Eratosthenes sieve for ***small numbers, that is 10 million*** quite extrordinary . And also it is easy to see that  Eratosthenes need to store 18/19= 95% of all values upto 20 000000 and the storage ratio just grow with bigger numbers until it becume almost as big as the total searchspace.

For strawmans sieve it is only 1/19 = 5% of searchspace to store upto 20 000000, and the needed amount of storage ratio is decreasing ***steadily***.

Maybe strawman should have his algorithm in an algorithm book.

[toc] | [prev] | [next] | [standalone]

#21229

Den måndagen den 9:e september 2013 kl. 13:45:42 UTC+2 skrev Stefan Weiss:
> 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

Regarding removing numbers, that is *NOT* what i do. What i do is a jump or skipjack each base has its own set of values not necessary to test for base 10 they are.

For base 10 we jump everything with
0+x*10
2+x*10
4+x*10
5+x*10
8+x*10
0+x*10

Thus we only need test a subset, and the subset for base 10 is 40%.
while(n < 20000000) 
{ 
 n=y*10+1; 
 isPrime(n); 
 n=y*10+3; 
 isPrime(n); 
 n=y*10+7; 
 isPrime(n); 
 n=y*10+9; 
 isPrime(n); 
 y++; 
} 

[toc] | [prev] | [next] | [standalone]

#21231

On 2013-09-09 15:41, jonas.thornvall@gmail.com wrote:
> Den måndagen den 9:e september 2013 kl. 13:45:42 UTC+2 skrev Stefan Weiss:
>> One interesting effect was that eliminating all even numbers before
>> calculating the square root had a negative effect on performance (in Node).
...
> Regarding removing numbers, that is *NOT* what i do. What i do is a
> jump or skipjack each base has its own set of values not necessary to
> test for base 10 they are.
> 
> For base 10 we jump everything with
> 0+x*10
> 2+x*10
> 4+x*10
> 5+x*10
> 8+x*10
> 0+x*10
> 
> Thus we only need test a subset, and the subset for base 10 is 40%.
> while(n < 20000000) 
> { 
>  n=y*10+1; 
>  isPrime(n); 
>  n=y*10+3; 
>  isPrime(n); 
>  n=y*10+7; 
>  isPrime(n); 
>  n=y*10+9; 
>  isPrime(n); 
>  y++; 
> } 

But that's basically the same thing as ignoring numbers divisible by 2
or 5. The loop would filter those out right at the start anyway, but it
has to calculate the square root of the number first. Maybe
multiplication + addition is faster than a modulo operation, I didn't
test that. On the other hand, the base+offset form requires an isPrime()
function, and when you're talking millions and billions of iterations,
the function call overhead is noticable.

I made a mistake in my first quick test - filtering out the small primes
does increase performance (a little). See the amended test script at the
end. I'm sure this is still far from optimal.

By the way, if you use your offsets, you don't have to test divide the
number through all the previous primes, you can start the loop at index
1, because prime[0] is 2.

Calculating primes up to 10M shows that the inline loop is indeed a bit
faster than calling isPrime().

$ for i in `seq 0 9`; do echo -n "$i: "; node stefan.js; done
0: time: 2135 ms
1: time: 2133 ms
2: time: 2143 ms
3: time: 2127 ms
4: time: 2138 ms
5: time: 2131 ms
6: time: 2138 ms
7: time: 2128 ms
8: time: 2138 ms
9: time: 2134 ms

$ for i in `seq 0 9`; do echo -n "$i: "; node jonas.js; done
0: time: 2685 ms
1: time: 2674 ms
2: time: 2654 ms
3: time: 2644 ms
4: time: 2648 ms
5: time: 2647 ms
6: time: 2685 ms
7: time: 2675 ms
8: time: 2642 ms
9: time: 2636 ms

----------------------------------------------------------------
var MAX = 10000000;
var primes = [2, 3, 5, 7];
var t0 = +new Date();

outer:
for (var num = 11; num < MAX; ++num) {
    if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0) {
        continue;  // shortcut (not really necessary)
    }
    for (var i = 3, stop = Math.sqrt(num) + 1; primes[i] < stop; ++i) {
        if (num % primes[i] == 0) {
            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");
----------------------------------------------------------------


- stefan


PS: Please trim your quotes.

[toc] | [prev] | [next] | [standalone]

#21232

On 2013-09-09 15:41, jonas.thornvall@gmail.com wrote:
> each base has its own set of values not necessary to test

By the way, that's an incorrect general assumption.

With a chunk size (or "base") of 10, there's an obvious pattern: skip
every second number and skip the fifth number.

With other chunk sizes, you may not get such regular offsets:

Chunk size 7:
  offset 0 |   0   *7     14    21    28    35
  offset 1 |   1    8     15    22   *29    36
  offset 2 |  *2    9     16   *23    30   *37
  offset 3 |  *3    10   *17    24   *31    38
  offset 4 |   4   *11    18    25    32    39
  offset 5 |  *5    12   *19    26    33    40
  offset 6 |   6   *13    20    27    34   *41

The only offset you don't have to test for this "base" is 0 (after the
second column).

IMHO, the word "base" is a poor choice. At first, I thought you meant
base in the sense of "radix" for a numeral system. (That wouldn't work,
because primes are primes, regardless of the base used).

- stefan

[toc] | [prev] | [next] | [standalone]

#21233

Den måndagen den 9:e september 2013 kl. 19:54:05 UTC+2 skrev Stefan Weiss:
> On 2013-09-09 15:41, jonas.thornvall@gmail.com wrote:
> 
> > each base has its own set of values not necessary to test
> 
> 
> 
> By the way, that's an incorrect general assumption.
> 
> 
> 
> With a chunk size (or "base") of 10, there's an obvious pattern: skip
> 
> every second number and skip the fifth number.
> 
> 
> 
> With other chunk sizes, you may not get such regular offsets:
> 
> 
> 
> Chunk size 7:
> 
>   offset 0 |   0   *7     14    21    28    35
> 
>   offset 1 |   1    8     15    22   *29    36
> 
>   offset 2 |  *2    9     16   *23    30   *37
> 
>   offset 3 |  *3    10   *17    24   *31    38
> 
>   offset 4 |   4   *11    18    25    32    39
> 
>   offset 5 |  *5    12   *19    26    33    40
> 
>   offset 6 |   6   *13    20    27    34   *41
> 
> 
> 
> The only offset you don't have to test for this "base" is 0 (after the
> 
> second column).
> 
> 
> 
> IMHO, the word "base" is a poor choice. At first, I thought you meant
> 
> base in the sense of "radix" for a numeral system. (That wouldn't work,
> 
> because primes are primes, regardless of the base used).
> 
> 
> 
> - stefan

I Think you are wrong Stefan using base 11.
We can skip x*11*1. But of course we lose others.

What i say is there are more optimal bases where we can reduce the subset even more. There could even be dofferemt operations and cubic numbersystems that could exploit this. We could chose base 30 or 60 to add a more selective subset. Only the fantasy and the operational cost sets the limit for sieving out an optimal subset.

[toc] | [prev] | [next] | [standalone]

#21235

On 2013-09-09 21:46, jonas.thornvall@gmail.com wrote:
> Den måndagen den 9:e september 2013 kl. 19:54:05 UTC+2 skrev Stefan Weiss:
>> On 2013-09-09 15:41, jonas.thornvall@gmail.com wrote:
>> > each base has its own set of values not necessary to test
>> 
>> By the way, that's an incorrect general assumption.
>> 
[...]
> I Think you are wrong Stefan using base 11.
> We can skip x*11*1. But of course we lose others.

11 is a really bad example: you can still only skip a single offset.
You'll get that for all prime-sized "bases". If you want a useful base,
you should instead multiply the first n primes:

2*3     = 6   -> you can skip every 2nd and 3rd offset
2*3*5   = 30  -> you can skip every 2nd, 3rd and 5th offset
2*3*5*7 = 210 -> you can skip every 2nd, 3rd, 5th and 7th offset

And so on.

Here's a great idea: you could automate this process for higher chunk
sizes... put the prime numbers in an array and loop over it to
automatically skip them. And then we're right back where we started ;-)

> What i say is there are more optimal bases where we can reduce the
> subset even more. There could even be dofferemt operations and cubic
> numbersystems that could exploit this. We could chose base 30 or 60 to
> add a more selective subset. Only the fantasy and the operational cost
> sets the limit for sieving out an optimal subset.

You lost me at "cubic numbersystems", I have no idea what that is.
I'm still not convinced that skipping offsets like this actually
improves performance. It didn't in my tests.

Again, please trim your quotes.

- stefan

[toc] | [prev] | [next] | [standalone]

#21236

Den måndagen den 9:e september 2013 kl. 23:25:21 UTC+2 skrev Stefan Weiss:
> On 2013-09-09 21:46, jonas.thornvall@gmail.com wrote:
> 
> > Den måndagen den 9:e september 2013 kl. 19:54:05 UTC+2 skrev Stefan Weiss:
> 
> >> On 2013-09-09 15:41, jonas.thornvall@gmail.com wrote:
> 
> >> > each base has its own set of values not necessary to test
> 
> >> 
> 
> >> By the way, that's an incorrect general assumption.
> 
> >> 
> 
> [...]
> 
> > I Think you are wrong Stefan using base 11.
> 
> > We can skip x*11*1. But of course we lose others.
> 
> 
> 
> 11 is a really bad example: you can still only skip a single offset.
> 
> You'll get that for all prime-sized "bases". If you want a useful base,
> 
> you should instead multiply the first n primes:
> 
> 
> 
> 2*3     = 6   -> you can skip every 2nd and 3rd offset
> 
> 2*3*5   = 30  -> you can skip every 2nd, 3rd and 5th offset
> 
> 2*3*5*7 = 210 -> you can skip every 2nd, 3rd, 5th and 7th offset
> 
> 
> 
> And so on.
> 
> 
> 
> Here's a great idea: you could automate this process for higher chunk
> 
> sizes... put the prime numbers in an array and loop over it to
> 
> automatically skip them. And then we're right back where we started ;-)
> 
> 
> 
> > What i say is there are more optimal bases where we can reduce the
> 
> > subset even more. There could even be dofferemt operations and cubic
> 
> > numbersystems that could exploit this. We could chose base 30 or 60 to
> 
> > add a more selective subset. Only the fantasy and the operational cost
> 
> > sets the limit for sieving out an optimal subset.
> 
> 
> 
> You lost me at "cubic numbersystems", I have no idea what that is.
> 
> I'm still not convinced that skipping offsets like this actually
> 
> improves performance. It didn't in my tests.
> 
> 
> 
> Again, please trim your quotes.
> 
> 
> 
> - stefan

Bases is basicly about partitioning naturals into a certain kind of geometry, basicly it is the numberline Using different signs and subgrouping.

The numbersystem must not necessarily adhere to partitioning of a numberline. There is other kinds of geometris with other types of relations then the simple multiple.

[toc] | [prev] | [next] | [standalone]

#21260

Stefan Weiss wrote:
 
> […] I just calculated the [prime] 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. […]

The relevant ECMAScript implementations support only one numeric data type, 
Number, which is an implementation of IEEE-754 double-precision floating-
point values.  Each such value requires 64 bits of storage (1 sign bit, 11 
exponent bits, and 52 mantissa bits), or _8_ bytes whereas each byte 
consists of 8 bits.

-- 
PointedEars

Twitter: @PointedEars2
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#21261

Den onsdagen den 11:e september 2013 kl. 10:39:33 UTC+2 skrev Thomas 'PointedEars' Lahn:
> Stefan Weiss wrote:
> 
>  
> 
> > […] I just calculated the [prime] 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. […]
> 
> 
> 
> The relevant ECMAScript implementations support only one numeric data type, 
> 
> Number, which is an implementation of IEEE-754 double-precision floating-
> 
> point values.  Each such value requires 64 bits of storage (1 sign bit, 11 
> 
> exponent bits, and 52 mantissa bits), or _8_ bytes whereas each byte 
> 
> consists of 8 bits.
> 
> 
> 
> -- 
> 
> PointedEars
> 
> 
> 
> Twitter: @PointedEars2
> 
> Please do not Cc: me. / Bitte keine Kopien per E-Mail.

Lets start on a new foot Thomas sorry i was in a bad mood the other day, when you generate an array just with truth values how can i calculate the amount of memory it will hold, i suppose there is more then 1 bit per index or are they just stored binary?

[toc] | [prev] | [next] | [standalone]

#21262

On 2013-09-11 10:39, Thomas 'PointedEars' Lahn wrote:
> Stefan Weiss wrote:
>  
>> […] I just calculated the [prime] 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. […]
> 
> The relevant ECMAScript implementations support only one numeric data type, 
> Number, which is an implementation of IEEE-754 double-precision floating-
> point values.  Each such value requires 64 bits of storage (1 sign bit, 11 
> exponent bits, and 52 mantissa bits), or _8_ bytes whereas each byte 
> consists of 8 bits.

IEEE-754 and ECMAScript numbers are irrelevant for storing integers on
disk. For reference, Jonas wrote:

| But as i said you need a 4 TB disk, 16 GB of memory to really notice
| how great strawmans approach is.

I was referring to the "4 TB" figure (and said so directly before the
part you quoted). On typical PC hardware, 4 bytes gives me 32 bits.
That's enough to store any integer between 0 and 4294967295.
(Sure, you could also store them as IEEE floats instead of unsigned
ints, but why would you do that for prime numbers?)

The next part (which you also didn't quote), was:

>> RAM is a bigger problem, because of the overhead from the scripting engine.

That's where the 8 bytes for ECMAScript numbers are relevant. Other than
"bigger problem", I didn't say anything about RAM usage, because I don't
know what optimizations an engine would use when all the numbers are
integers. There will be some overhead compared to unsigned ints, but I
can't say how much. Maybe 4 bytes overhead, maybe more, maybe less.

- stefan

[toc] | [prev] | [next] | [standalone]

#21309

In comp.lang.javascript message <3251928.WeJvBNZfad@PointedEars.de>,
Wed, 11 Sep 2013 10:39:33, Thomas 'PointedEars' Lahn
<PointedEars@web.de> posted:

>Stefan Weiss wrote:
>
>> […] I just calculated the [prime] 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. […]
>
>The relevant ECMAScript implementations support only one numeric data type,
>Number, which is an implementation of IEEE-754 double-precision floating-
>point values.  Each such value requires 64 bits of storage (1 sign bit, 11
>exponent bits, and 52 mantissa bits), or _8_ bytes whereas each byte
>consists of 8 bits.

But perhaps it has not occurred to you that, /in extremis/, one can
store nearly 64 bits in an ECMAScript IEEE-754 Double.  IIRC, of the
2^64 bit patterns in an 8 byte Double, two represent the infinities, and
about 2^53 represent NaN, which ECMAScript cannot "resolve".

One can very easily store 32 bits in a Number, using the integer values
0 to 2^32-1.

-- 
 (c) John Stockton, Surrey, UK.  ¬@merlyn.demon.co.uk   Turnpike v6.05   MIME.
   Web  <http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
 Proper <= 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036)
 Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036)

[toc] | [prev] | [next] | [standalone]

#21311

Dr J R Stockton wrote:

> Thomas 'PointedEars' Lahn posted:
>> Stefan Weiss wrote:
>>> […] I just calculated the [prime] 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. […]
>>
>> The relevant ECMAScript implementations support only one numeric data
>> type, Number, which is an implementation of IEEE-754 double-precision
>> floating-point values.  Each such value requires 64 bits of storage (1
>> sign bit, 11 exponent bits, and 52 mantissa bits), or _8_ bytes whereas
>> each byte consists of 8 bits.
> 
> But perhaps it has not occurred to you that, /in extremis/, one can
> store nearly 64 bits in an ECMAScript IEEE-754 Double.

I believe I have just said that.

> IIRC, of the 2^64 bit patterns in an 8 byte Double, two represent the
> infinities, and about 2^53 represent NaN, which ECMAScript cannot
> "resolve".

True, but:
 
> One can very easily store 32 bits in a Number, using the integer values
> 0 to 2^32-1.

I do not see how that could reduce the memory footprint without some form of 
(potentially expensive) compression.  The 0-bits of the IEEE-754 value must 
*also* be stored in memory.

Another problem is the limited number of elements in an Array (2³²−2).  This 
means that there comes a point where it is no longer possible to simply push 
to an array like Stefan did, and you have to use, e. g., an Object instance 
whose properties you set (you could also use an Array instance, but there is 
no obvious advantage, and a clear disadvantage: potentially an even greater 
memory footprint), as Ben suggested.  IOW, Ben’s approach scales better than 
both Stefan‘s and the OP’s.

-- 
PointedEars

Twitter: @PointedEars2
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#21315

On 2013-09-13 02:27, Thomas 'PointedEars' Lahn wrote:
> Dr J R Stockton wrote:
>> IIRC, of the 2^64 bit patterns in an 8 byte Double, two represent the
>> infinities, and about 2^53 represent NaN, which ECMAScript cannot
>> "resolve".

(If we're going into that much detail, there's also -0, which is a
separate value in IEEE floats.)

> The 0-bits of the IEEE-754 value must *also* be stored in memory.

Oh, that's easy to solve. The 0-bits are empty anyway, so we can just
leave them out and concentrate on the more important 1s. Then we just
count how many 1s there are left and store that total, thus drastically
reducing memory usage. To decompress, just insert the empty bits back
in. (The boring question of where to insert them is left as an exercise
to the reader.) I call this compression technique "Bogocomp"; patent
pending.

> Another problem is the limited number of elements in an Array (2³²−2).  This 
> means that there comes a point where it is no longer possible to simply push 
> to an array like Stefan did

If the array where the primes are stored gets too big, we're way beyond
the point where it's reasonable to do integer arithmetic in JS.

> IOW, Ben’s approach scales better than both Stefan‘s and the OP’s.

In a way. Ben's using an actual sieve instead of doing trial division,
so of course his code is going to perform better. I wasn't trying to
find a performant or scalable algorithm, I just looked at the OP's idea
of "skipping" tests. Ben's 'comp' sieve marks all future (and past)
known-bad positions, which saves a lot of time. In the end, 'comp' will
contain almost as many elements as the maximum number requested, and the
program will use up quite a lot of memory. The OP wanted to go to 2
billion, which would mean a memory usage of around 16GB, plus the
'primes' array, plus overhead. [Theoretical worst case: the 'primes'
array has to be copied again when it's returned from the 'sieve'
function (barring copy on write optimization)].
Bottom line: scalability is relative.

Maybe some memory could be reclaimed by periodically rewriting 'comp' to
remove the parts of the sieve that are no longer needed? Just wondering,
I didn't try it out.

- stefan

[toc] | [prev] | [next] | [standalone]

#21317

Den fredagen den 13:e september 2013 kl. 04:03:13 UTC+2 skrev Stefan Weiss:
> On 2013-09-13 02:27, Thomas 'PointedEars' Lahn wrote:
> 
> > Dr J R Stockton wrote:
> 
> >> IIRC, of the 2^64 bit patterns in an 8 byte Double, two represent the
> 
> >> infinities, and about 2^53 represent NaN, which ECMAScript cannot
> 
> >> "resolve".
> 
> 
> 
> (If we're going into that much detail, there's also -0, which is a
> 
> separate value in IEEE floats.)
> 
> 
> 
> > The 0-bits of the IEEE-754 value must *also* be stored in memory.
> 
> 
> 
> Oh, that's easy to solve. The 0-bits are empty anyway, so we can just
> 
> leave them out and concentrate on the more important 1s. Then we just
> 
> count how many 1s there are left and store that total, thus drastically
> 
> reducing memory usage. To decompress, just insert the empty bits back
> 
> in. (The boring question of where to insert them is left as an exercise
> 
> to the reader.) I call this compression technique "Bogocomp"; patent
> 
> pending.
> 
> 
> 
> > Another problem is the limited number of elements in an Array (2³²-2).  This 
> 
> > means that there comes a point where it is no longer possible to simply push 
> 
> > to an array like Stefan did
> 
> 
> 
> If the array where the primes are stored gets too big, we're way beyond
> 
> the point where it's reasonable to do integer arithmetic in JS.
> 
> 
> 
> > IOW, Ben's approach scales better than both Stefan's and the OP's.
> 
> 
> 
> In a way. Ben's using an actual sieve instead of doing trial division,
> 
> so of course his code is going to perform better. I wasn't trying to
> 
> find a performant or scalable algorithm, I just looked at the OP's idea
> 
> of "skipping" tests. Ben's 'comp' sieve marks all future (and past)
> 
> known-bad positions, which saves a lot of time. In the end, 'comp' will
> 
> contain almost as many elements as the maximum number requested, and the
> 
> program will use up quite a lot of memory. The OP wanted to go to 2
> 
> billion, which would mean a memory usage of around 16GB, plus the
> 
> 'primes' array, plus overhead. [Theoretical worst case: the 'primes'
> 
> array has to be copied again when it's returned from the 'sieve'
> 
> function (barring copy on write optimization)].
> 
> Bottom line: scalability is relative.
> 
> 
> 
> Maybe some memory could be reclaimed by periodically rewriting 'comp' to
> 
> remove the parts of the sieve that are no longer needed? Just wondering,
> 
> I didn't try it out.
> 
> 
> 
> - stefan

Well it did turn out that for my petproject in javascript it really doesn't matter, although i think that my and Stefans approach would have benefits in other languages, when numbers start to get real big.

Have a look at my petproject it is a variant of ulam spiral but that does summation of squares.

Fixed a startposition and size for draw/animation
http://web.comhem.se/jonasth/main.html

[toc] | [prev] | [next] | [standalone]

#21318

Stefan Weiss wrote:

> On 2013-09-13 02:27, Thomas 'PointedEars' Lahn wrote:
>> Dr J R Stockton wrote:
>>> IIRC, of the 2^64 bit patterns in an 8 byte Double, two represent the
>>> infinities, and about 2^53 represent NaN, which ECMAScript cannot
>>> "resolve".
> 
> (If we're going into that much detail, there's also -0, which is a
> separate value in IEEE floats.)

Yes, but that is irrelevant.
 
>> The 0-bits of the IEEE-754 value must *also* be stored in memory.
> 
> Oh, that's easy to solve. The 0-bits are empty anyway, so we can just
> leave them out and concentrate on the more important 1s. Then we just
> count how many 1s there are left and store that total, thus drastically
> reducing memory usage. To decompress, just insert the empty bits back
> in. (The boring question of where to insert them is left as an exercise
> to the reader.) I call this compression technique "Bogocomp"; patent
> pending.

Utter nonsense.  You have no clue what you are talking about.
 
-- 
PointedEars

Twitter: @PointedEars2
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.javascript

csiph-web