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$
1
  • 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$ Dec 30, 2013 at 11:17

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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