2
$\begingroup$

I want to know the best optimal algoritm of gcd with its complexity if you have a any useful source I will be glad to have a look at it.

$\endgroup$
  • 2
    $\begingroup$ Lehmers algorithm is quite good. Essentially divide-and-conquer, building up the Bezout identity from the leading digits on. -- Perhaps you should clarify if it is the integer gcd or the polynomial gcd, for the latter, subresultants may be the way to go. $\endgroup$ – Dr. Lutz Lehmann Dec 30 '13 at 11:17
2
$\begingroup$

Current state of the art uses variants of Euclid's algorithm. Yet, it is proven to be non-optimal:

http://dspace.ucalgary.ca/bitstream/1880/46601/2/1989-376-38.pdf

Even though its variants have significant speed improvements, I have not heard of a sequential optimal one. I guess one of the best modifications is Lehmer's algorithm. Extended Euclidean algorithms are also worth mentioning.

Furthermore, I guess optimality, or at least guaranteed bounds are obtained on parallel machines. One of such profound works prove a sequential complexity of O(n^2/log(n)) while achieving a paralel complexity, which is worth taking a look at :

http://www.csie.nuk.edu.tw/~cychen/gcd/Two%20fast%20GCD%20algorithms.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.