Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

perf: check for divisibility by small primes #2

Merged

Conversation

ForbesLindesay
Copy link
Contributor

@ForbesLindesay ForbesLindesay commented Apr 29, 2022

In my tests, this results in the prime searching process running approximately twice as fast. I believe this happens because:

  1. A very large proportion of the candidates can be eliminated by checking them for divisibility with the first 2,000 primes.
  2. Checking against the first 2,000 primes is very fast, even when single threaded in JavaScript.
  3. Calling out to OpenSSL via the terminal adds considerable overhead/latency

Benchmarks on the sample image (higher is better)

The old code that always uses OpenSSL

36.7 prime candidates tested per second
37.5 prime candidates tested per second
33.7 prime candidates tested per second

My version that first checks for divisibility by small primes

60.5 prime candidates tested per second
86.5 prime candidates tested per second
95.6 prime candidates tested per second

In my tests, this results in the prime searching process running approximately twice as fast. I believe this happens because:

1. A very large proportion of the candidates can be eliminated by checking them for divisibility with the first 2,000 primes.
2. Checking against the first 2,000 primes is very fast, even when single threaded in JavaScript.
3. Calling out to OpenSSL via the terminal adds considerable overhead/latency
@TotalTechGeek
Copy link
Owner

Oh cool! I'll try to benchmark & potentially merge this later!

That makes perfect sense! OpenSSL also implements trial divisions, which is why I didn't think it'd be worth it, but this is cool! :)

@ForbesLindesay
Copy link
Contributor Author

I'm also going to have a go at using node.js worker_threads with all the prime testing code in node.js and see how that compares to calling openSSL, but thought this was worth sharing while I look into that.

primeSearch.js Outdated Show resolved Hide resolved
@TotalTechGeek TotalTechGeek merged commit a1283c3 into TotalTechGeek:master Apr 29, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants