20180612, 19:09  #1 
Jun 2018
1 Posts 
Dubious claim on wikipedia
Wikipedia claims that an integer gcd can be calculated in asymptotically linear time. Of course there is no citation. Looking at the source for GMP, it appears to use only the standard euclidean method and the extended version. There is also no other reference to this magical algorithm that is easy to find with a search engine. Is the entire paragraph just bullshit?
from here: https://en.wikipedia.org/wiki/Greatest_common_divisor However, if a fast multiplication algorithm is used, one may modify the Euclidean algorithm for improving the complexity, but the computation of a greatest common divisor becomes slower than the multiplication. More precisely, if the multiplication of two integers of n bits takes a time of T(n), then the fastest known algorithm for greatest common divisor has a complexity O ( T ( n ) log n ) . This implies that the fastest known algorithm has a complexity of O ( n ( log n ) 2 log log n ) . 
20180612, 20:07  #2 
Aug 2006
2×2,969 Posts 
It's not claiming linear time, where do you get that idea?
GMP certainly does not use the Euclidean algorithm, it uses subquadratic methods  specifically Möller's algorithm, which Wikipedia refers to as "Schönhage controlled Euclidean descent algorithm". https://gmplib.org/manual/SubquadraticGCD.html If you use SchönhageStrassen multiplication you get the desired performance. You can do (technically, slightly) even better if you use Fürer's algorithm or any of its derivatives. 
20180613, 11:42  #3 
Tribal Bullet
Oct 2004
3×1,163 Posts 
GMP for many years did use only the basic algorithms, although subquadratic GCD patches were available. One of the reasons GMP was forked to become MPIR was that patches like this were felt to be languishing even though there was a clear need for them.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Perhaps the independent LMHs should claim ranges?  chalsall  Lone Mersenne Hunters  21  20101101 17:36 
EFF claim(s)  bearnol  Miscellaneous Math  58  20100905 17:48 
Inconsistencies on Wikipedia?  ShiningArcanine  Math  4  20080902 20:41 
GIMPS may not claim $100,000  Mindnar  Lounge  28  20080827 16:22 
57M to 58M to 62 (Chickenman continues to claim exponents like a Homesteader)  thechickenman  Lone Mersenne Hunters  2  20060518 23:35 