What is the fastest way to check if two given numbers are coprime?

Question

One way is to calculate their gcd and check if it is 1.

Is there some faster way?

Anthem

Answer 1

The Euclidean algorithm (computes gcd) is very fast. When two numbers are drawn uniformly at random from [1, n], the average number of steps to compute their gcd is O(log n). The average computation time required for each step is quadratic in the number of digits.

There are alternatives that perform somewhat better (i.e., each step is subquadratic in the number of digits), but they are only effective on very large integers. See, for example, On Schönhage's algorithm and subquadratic integer gcd computation.

Homophonic

I'd like to comment that it's a bit coarse to measure complexity of arithmetic algorithms without taking costs of arithmetic operations into account. – Ranchero

The worstcase # of steps is O(log n) as well, when two numbers are successive entries in the Fibonacci sequence. – Acred

@Pavel Shved: I did take the cost into consideration. cf. the sentence "The average computation time required for each step is quadratic in the number of digits." – Homophonic

Answer 2

if you're running on a machine for which division/remainder is significantly more expensive than shifts, consider binary GCD.

Acred

Just implemented this in f# and its more than 2x faster than traditional Euclid's GCD, cannot give exact numbers as there is other code poluting my measurements, however its > 2x faster. Good find Jason. – Muskogean

Update: Did better numbers in isolation: Iterations: 100000, Euclid Took: 27ms, Binary GCD Tool: 11ms (so that's about 40% of Euclid). Awesome! – Muskogean

@Muskogean Care to do a gist of your F# ? – Plosion

@javadba check out here last function called binGcd – Muskogean

anyone have a js version? – Offspring