View Single Post
Old 2019-01-21, 14:04   #24
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·32·191 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Has anybody tried the Trial Division algorithm : https://github.com/TilmanNeumann/jav...63Inverse.java ?

The idea is pretty simple:
Since we anyway compute a list of primes, why not also calculate the inverse of the prime as a double value and store it as well. Then instead of doing a trial division with this prime we multiply with its reciprocal. We have to check if this value is an integer. So we convert the value to long and see if this multiplied by the prime gives the back the original number to test.

We observed a reasonable speedup over standard trial division.
Yes, I did, and unfortunately I didn't see any speed improvement. Well, possibly there was a slight improvement at sizes > 50 bits, past the crossover point with rho.
bsquared is offline   Reply With Quote