Last active
October 11, 2021 17:41
-
-
Save trevnorris/3955671 to your computer and use it in GitHub Desktop.
fastest js prime generator been able to get
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Thanks to @isntitvacant (https://github.com/chrisdickinson) for optimizing the | |
// bit shift performance tweaks. | |
var SB = require('buffer').SlowBuffer; | |
var ITER = 2e4; | |
var SIZE = 1e3; | |
function genPrimes(max) { | |
var primes = new Array(); | |
var len = (max >>> 3) + 1; | |
var sieve = new SB(len); | |
var cntr = 0; | |
var x = 2; | |
var j; | |
sieve.fill(0xff, 0, len); | |
for (cntr = 0, x = 2; x <= max; ++x) { | |
if (sieve[x >>> 3] & (1 << (x & 7))) { | |
primes[cntr++] = x | |
for(j = 2 * x; j <= max; j += x) | |
sieve[j >>> 3] &= ~(1 << (j & 7)) | |
} | |
} | |
return primes; | |
} | |
var t = process.hrtime(); | |
for (var i = 0; i < ITER; i++) | |
genPrimes(SIZE); | |
t = process.hrtime(t); | |
console.log(((t[0] * 1e6 + t[1] / 1e3) / ITER).toFixed(1) + ' us/op'); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This implementation - primes-generator makes the best of it. It includes calculation of the optimum buffer size, for best memory use. Can generate the first 100mln primes in under 8s.