[Python-ideas] Add the imath module
Steven D'Aprano
steve at pearwood.info
Sat Jul 14 20:59:42 EDT 2018
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
More information about the Python-ideas
mailing list