5 ms·
"On my machine, testing the prime number 27,644,437 took about 1.2 milliseconds with a k value of 50 (far higher than you’ll probably need for your applications
by VikingCoder 15y ago
"On my machine, testing the prime number 27,644,437 took about 1.2 milliseconds with a k value of 50 (far higher than you’ll probably need for your applications.)"
I'm sorry, but WHAT?
Writing the dumbest implementation of trial-division that I could, in C++ on my laptop, in Debug mode, took 0.0247046 ms to determine definitively if 27,644,437 is prime.
My dumbest-possible implementation, in Debug mode, is 48.5 times faster, and doesn't get confused by Carmichael numbers.
Move along, folks, nothing to see here.
"The trial-division method... gets slow quickly."
That may be true, but using the number 27,644,437 as a benchmark will not get you anywhere near that "slow" point.
- ocharles 15y agoCould we see this code as well then?
- VikingCoder 15y agohttps://gist.github.com/1507400 https://gist.github.com/1507400 I unfortunately can't share all of the code, because of the timer code I used.
- dpkendal 15y agoI'm fairly sure that most of that 48x difference will come from the fact that you're using C++. I tested it in Scheme, a much slower language. (Actually, it was in Arc, which compiles to Scheme, but is still even slower.)