mersenneforum.org Dubious claim on wikipedia
 Register FAQ Search Today's Posts Mark Forums Read

 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 ) .
 2018-06-12, 20:07 #2 CRGreathouse     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/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 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post chalsall Lone Mersenne Hunters 21 2010-11-01 17:36 bearnol Miscellaneous Math 58 2010-09-05 17:48 ShiningArcanine Math 4 2008-09-02 20:41 Mindnar Lounge 28 2008-08-27 16:22 thechickenman Lone Mersenne Hunters 2 2006-05-18 23:35

All times are UTC. The time now is 04:07.

Thu Nov 26 04:07:55 UTC 2020 up 77 days, 1:18, 3 users, load averages: 2.49, 2.01, 1.66