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

Groups > comp.lang.javascript > #21259

Re: Strawmans prime sieve/filter

Newsgroups comp.lang.javascript
Date 2013-09-11 00:36 -0700
References <6e464d33-47e4-41b8-bfda-19511de92915@googlegroups.com> <l0jgv8$g2u$1@news.albasani.net> <65457886-cbe5-4ba8-8d77-b1c212faf964@googlegroups.com> <0.ae14d9ee263097e10773.20130910224834BST.87mwnk2vrh.fsf@bsb.me.uk>
Message-ID <c8df65e0-e61f-4df8-a02f-96ad2f9dfbfd@googlegroups.com> (permalink)
Subject Re: Strawmans prime sieve/filter
From jonas.thornvall@gmail.com

Show all headers | View raw

Den tisdagen den 10:e september 2013 kl. 23:48:34 UTC+2 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
> 
> 
> 
> <snip>
> 
> > So what is wrong with this code?
> 
> 
> 
> It looks over-complex, and it's not a fast as the plain sieve, so I
> 
> don't see the point of the complexity.  Maybe it kicks in for much
> 
> larger primes sets.
> 
> 
> 
> <snip>
> 
> > function sieve(max) {
> 
> > 	var D = [], primes = [];
> 
> > 	for (var q=2; q<max; q++) {
> 
> > 		if (D[q]) {
> 
> > 			for (var i=0; i<D[q].length; i++) {
> 
> > 				 var p = D[q][i];
> 
> > 				 if (D[p+q]) D[p+q].push(p);
> 
> > 				 else D[p+q]=[p];
> 
> > 			}
> 
> > 			delete D[q];
> 
> > 		} else {
> 
> > 			primes.push(q);
> 
> > 			if (q*q<max) D[q*q]=[q];
> 
> > 		}
> 
> > 	}
> 
> > 	return primes;
> 
> >  }
> 
> <snip>
> 
> 
> 
> The plain sieve of Eratosthenes goes like this:
> 
> 
> 
> function sieve(max) {
> 
>     var comp = [], primes = [], cur_prime = 2;
> 
>     while (cur_prime < max) {
> 
>         primes.push(cur_prime);
> 
>         for (var mult = 2 * cur_prime; mult < max; mult += cur_prime)
> 
>             comp[mult] = true;
> 
>         while (comp[++cur_prime]);
> 
>     }
> 
>     return primes;
> 
> }
> 
> 
> 
> On my machine, this runs five times faster for primes up to 20,000,000.
> 
> 
> 
> -- 
> 
> Ben.

Hello Ben nice implementation, i do not know if i remember wrong but is this a new twist on Eratosthenes only storing the truth values? yours indeed was much faster then strawman, and i found an even faster implementation of Eratosthenes.

But i will try to match your speeds by setting just the index like you seem todo, i found your implementation a bit hard to understand could you explain?

Here is the timings from my computer yours, mine and Eratosthenes like i remembered it but it only uses index.

Barcaisse Timing=10779

Thörnvall Timing=29738

Ereastohenes Timing=6348

Code below.

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

<script type="text/javascript">

var MAX = 30000000;

function Eratosthenes()
{
   
   // Eratosthenes algorithm to find all primes under n
   var array = [], upperLimit = Math.sqrt(n), output = [];

   // Make an array from 2 to (n - 1)
   for (var i = 0; i < n; i ++ )
   {
      array.push(true);
   }

   // Remove multiples of primes starting from 2, 3, 5, ...
   for (var i = 2; i <= upperLimit; i ++ )
   {
      if (array[i])
      {
         for (var j = i * i; j < n; j += i)
         {
            array[j] = false;
         }
      }
   }

   for (var i = 2; i < n; i ++ )
   {
      if(array[i])
      {
         output.push(i);
      }
   }
     outE = output.toString();
}



function benB()
{
   var comp = [], primes = [], cur_prime = 2;
   while (cur_prime < MAX)
   {
      primes.push(cur_prime);
      for (var mult = 2 * cur_prime; mult < MAX;
      mult += cur_prime)
      comp[mult] = true;
      while (comp[ ++ cur_prime]);

   }
   outB = primes.toString();
   return outB;
}

function jonasT()
{
   var primes = [2];
   n = 3;
   while(n < MAX)
   {
      p = true;
      k = 0;
      test = Math.sqrt(n) + 1;
      test = Math.round(test);
      while (test >= primes[k])
      {
         if  ((n % primes[k]) == 0)
         {
            p = false;
            break;
            document.write("break");
         }
         k ++ ;
      }
      if (p == true)
      {
         t = primes.length;
         primes[t] = n;
      }
      n ++ ;
   }
   outJ = primes.toString();
   return outJ;
}

var start = new Date().getTime();
benB();
var end = new Date().getTime();
var time = end - start;
outB=outB.substring(0,100);
document.write("Barcaisse=", outB, "<BR> Timing=", time, "<BR>");

var start = new Date().getTime();
jonasT();
var end = new Date().getTime();
var time = end - start;
outJ=outJ.substring(0,100);
document.write("<BR>Thörnvall=", outJ, "<BR> Timing=", time, "<BR>");

var start = new Date().getTime();
Eratosthenes(MAX);
var end = new Date().getTime();
var time = end - start;
outE=outE.substring(0,100);
document.write("<BR>Ereastohenes=",outE,"<BR> Timing=", time, "<BR>");

</script>
<body>
</body>
</html>

Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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