Dubious claim on wikipedia

dfff · 2018-06-12, 19:09

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 ) .

CRGreathouse · 2018-06-12, 20:07

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/Subquadratic-GCD.html

If you use Schönhage-Strassen 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.

jasonp · 2018-06-13, 11:42

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.

2018-06-12, 19:09	#1
dfff 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 ) .

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Perhaps the independent LMHs should claim ranges?	chalsall	Lone Mersenne Hunters	21	2010-11-01 17:36
EFF claim(s)	bearnol	Miscellaneous Math	58	2010-09-05 17:48
Inconsistencies on Wikipedia?	ShiningArcanine	Math	4	2008-09-02 20:41
GIMPS may not claim $100,000	Mindnar	Lounge	28	2008-08-27 16:22
57M to 58M to 62 (Chickenman continues to claim exponents like a Homesteader)	thechickenman	Lone Mersenne Hunters	2	2006-05-18 23:35

2018-06-12, 20:07	#2
CRGreathouse Aug 2006 3·1,993 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/Subquadratic-GCD.html If you use Schönhage-Strassen 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.

2018-06-13, 11:42	#3
jasonp Tribal Bullet Oct 2004 6727₈ 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.