Hacker News Reader

Comment by Retr0spectrum | Hacker News Reader

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.npmjs.com/package/big-integer#isprobableprimeite...)

View on HN

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.

Interesting. I guess in that case the only way to speed it up is with multithreading and/or asm.js.

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?

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.

Reply on news.ycombinator.com