On Sat, Jul 14, 2018 at 03:39:25PM -0500, Tim Peters wrote: > While my code had no fluff at all. It's hard to believe you could add > enough cruft to slow it down by a factor of 1000,
There's a factor of 20 because my computer is older and slower than yours. (I ran your version, and it was ~20 times slower on my computer than the numbers you give.) So the cruft factor is only 50 times :) > but pretty much > impossible to believe adding cruft could make it way faster in the middle > case above. > > Or do you first try division by small primes? 2**900+1 could get out cheap > in that case, because it happens to be divisible by 17. Yes indeed. My approach is: 1. trial division by small primes; 2. Miller-Rabin by a minimal set of provably deterministic witnesses (if such a set exists, which it does for n < 2**64); 3. or by the first twelve primes if no such known set exists; 4. followed by 30 random witnesses. 12+30 = 42 Miller-Rabin tests may be overkill :-) -- Steve _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
