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 2 of 3 — ← Prev page 1 [2] 3  Next page →

#21320

On 2013-09-13 05:15, Thomas 'PointedEars' Lahn wrote:
>> On 2013-09-13 02:27, Thomas 'PointedEars' Lahn wrote:
>>> 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.

You do have Spock's infallible grasp of humor.

- stefan

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

#21327

Den fredagen den 13:e september 2013 kl. 05:27:17 UTC+2 skrev Stefan Weiss:
> On 2013-09-13 05:15, Thomas 'PointedEars' Lahn wrote:
> 
> >> On 2013-09-13 02:27, Thomas 'PointedEars' Lahn wrote:
> 
> >>> 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.
> 
> 
> 
> You do have Spock's infallible grasp of humor.
> 
> 
> 
> - stefan

Humor aside if we talk about storing numbers disk saving space, the primes could be stored P-1 and then if we have them ordered we could find highest factor for each digit place, so P-1/GCD=factor and just store GCD pf1,pf2,pf3...

That could save many digitplaces for big numbers?

To recreate number GCD*pf1+1

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

#21326

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 you could always remove the 0's in unary base, compress the remaining 1's honestly i am not sure if i am joking or not.

Because it is a bit over my visualisation skills.

I have a feeling though the compressed 1's would look pretty much like the number i started with ;D

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

#21329

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.

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

#21336

Den fredagen den 13:e september 2013 kl. 19:13:52 UTC+2 skrev Thomas 'PointedEars' Lahn:
> 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.

Hello Thomas could you explain to me why the Eratosthenes function i found have bigger memory requirments then Ben's. I cut it down to just the bitstream natural prime and not prime, no  conversion back in code below. I did not understand the beauty of Eratosthenes until i realised it only had to store truth values. But there could be heap and pointer implementation that are more effective using mine or Stefans approach in the long run. There will come a moment when you simply can not store the truth values in an array. And if you do chose to store the linear array of naturals as bits representing none primes
and primes, there will also be a point where the cost to look up a truth value and convert it into a prime exceeds the cost to store the prime in a compressed format.

Do you agree?
function isPrime()
{
   n = MAX;
   // Eratosthenes algorithm to find all primes under n
   upperLimit = Math.sqrt(n);

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

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

         }
      }
      i ++ ;
   }
   return array;
}

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

#21337

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Stefan Weiss wrote:
<snip>
>> 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).

You say above that this code is an optimised version of mine, but then
you say it *might* decrease memory footprint, but that all the deleting
decreases the runtime-efficiency.  In what sense has it been optimised?

On two test engines (rhino and nodejs) the deleting has a huge impact on
the run time (a factor of four in rhino and way more in nodejs -- so
much so I killed it before getting a time).

Setting comp = Object.create(null) is not much help in rhino (a small
win with optimisation on but it slows things down without) but in the
better engine (nodejs) it takes 1/4 off the run time.  It's a really
neat thing to remember -- thanks.

Obviously one can't generalise about what other run-time environments
will do, but I think pushing the primes and using "plain" object for
recording composites looks like a good strategy.

> 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));

That just adds to the time, of course, but you need it to compare like
with like.

> 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; })

I was surprised how fast this was in nodejs.  It's really slow in rhino.

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

This had little cost in both engines.

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

-- 
Ben.

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

#21339

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Stefan Weiss wrote:
> <snip>
>>> 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).
> 
> You say above that this code is an optimised version of mine, but then
> you say it *might* decrease memory footprint,

I said the *deletion* might decrease the memory footprint.

> but that all the deleting decreases the runtime-efficiency.  In what sense
> has it been optimised?

- it can store primes up to 2⁵³−1 (an Array instance can only hold 2³²−1
  elements)
- reduced memory usage (Object instead of Array)
- potentially faster (no extra Array.prototype.push() calls)
- post-increment replaced with pre-increment (maybe faster)
 
> On two test engines (rhino and nodejs) the deleting has a huge impact on
> the run time (a factor of four in rhino and way more in nodejs -- so
> much so I killed it before getting a time).

Thanks.
 
> Setting comp = Object.create(null) is not much help in rhino (a small
> win with optimisation on but it slows things down without)
           ^^^^^^^^^^^^        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Which JavaScript version, and what do you mean by that?

> but in the better engine (nodejs) it takes 1/4 off the run time.  It's a
> really neat thing to remember -- thanks.

You're welcome.  Which nodeJS and V8 versions?
 
>> 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));
> 
> That just adds to the time, of course, but you need it to compare like
> with like.

Yes, you have to consider that this approach is more capable and flexible, 
at the cost of increased runtime towards the end when you really need (only) 
an Array or will never have more than 2³²−1 primes (upper bounds at or below 
ca. 10¹¹).

[Observing a need for arrays that can index up to 2⁵³ elements prior to 
Harmony, I am adding jsx.array.BigArray to JSX:array.js.  You will find it 
at <http://PointedEars.de/wsvn/JSX/trunk/array.js>.]
 
>> 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; })
> 
> I was surprised how fast this was in nodejs.  It's really slow in rhino.

You can skip this step if you are content with strings in the array because 
…
 
>>     /* sort numerically ascending */
>>     .sort(function (a, b) { return a - b; });

… this implicitly converts the elements to Number for sorting.  However, 
skipping the first step might be even slower in Rhino if conversion to 
Number is the cause.
 
> This had little cost in both engines.

Very good.

-- 
PointedEars

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

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

#21341

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>> Stefan Weiss wrote:
>> <snip>
>>>> 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).
>> 
>> You say above that this code is an optimised version of mine, but then
>> you say it *might* decrease memory footprint,
>
> I said the *deletion* might decrease the memory footprint.

Yes, I understood that.  My point is that you cite it as a potential
benefit.

>> but that all the deleting decreases the runtime-efficiency.  In what sense
>> has it been optimised?
>
> - it can store primes up to 2⁵³−1 (an Array instance can only hold 2³²−1
>   elements)
> - reduced memory usage (Object instead of Array)
> - potentially faster (no extra Array.prototype.push() calls)
> - post-increment replaced with pre-increment (maybe faster)

But it could also be slower and use exactly the same amount of memory.
In fact that is the case in both engines I tested.  As posted, your
"optimised" version did not finish in two minutes when run under nodejs,
and was about 4 to 5 times slower than mine in rhino.  That does not
match what I think of as optimised code.

>> On two test engines (rhino and nodejs) the deleting has a huge impact on
>> the run time (a factor of four in rhino and way more in nodejs -- so
>> much so I killed it before getting a time).
>
> Thanks.

For testing, or showing that deleting elements is slow?

>> Setting comp = Object.create(null) is not much help in rhino (a small
>> win with optimisation on but it slows things down without)
>            ^^^^^^^^^^^^        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> Which JavaScript version, and what do you mean by that?

The man page does not say what version, but the options are 100, 110,
120, ... up to 170 but setting the language version has no perceptible
effect on the timing.

To see what using Object.create(null) did on its own, I timed my code
with cmomp = [] and comp = Object.create(null).  In rhino, with
optimisation off, there was a small difference, but with optimisation on
(rhino -opt 9) the version with an array is faster -- using
Object.create(null) slows it down, by a factor of about 3.5 (3.8s up to
14.12s).

I've tested again, and the Object version (of my code) is slower even
without optimisation.  I think my report of a small gain in speed was
due to not timing enough runs.

This is counter-intuitive and not what I see with nodejs.

>> but in the better engine (nodejs) it takes 1/4 off the run time.  It's a
>> really neat thing to remember -- thanks.
>
> You're welcome.  Which nodeJS and V8 versions?

All I can tell you is the package version (0.6.19).  If you can tell me
how to find out the V8 version i will report back.

>>> 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));
>> 
>> That just adds to the time, of course, but you need it to compare like
>> with like.
>
> Yes, you have to consider that this approach is more capable and flexible, 
> at the cost of increased runtime towards the end when you really need (only) 
> an Array or will never have more than 2³²−1 primes (upper bounds at or below 
> ca. 10¹¹).
>
> [Observing a need for arrays that can index up to 2⁵³ elements prior to 
> Harmony, I am adding jsx.array.BigArray to JSX:array.js.  You will find it 
> at <http://PointedEars.de/wsvn/JSX/trunk/array.js>.]
>  
>>> 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; })
>> 
>> I was surprised how fast this was in nodejs.  It's really slow in rhino.
>
> You can skip this step if you are content with strings in the array because 
> …
>  
>>>     /* sort numerically ascending */
>>>     .sort(function (a, b) { return a - b; });
>
> … this implicitly converts the elements to Number for sorting.  However, 
> skipping the first step might be even slower in Rhino if conversion to 
> Number is the cause.
>  
>> This had little cost in both engines.
>
> Very good.

Just to be clear my timings excluded these refinements.  I was comparing
your code without extracting the keys (nor converting nor sorting them),
with mine as posted.

-- 
Ben.

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

#21343

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Ben Bacarisse wrote:
>>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>>> 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).
>>> You say above that this code is an optimised version of mine, but then
>>> you say it *might* decrease memory footprint,
>> I said the *deletion* might decrease the memory footprint.
> 
> Yes, I understood that.  My point is that you cite it as a potential
> benefit.

If a program uses less memory than another while doing the same thing or 
even more than the latter, that is a benefit.

>>> but that all the deleting decreases the runtime-efficiency.  In what
>>> sense has it been optimised?
>>
>> - it can store primes up to 2⁵³−1 (an Array instance can only hold 2³²−1
>>   elements)
>> - reduced memory usage (Object instead of Array)
>> - potentially faster (no extra Array.prototype.push() calls)
>> - post-increment replaced with pre-increment (maybe faster)
> 
> But it could also be slower and use exactly the same amount of memory.
> In fact that is the case in both engines I tested.  As posted, your
> "optimised" version did not finish in two minutes when run under nodejs,
> and was about 4 to 5 times slower than mine in rhino.  That does not
> match what I think of as optimised code.

If you think of optimization only in terms of runtime-efficiency, you are 
correct.

>>> On two test engines (rhino and nodejs) the deleting has a huge impact on
>>> the run time (a factor of four in rhino and way more in nodejs -- so
>>> much so I killed it before getting a time).
>>
>> Thanks.
> 
> For testing, or showing that deleting elements is slow?

Both.

Please trim your quotes to the relevant parts.

-- 
PointedEars

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

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

#21345

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>> Ben Bacarisse wrote:
<snip>
>>>> but that all the deleting decreases the runtime-efficiency.  In what
>>>> sense has it been optimised?
>>>
>>> - it can store primes up to 2⁵³−1 (an Array instance can only hold 2³²−1
>>>   elements)
>>> - reduced memory usage (Object instead of Array)
>>> - potentially faster (no extra Array.prototype.push() calls)
>>> - post-increment replaced with pre-increment (maybe faster)
>> 
>> But it could also be slower and use exactly the same amount of memory.
>> In fact that is the case in both engines I tested.  As posted, your
>> "optimised" version did not finish in two minutes when run under nodejs,
>> and was about 4 to 5 times slower than mine in rhino.  That does not
>> match what I think of as optimised code.
>
> If you think of optimization only in terms of runtime-efficiency, you are 
> correct.

I think of it in engineering terms, not theoretical ones.  You cite
three advantages: increased range, memory use, and speed.  Do you know
of any engine in which any of the three advantages is realised?  I only
tested two, and you are aware of a very much wider range of
implementations than I am, so there may well be one.

<snip>
-- 
Ben.

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

#21346

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Ben Bacarisse wrote:
>>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>>> Ben Bacarisse wrote:
> <snip>
>>>>> but that all the deleting decreases the runtime-efficiency.  In what
>>>>> sense has it been optimised?
>>>>
>>>> - it can store primes up to 2⁵³−1 (an Array instance can only hold
>>>>   2³²−1 elements)
>>>> - reduced memory usage (Object instead of Array)
>>>> - potentially faster (no extra Array.prototype.push() calls)
>>>> - post-increment replaced with pre-increment (maybe faster)
>>> 
>>> But it could also be slower and use exactly the same amount of memory.
>>> In fact that is the case in both engines I tested.  As posted, your
>>> "optimised" version did not finish in two minutes when run under nodejs,
>>> and was about 4 to 5 times slower than mine in rhino.  That does not
>>> match what I think of as optimised code.
>>
>> If you think of optimization only in terms of runtime-efficiency, you are
>> correct.
> 
> I think of it in engineering terms, not theoretical ones.  You cite
> three advantages: increased range, memory use, and speed.  Do you know
> of any engine in which any of the three advantages is realised?

(I had listed *four*.)  Free memory permitting (see below), the first 
advantage certainly appears to be realized in Google V8 in Chromium “Version 
29.0.1547.57 Debian jessie/sid (217859)”:

,----
| 
| > String(Math.pow(2, 53))
| "9007199254740992"
| 
| > String(Math.pow(2, 53) - 1)
| "9007199254740991"
| 
| > var o = Object.create(null);
| undefined
| 
| > o[Math.pow(2, 53)] = 42
| 42
| 
| > o[Math.pow(2, 53) - 1] = 23
| 23
| 
| > o[Math.pow(2, 53)]
| 42
| 
| > o[Math.pow(2, 53) - 1]
| 23
| 
| > o[Math.pow(2, 53) - 2]
| undefined
| 
`----

Of course, how large a prime number candidate actually can be confirmed 
hinges on the precision of string representations of Number values which 
IMHO is defined in such a complicated way that it may well be considered 
implementation-dependent (ES 5.1, §9.8.1).

> I only tested two, and you are aware of a very much wider range of
> implementations than I am, so there may well be one.

The fallacy here is “proof by example”.  It is a mistake for an author of an 
ECMAScript script to base their design decisions on speculations about 
possible implementations and their possible optimizations.  Even the 
optimizations in a specific implementation are moving targets.  In a 
situation where you want to write cross-implementation code, but you have no 
control over the actual runtime environment, you have to choose that which 
is best for the task and probably best for *all* *targeted* implementations; 
in the simplest case, all widely distributed ones *currently* in use.

IOW, theoretical deliberations *must* guide the implementation.  As a rule 
of thumb, the more capable algorithms should be chosen.  Of those, the more 
efficient algorithms should be implemented, while – as always – you have to 
weigh memory-efficiency against runtime-efficiency.  Sometimes it can even 
be useful to have several implementations for the same task (in a library) 
with focus on different kinds of efficiency.  Sometimes the less capable, 
but more efficient algorithm is preferable in a particular situation.  In 
yet other words, there is no black and white.

In this case I have made the (IMHO reasonable) assumption that it would be 
preferable to be able to confirm more prime number candidates than less, 
even if that means that in the end this might be slower.  Therefore, I am 
using Object instances instead of Array instances, and I am deleting 
unnecessary properties as soon as possible (as Stefan suggested).  You have 
showed *by two examples* (out of more than 6 possible) that deleting 
unnecessary properties as soon as possible might not be a good idea, and I 
have been and am grateful for that.  However, it remains to be seen how the 
implementation of this algorithm performs in other environments, with other 
ECMAScript implementations, particularly in my target environments.

Aside from the fact that it matters how the code was used (i.e., with which 
arguments the function was called), it is also important which versions of 
implementations you have tested with in which environments, which is why I 
asked for that information.  For example, one has to weigh the age of Rhino 
(version 1.7R4 was released on 2012-06-18 CE; JavaScript 1.7 was released 
with Firefox 2 in 2006 – before TraceMonkey, JägerMonkey, IonMonkey, and 
Baseline [1]) against the fact that *you* have observed in *some* version of 
Rhino that type conversion is slow.  If you are not versed enough with your 
environment that you cannot even provide that basic information, maybe your 
test results are not that important as your test methodology might be flawed 
as well.  (That is not to say I would not help you finding that out if I 
just could, but those are not my target environments/implementations, and I 
do not think it is my job to RTFM to or STFW for you.)

If you want to write a version that is optimized for your favorite/target 
environment(s), implementation(s), and version(s), you can do so.  You may 
even use the bulk of my code as template, considering its license. [2]

HTH.

________
[1] <http://PointedEars.de/es-matrix#javascript> (to be updated)
[2] <http://PointedEars.de/wsvn/JSX/trunk/math/integer.js> (to be updated)

-- 
PointedEars

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

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

#21348

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>> Ben Bacarisse wrote:
>>>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>>>> Ben Bacarisse wrote:
>> <snip>
>>>>>> but that all the deleting decreases the runtime-efficiency.  In what
>>>>>> sense has it been optimised?
>>>>>
>>>>> - it can store primes up to 2⁵³−1 (an Array instance can only hold
>>>>>   2³²−1 elements)
>>>>> - reduced memory usage (Object instead of Array)
>>>>> - potentially faster (no extra Array.prototype.push() calls)
>>>>> - post-increment replaced with pre-increment (maybe faster)
>>>> 
>>>> But it could also be slower and use exactly the same amount of memory.
>>>> In fact that is the case in both engines I tested.  As posted, your
>>>> "optimised" version did not finish in two minutes when run under nodejs,
>>>> and was about 4 to 5 times slower than mine in rhino.  That does not
>>>> match what I think of as optimised code.
>>>
>>> If you think of optimization only in terms of runtime-efficiency, you are
>>> correct.
>> 
>> I think of it in engineering terms, not theoretical ones.  You cite
>> three advantages: increased range, memory use, and speed.  Do you know
>> of any engine in which any of the three advantages is realised?
>
> (I had listed *four*.)

You list four changes, but they confer three potential advantages.

>  Free memory permitting (see below), the first 
> advantage certainly appears to be realized in Google V8 in Chromium “Version 
> 29.0.1547.57 Debian jessie/sid (217859)”:

I don't want to install that version but in version 28.0.1500.71 your
code stands no chance of going beyond 2^32.  I can't get it to go to 2
million, let alone the 20 million that was the posted example.  2^53-1
is fantasy.

I think I see the problem.  You take each of your four modifications and
consider what they might do in the right circumstances.  And, yes, each
one might help in this or other programs.  I was just complaining that
you characterised the code as "optimised".  If an EcmaScript expert like
you optimises my code, I'd expect *the posted code* to realise *some* of
the supposed benefits in a major implementation like V8.  Instead it
just exercises the fan of my laptop.

I am not disputing the potential gains that *might* be had by using the
techniques you applied.  I am disputing that they are gains in relation
to the ocde you described as "optimised".

> ,----
> | 
> | > String(Math.pow(2, 53))
> | "9007199254740992"
> | 
> | > String(Math.pow(2, 53) - 1)
> | "9007199254740991"
> | 
> | > var o = Object.create(null);
> | undefined
> | 
> | > o[Math.pow(2, 53)] = 42
> | 42
> | 
> | > o[Math.pow(2, 53) - 1] = 23
> | 23
> | 
> | > o[Math.pow(2, 53)]
> | 42
> | 
> | > o[Math.pow(2, 53) - 1]
> | 23
> | 
> | > o[Math.pow(2, 53) - 2]
> | undefined
> | 
> `----
>
> Of course, how large a prime number candidate actually can be confirmed 
> hinges on the precision of string representations of Number values which 
> IMHO is defined in such a complicated way that it may well be considered 
> implementation-dependent (ES 5.1, §9.8.1).
>
>> I only tested two, and you are aware of a very much wider range of
>> implementations than I am, so there may well be one.
>
> The fallacy here is “proof by example”.  It is a mistake for an author of an 
> ECMAScript script to base their design decisions on speculations about 
> possible implementations and their possible optimizations.

I don't follow -- I have not attempted to prove anything.  Are you
talking about your examples above?

I am acutely aware that I am posting from a position of relative
ignorance.  That's why I asked you for and example where the code you
posted (not each modification of my code) realises some or all of the
purported benefits.

If, on the other hand, you stand by the idea that one should not rely
on speculation about implementations and their possible optimisations, in
what sense do you justify calling your code "optimised"?  Surely your
changes were based on exactly that sort of speculation.

I know that the change in representation does not rely on speculation,
but the benefit of it (going beyond 2^32) does speculate on the
existence of an implementation that can execute the code fast enough to
get near to that number in some reasonable time.

>  Even the 
> optimizations in a specific implementation are moving targets.  In a 
> situation where you want to write cross-implementation code, but you have no 
> control over the actual runtime environment, you have to choose that which 
> is best for the task and probably best for *all* *targeted* implementations; 
> in the simplest case, all widely distributed ones *currently* in use.

Absolutely.  So how can your code be called optimised if it doesn't even
manage the posted task in one major implementation?

<patronising stuff snipped>
-- 
Ben.

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

#21351

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Ben Bacarisse wrote:
>>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>>> Ben Bacarisse wrote:
>>>>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>>>>> Ben Bacarisse wrote:
>>> <snip>
>>>>>>> but that all the deleting decreases the runtime-efficiency.  In what
>>>>>>> sense has it been optimised?
>>>>>>
>>>>>> - it can store primes up to 2⁵³−1 (an Array instance can only hold
>>>>>>   2³²−1 elements)
>>>>>> - reduced memory usage (Object instead of Array)
>>>>>> - potentially faster (no extra Array.prototype.push() calls)
>>>>>> - post-increment replaced with pre-increment (maybe faster)
>>>>> 
>>>>> But it could also be slower and use exactly the same amount of memory.
>>>>> In fact that is the case in both engines I tested.  As posted, your
>>>>> "optimised" version did not finish in two minutes when run under
>>>>> nodejs,
>>>>> and was about 4 to 5 times slower than mine in rhino.  That does not
>>>>> match what I think of as optimised code.
>>>>
>>>> If you think of optimization only in terms of runtime-efficiency, you
>>>> are correct.
>>> 
>>> I think of it in engineering terms, not theoretical ones.  You cite
>>> three advantages: increased range, memory use, and speed.  Do you know
>>> of any engine in which any of the three advantages is realised?
>>
>> (I had listed *four*.)
> 
> You list four changes, but they confer three potential advantages.

Wrong.

>>  Free memory permitting (see below), the first
>> advantage certainly appears to be realized in Google V8 in Chromium
>> “Version 29.0.1547.57 Debian jessie/sid (217859)”:
> 
> I don't want to install that version but in version 28.0.1500.71 your
> code stands no chance of going beyond 2^32.

Neither has the “push to Array” approach because, unfortunately, ECMAScript 
arrays can have at most 2³²−1 elements.  So any prime candidates you could 
confirm with that approach (free memory permitting) are not visible to the 
caller.  *That* is the main benefit of the “set Object property” approach.

And why should I optimize code for *obsolete* browser versions?  It is not 
like anyone would be keeping v28, or v29, for that matter, for very long.  
With rapid releases, in Chromium we are beyond those times when you had to 
consider a number of past major versions.

> I can't get it

What, exactly?  As you have identified the “delete” operation as a potential 
disadvantage, have you removed that operation and re-checked?

> to go to 2 million, let alone the 20 million that was the posted example. 
> 2^53-1 is fantasy.

Why?
 
> I think I see the problem.  You take each of your four modifications and
> consider what they might do in the right circumstances.  And, yes, each
> one might help in this or other programs.  I was just complaining 

Usenet is not a right.

> that you characterised the code as "optimised".  If an EcmaScript expert
> like you optimises my code, I'd expect *the posted code* to realise *some*
> of the supposed benefits in a major implementation like V8. 

It *is* optimized.  Again, optimization means something else than you think 
it does.  In which way does the code not realize *some* of the mentioned 
benefits?

> Instead it just exercises the fan of my laptop.

Maybe you are using it wrong.  With that many operations, you most certainly 
want to run it with window.setTimeout() in order to prevent UI lockup.  And 
certainly your fan would go up; it is quite a number crunching your CPU has 
to do then.  Maybe, as Stefan indicated, ECMAScript implementations are just 
the wrong languages for number crunching.  That does not mean the approach 
is wrong.
 
> <patronising stuff snipped>

Your customer attitude makes me sick.  Go away.

-- 
PointedEars

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

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

#21352

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
<snip>
> Your customer attitude makes me sick.  Go away.

What makes you think I'm a customer?

-- 
Ben.

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

#21354

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
> <snip>
>> Your customer attitude makes me sick.  Go away.

Perhaps I should have said “customer’s attitude”.

> What makes you think I'm a customer?

You make me think that *you* think you *were* a customer by the way you 
react.  For example, you do not object, you “complain”.  As if you had a 
right to a perfect product or service around here.
 
-- 
PointedEars

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

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

#21355

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> <snip>
>>> Your customer attitude makes me sick.  Go away.
>
> Perhaps I should have said “customer’s attitude”.
>
>> What makes you think I'm a customer?
>
> You make me think that *you* think you *were* a customer by the way you 
> react.  For example, you do not object, you “complain”.  As if you had a 
> right to a perfect product or service around here.

Ah, I see.  I misunderstood and I seem to have been misunderstood in
return.  I don't expect, or even want, any product or service here.
There are things I'd like to be different, but they don't relate to any
product or service.

-- 
Ben.

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

#21353

Den lördagen den 14:e september 2013 kl. 22:51:09 UTC+2 skrev Ben Bacarisse:
> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
> 
> 
> 
> > Ben Bacarisse wrote:
> 
> >
> 
> >> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
> 
> >>> Ben Bacarisse wrote:
> 
> >>>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
> 
> >>>>> Ben Bacarisse wrote:
> 
> >> <snip>
> 
> >>>>>> but that all the deleting decreases the runtime-efficiency.  In what
> 
> >>>>>> sense has it been optimised?
> 
> >>>>>
> 
> >>>>> - it can store primes up to 2⁵³−1 (an Array instance can only hold
> 
> >>>>>   2³²−1 elements)
> 
> >>>>> - reduced memory usage (Object instead of Array)
> 
> >>>>> - potentially faster (no extra Array.prototype.push() calls)
> 
> >>>>> - post-increment replaced with pre-increment (maybe faster)
> 
> >>>> 
> 
> >>>> But it could also be slower and use exactly the same amount of memory.
> 
> >>>> In fact that is the case in both engines I tested.  As posted, your
> 
> >>>> "optimised" version did not finish in two minutes when run under nodejs,
> 
> >>>> and was about 4 to 5 times slower than mine in rhino.  That does not
> 
> >>>> match what I think of as optimised code.
> 
> >>>
> 
> >>> If you think of optimization only in terms of runtime-efficiency, you are
> 
> >>> correct.
> 
> >> 
> 
> >> I think of it in engineering terms, not theoretical ones.  You cite
> 
> >> three advantages: increased range, memory use, and speed.  Do you know
> 
> >> of any engine in which any of the three advantages is realised?
> 
> >
> 
> > (I had listed *four*.)
> 
> 
> 
> You list four changes, but they confer three potential advantages.
> 
> 
> 
> >  Free memory permitting (see below), the first 
> 
> > advantage certainly appears to be realized in Google V8 in Chromium “Version 
> 
> > 29.0.1547.57 Debian jessie/sid (217859)”:
> 
> 
> 
> I don't want to install that version but in version 28.0.1500.71 your
> 
> code stands no chance of going beyond 2^32.  I can't get it to go to 2
> 
> million, let alone the 20 million that was the posted example.  2^53-1
> 
> is fantasy.
> 
> 
> 
> I think I see the problem.  You take each of your four modifications and
> 
> consider what they might do in the right circumstances.  And, yes, each
> 
> one might help in this or other programs.  I was just complaining that
> 
> you characterised the code as "optimised".  If an EcmaScript expert like
> 
> you optimises my code, I'd expect *the posted code* to realise *some* of
> 
> the supposed benefits in a major implementation like V8.  Instead it
> 
> just exercises the fan of my laptop.
> 
> 
> 
> I am not disputing the potential gains that *might* be had by using the
> 
> techniques you applied.  I am disputing that they are gains in relation
> 
> to the ocde you described as "optimised".
> 
> 
> 
> > ,----
> 
> > | 
> 
> > | > String(Math.pow(2, 53))
> 
> > | "9007199254740992"
> 
> > | 
> 
> > | > String(Math.pow(2, 53) - 1)
> 
> > | "9007199254740991"
> 
> > | 
> 
> > | > var o = Object.create(null);
> 
> > | undefined
> 
> > | 
> 
> > | > o[Math.pow(2, 53)] = 42
> 
> > | 42
> 
> > | 
> 
> > | > o[Math.pow(2, 53) - 1] = 23
> 
> > | 23
> 
> > | 
> 
> > | > o[Math.pow(2, 53)]
> 
> > | 42
> 
> > | 
> 
> > | > o[Math.pow(2, 53) - 1]
> 
> > | 23
> 
> > | 
> 
> > | > o[Math.pow(2, 53) - 2]
> 
> > | undefined
> 
> > | 
> 
> > `----
> 
> >
> 
> > Of course, how large a prime number candidate actually can be confirmed 
> 
> > hinges on the precision of string representations of Number values which 
> 
> > IMHO is defined in such a complicated way that it may well be considered 
> 
> > implementation-dependent (ES 5.1, §9.8.1).
> 
> >
> 
> >> I only tested two, and you are aware of a very much wider range of
> 
> >> implementations than I am, so there may well be one.
> 
> >
> 
> > The fallacy here is “proof by example”.  It is a mistake for an author of an 
> 
> > ECMAScript script to base their design decisions on speculations about 
> 
> > possible implementations and their possible optimizations.
> 
> 
> 
> I don't follow -- I have not attempted to prove anything.  Are you
> 
> talking about your examples above?
> 
> 
> 
> I am acutely aware that I am posting from a position of relative
> 
> ignorance.  That's why I asked you for and example where the code you
> 
> posted (not each modification of my code) realises some or all of the
> 
> purported benefits.
> 
> 
> 
> If, on the other hand, you stand by the idea that one should not rely
> 
> on speculation about implementations and their possible optimisations, in
> 
> what sense do you justify calling your code "optimised"?  Surely your
> 
> changes were based on exactly that sort of speculation.
> 
> 
> 
> I know that the change in representation does not rely on speculation,
> 
> but the benefit of it (going beyond 2^32) does speculate on the
> 
> existence of an implementation that can execute the code fast enough to
> 
> get near to that number in some reasonable time.
> 
> 
> 
> >  Even the 
> 
> > optimizations in a specific implementation are moving targets.  In a 
> 
> > situation where you want to write cross-implementation code, but you have no 
> 
> > control over the actual runtime environment, you have to choose that which 
> 
> > is best for the task and probably best for *all* *targeted* implementations; 
> 
> > in the simplest case, all widely distributed ones *currently* in use.
> 
> 
> 
> Absolutely.  So how can your code be called optimised if it doesn't even
> 
> manage the posted task in one major implementation?
> 
> 
> 
> <patronising stuff snipped>
> 
> -- 
> 
> Ben.

I Think i've come up with a way to store them fairly searchable and very highly compresses for extremly large numbers. Store them as Squares cubic quarctic and so on.

I do not Think the trade of converting them to sum of Squares big, but what about cubic quarctic?

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

#21349

In comp.lang.javascript message <l0trp1$ef5$1@news.albasani.net>, Fri,
13 Sep 2013 04:03:13, Stefan Weiss <krewecherl@gmail.com> posted:

>
>On 2013-09-13 02:27, Thomas 'PointedEars' Lahn wrote:

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

Do you think that Lahn would like the Quantum Bogosort?

-- 
 (c) John Stockton, nr London UK               Reply address via Home Page.
   news:comp.lang.javascript FAQ <http://www.jibbering.com/faq/index.html>.
   <http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
   <http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

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

#21221

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

The only code in Javascript that i managed to download and execute took well over 1 min while my code run 17 seconds.

So what is wrong with this code?

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

<script type="text/javascript">

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;
 }
var start = new Date().getTime();
 sieve(20000000)
var end = new Date().getTime();
var time = end - start;
alert('Execution time: ' + time);
</script>
<body>
<div id="output"></div>
</body>
</html>

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

#21255

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.

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

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

csiph-web