Path: csiph.com!usenet.pasdenom.info!dedibox.gegeweb.org!gegeweb.eu!nntpfeed.proxad.net!proxad.net!feeder2-2.proxad.net!newsfeed.arcor.de!newsspool4.arcor-online.net!news.arcor.de.POSTED!not-for-mail Content-Type: text/plain; charset="UTF-8" Message-ID: <7523620.37GnReVopu@PointedEars.de> From: Thomas 'PointedEars' Lahn Reply-To: Thomas 'PointedEars' Lahn Organization: PointedEars Software (PES) Date: Fri, 13 Sep 2013 19:13:52 +0200 User-Agent: KNode/4.10.5 Content-Transfer-Encoding: 8Bit X-Face: %i>XG-yXR'\"2P/C_aO%~;2o~?g0pPKmbOw^=NT`tprDEf++D.m7"}HW6.#=U:?2GGctkL,f89@H46O$ASoW&?s}.k+&. <3251928.WeJvBNZfad@PointedEars.de> <10475868.RPHzNtd8jb@PointedEars.de> MIME-Version: 1.0 Lines: 245 NNTP-Posting-Date: 13 Sep 2013 19:13:55 CEST NNTP-Posting-Host: 861a72e2.newsspool4.arcor-online.net X-Trace: DXC=BYIWo=b6DnnFXUDVUnEXQm4IUK 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] 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): > 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 ,- | | 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.