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.
$\begingroup$
$\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$– Lutz LehmannDec 30, 2013 at 11:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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
