4
$\begingroup$

Are any algorithms known that can compute the greatest common denominator of multiple (more than two) input values more efficiently than just an iterative application of the fastest GCD algorithm for exactly two input values? E.g. gcd(a, b, c, ...) vs. gcd(a, gcd(b, gcd(c, ...)))

If so, then what is such an algorithm?

If not, then is it known whether there cannot exist such an algorithm?

$\endgroup$
  • $\begingroup$ Asymptotic runtime (average and/or worst-case) as a function of the number of inputs where it may be assumed that all inputs are of sufficiently similar size as to be approximated to be the same size. As far as how the runtime is measured, is there any model for which the answer to my question is "yes"? $\endgroup$ – Travis May 15 '17 at 4:43
  • $\begingroup$ @D.W. Please combine and post your comments (especially the second) as an answer and I will accept it, as it appears as close to a direct answer as will be possible for my question. $\endgroup$ – Travis May 15 '17 at 23:24
2
$\begingroup$

As Wikipedia reports, the fastest currently known algorithm for the gcd of two $n$-bit numbers runs in $O(n f(n))$ time where $f(n)$ is a slow-growing function of $n$ (roughly $\log n \cdot \log \log n$). It is not known whether the gcd of two $n$-bit numbers can be computed in $O(n)$ time.

This means that the iterative algorithm for computing the gcd of $k$ $n$-bit numbers (as described in the question) runs in $O(kn f(n))$ time. Obviously, any algorithm needs at least $\Omega(kn)$ time -- this lower bound follows from the fact that any algorithm needs to read the entire input. This doesn't leave much of a gap between the trivial lower bound and the running time of the iterative algorithm. In other words, it doesn't leave much room for improvement in running time.


That's the theoretical answer. From a pragmatic perspective, the $O(n f(n))$-time algorithms only become faster than (asymptotically slower) alternatives once $n$ is fairly large. As a result, if $n$ is not too large, these results might not mean much.

Also, from a pragmatic perspective, we can expect that $\gcd(a,\gcd(b,\gcd(c,d)))$ might be faster than $\gcd(\gcd(a,b),\gcd(c,d))$. They both yield the same answer, but the former might often be faster, because typically one of the two arguments to the gcd will be small. Computing $\gcd(x,y)$ might be faster in practice if $y$ is much smaller than $x$ (because the first step is to replace $y$ with $y \bmod x$) than when $x,y$ are about the same size. So, you might benefit by performing the gcd's in an order that gets you down to a small number as soon as possible.

$\endgroup$
-1
$\begingroup$

The runtime of gcd depends on the size of the result relative to the size of the inputs, especially the smaller input.

If you start with inputs of equal size, the runtime depends on the ratio between inputs and final result. Best to calculate x = gcd (a, b), y = gcd (x, c) and so on.

$\endgroup$
  • $\begingroup$ I'm not seeing how this answers the question. The question was whether there is a faster strategy. So is there? You list a strategy, but don't indicate whether it is faster than the iterative strategy in the question -- in fact, it looks like your strategy is equivalent to the iterative strategy in the question (just reverse the order of the numbers and your strategy is identical to the one in the question). $\endgroup$ – D.W. May 15 '17 at 21:20

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.