View Single Post
Old 2003-08-01, 23:53   #8
ewmayer's Avatar
Sep 2002
Rep├║blica de California

2×5,791 Posts

Originally Posted by TravisT
it seems to me that there should be some way to short circuit this to just look for relatively prime or not, instead of finding out the greatest common divisor.
The definition of relative primality of x and y is GCD(x,y) = 1. The only remaining issues are how fast one can do a GCD, and how best to test RP among more than 2 integer inputs.

doing GCD's seems like factoring a number to see if it is prime ..
While a GCD may superficially look like a kind of factorization, it is in fact algorithmically completely different, and can be done much faster. To factor an N-digit integer takes exponential time, i.e. the amount of work needed grows faster than any finite power of the number of digits N. The fastest GCD algorithms, on the other hand, need just algebraic time, in fact they need only order of N*(log N)^2 work. That is only slightly larger than (say) a fast FFT-based multiply needs. (In fact a fast GCD involves O(log N) FFT-based muls, each of which needs O(N*log N) work, and multiplying these two together gives the overall cost.) Even a naive GCD needs just O(N^2) work.

Originally Posted by apocalypse
Why don't we need N choose 2 gcd's. Or are we not talking about pairwise relatively prime numbers?
I believe there are some optimizations to be gained by processing all N vectors in parallel - for one, we don't need to save a copy of any of the inputs. But I wouldn't expect a huge speedup from this, perhaps at most a factor of ~2.

The Gnu MP package has fast GCD algorithms of various kinds (and both regular and "extended" GCDs - the latter are handy for finding modular inverses).
ewmayer is offline   Reply With Quote