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

Groups > comp.lang.javascript > #21329

Re: Strawmans prime sieve/filter

Show key headers only | View raw

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.)
> 
>> The 0-bits of the IEEE-754 value must *also* be stored in memory.
> 
> [joke]
> 
>> Another problem is the limited number of elements in an Array (2³²−2). 

2³²−_1_.  2³²−2 is the largest index.

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

Are we?  The largest integer that can be represented with IEEE-754 Doubles 
below which no loss of integer precision occurs is that where the mantissa 
is all zeros, the exponent is sufficiently large but does neither represent 
NaN, nor infinity or a subnormal, and the sign is 0.  That is,

  S Exponent     Mantissa
  -------------------------------------------------------------------------
  0 1111111 1111 0000 00000000 00000000 00000000 00000000 00000000 00000000
  0   7   F    F    0    0   0    0   0    0   0    0   0    0   0    0   0

must be excluded because it represents positive infinity, and

  S Exponent     Mantissa
  -------------------------------------------------------------------------
  0 1111111 1111 1000 00000000 00000000 00000000 00000000 00000000 00000000
  0   7   F    F    0    0   0    0   0    0   0    0   0    0   0    0   0
 
must be excluded because it represents NaN.  We can use

  S Exponent     Mantissa
  -------------------------------------------------------------------------
  0 1111111 1110 1111 11111111 11111111 11111111 11111111 11111111 11111111
  0   7   F    E    F    F   F    F   F    F   F    F   F    F   F    F   F

to represent

  (−1)⁰ × 2²⁰⁴⁶⁻¹⁰²³ × (1.1…1)₂ ≈ 1.7976931348623157 × 10³⁰⁸ [1]

  [1] <https://en.wikipedia.org/wiki/Double_precision_floating-point_format>

however loss of precision occurs already after all mantissa bits are 1.  
Still,

  S Exponent     Mantissa
  -------------------------------------------------------------------------
  0 0000000 0000 1111 11111111 11111111 11111111 11111111 11111111 11111111
  0   0   0    0    F    F   F    F   F    F   F    F   F    F   F    F   F

represents the subnormal

  (−1)⁰ × 2⁰⁻¹⁰²³ × (1.1…1)₂ = 2⁻¹⁰²³ × (1.1…1)₂ < 1

which is not what we are looking for.  Therefore, we can at most use
  
  S Exponent     Mantissa
  -------------------------------------------------------------------------
  0 1000011 0100 0000 00000000 00000000 00000000 00000000 00000000 00000000
  0   4   3    4    0    0   0    0   0    0   0    0   0    0   0    0   0

which represents

  (−1)⁰ × 2¹⁰⁷⁶⁻¹⁰²³ × 1.0 = 2⁵³

However, 2⁵³ is an even number; a multiple of 2, it cannot be prime.  As a 
result, the largest prime number candidate that could be confirmed with 
ECMAScript implementations so far is 2⁵³−1.

This leaves 2⁵³ − 2³², or more than 9 × 10¹⁵ (9 quadrillion, short scale), 
prime candidates (actually, only more than 4.5 × 10¹⁵ as half of them are 
even numbers) that cannot be confirmed *and* stored in (infinite) memory 
with the “push to Array” approach, but with the “set Object property” 
approach.
 
>> 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 ide
> of "skipping" tests.

Property lookups, likely based on hash tables, are among the most efficient 
operations there are in ECMAScript (and still they are to be avoided if not 
necessary).

Starting with an empty prototype chain removes the need for excluding 
inherited properties while iterating:

  var primes = Object.create(null);

and the like.

The remaining issue is arbitrary order with for-in iteration, however 
implementations tend to use the order of property creation.

  for (var i in primes)
  {
    /* integer i is prime */
  }

> Ben's 'comp' sieve

… which is actually a slightly optimized variant of the true implementation 
of the original sieve of Eratosthenes (c. 276 BCE – c. 195 BCE):

<https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>

> marks all future (and past)

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,

It is true that because of the prime number theorem (PNT) the ratio of prime 
numbers to the numbers that are not prime will decrease with increasing 
upper boundary, and therefore the “set Object property” approach becomes 
increasingly memory-inefficient.  But it is still more runtime-efficient and 
more capable of confirming a large number of numbers, particularly large 
prime numbers, than the “push to Array” approach.

> 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,

I wonder where you get your numbers from.

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

Without (the need for) the Array instance, the “set Object property” 
approach will not consume more memory than the “push to Array” approach up 
to an upper boundary of ca. 10¹¹ [π(10¹¹) = 4'118'054'813 < 2³²−1], and 
beyond that it will still have the advantage over the latter approach by 
simply still working.

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

Maybe.  For reference, it was

,-<news:0.f56f47af16523795dd40.20130911144711BST.87fvtb31y8.fsf@bsb.me.uk>
| 
| function sieve(max) {
|     var comp = [], primes = [], cur_prime = 2;
|     var upperLimit = Math.sqrt(max);
|     while (cur_prime < upperLimit) {
|         primes.push(cur_prime);
|         for (var mult = cur_prime * cur_prime; mult < max;
| mult += cur_prime)
|             comp[mult] = true;
|         while (comp[++cur_prime]);
|     }
|     for (; cur_prime < max; cur_prime++)
|         if (!comp[cur_prime])
|             primes.push(cur_prime);
|     return primes;
| }
| 
`----

This can be optimized as follows:

  function getPrimes (max)
  {
    var not_prime = Object.create(null);
    var prime = Object.create(null);
    var i = 2;
    var upperLimit = Math.sqrt(max);

    while (i < upperLimit)
    {
      prime[i] = true;

      for (var mult = i * i; mult < max; mult += i)
      {
        not_prime[mult] = true;
      }

      while (not_prime[++i])
      {
        delete not_prime[i];
      }
    }

    for (; i < max; ++i)
    {
      if (!not_prime[i])
      {
        prime[i] = true;
      }

      delete not_prime[i];
    }

    return prime;
  }

The algorithm differs in that properties of the object referred to by 
“not_prime” (formerly: “comp”) are removed as they are no longer needed.  
This *might* decrease the memory footprint (thus increase the memory-
efficiency), but it adds another step (thus decreases the runtime-
efficiency).

The return value differs in that a reference to an Object instance is 
returned, whose property *names* are the prime numbers in range.  In order 
to get an Array of up to 2³²−1 prime numbers in range, you can write:

  var primes = Object.keys(getPrimes(x));

Note that the elements of the Array referred to by “primes” will be string 
values (as all property names are strings, even the numeric ones).  Mass 
conversion is possible:

  var primes = Object.keys(getPrimes(x))
    /* convert to Number */
    .map(function (e) { return +e; })

    /* sort numerically ascending */
    .sort(function (a, b) { return a - b; });

In order to get *all* prime numbers in range, use for-in iteration as I 
wrote above.

-- 
PointedEars

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

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