Go Back > Extra Stuff > Miscellaneous Math

Thread Tools
Old 2018-06-12, 19:09   #1
Jun 2018

1 Posts
Default 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:

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 ) .
dfff is offline   Reply With Quote
Old 2018-06-12, 20:07   #2
CRGreathouse's Avatar
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".

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.
CRGreathouse is offline   Reply With Quote
Old 2018-06-13, 11:42   #3
Tribal Bullet
jasonp's Avatar
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.
jasonp is offline   Reply With Quote

Thread Tools

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.