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

Groups > comp.lang.javascript > #21346

Re: Strawmans prime sieve/filter

Show all headers | View raw

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.

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