4 ms·

You could probably speed things up a lot using isProbablePrime(), at least to pre-filter candidate numbers. (Assuming you're using this library: https://www.npm

• geonnave 9y ago
  I used isProbablePrime() before, when I had a 50x50 canvas. But it was still really really really slow. After changing to a 32x32 canvas, the difference between isPrime() and isProbablePrime() seemed negligible.
  • Retr0spectrum 9y ago
    Interesting. I guess in that case the only way to speed it up is with multithreading and/or asm.js.
  • schoen 9y ago
    That makes me think that their probable prime implementation isn't that great or else that they're losing a ton of efficiency to the Javascript interpreter. $ time python -c 'import gmpy; gmpy.next_prime(2**2500)' real 0m0.443s Was it taking a lot longer than that for you? Edit: I can see that there is an element of luck in terms of how many candidates you have to look at, but I'm still seeing everything in this size range take under 2 seconds. Maybe it's a question of what probability of error you're accepting from the test?
    • johndough 9y ago
      GMP is very well optimized and implemented in assembly. There's no way that a JavaScript implementation can get anywhere close to that performance since JavaScript doesn't even have support for 64 bit integers. WebAssembly might be faster, but is still lacking many instructions commonly used for big integer arithmetic.