Slug #1359
gcd: low degree but big coeffs can be slow
Description
gcd of low degree polys with big coeffs can be too slow.
gcd(x+1, x+1+factorial(100000)); --> takes about 1.7s
Replacing 1000000 by 200000 increases the time to about 3.3s.
And going up to 500000 take about 7.4s.
Related issues
History
#1
Updated by John Abbott over 4 years ago
Updated by If the number of steps in the PRS is very small then a direct method may well be better than the modular method.
The CRT modular method may have to compute modulo a million or more primes, and then reconstruction also becomes costly.
#2
Updated by John Abbott over 4 years ago
- Related to Bug #1113: gcd crashes (Floating point exception) added
#3
Updated by John Abbott over 4 years ago
- Related to Slug #129: Better GCD added