Re: Strawmans prime sieve/filter

From	Stefan Weiss <krewecherl@gmail.com>
Newsgroups	comp.lang.javascript
Subject	Re: Strawmans prime sieve/filter
Date	2013-09-13 04:03 +0200
Organization	albasani.net
Message-ID	<l0trp1$ef5$1@news.albasani.net> (permalink)
References	(2 earlier) <a13c125d-e801-43e3-9e12-4355b40e22d2@googlegroups.com> <l0kcd7$ol$1@news.albasani.net> <3251928.WeJvBNZfad@PointedEars.de> <KIdkZJh1MhMSFwD1@invalid.uk.co.demon.merlyn.invalid> <10475868.RPHzNtd8jb@PointedEars.de>

Show all headers | View raw

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

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