mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-06-12, 19:09   #1
dfff
 
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:
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 ) .
dfff is offline   Reply With Quote
Old 2018-06-12, 20:07   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

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

3×1,163 Posts
Default

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
Reply

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.