patternMinor
Efficient N-Ary GCD Algorithm
Viewed 0 times
gcdefficientaryalgorithm
Problem
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.
If so, then what is such an algorithm?
If not, then is it known whether there cannot exist such an algorithm?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#75387, answer score: 2
Revisions (0)
No revisions yet.