I was looking for ways to generate coprime pairs up to a limit and after some searching I found multiple sources telling that Farey's Sequence is the fastest algorithm. Here are a few of those sources: Stackexchange, Quora.
This is the Farey's algorithm and a simple GCD:
from itertools import combinations
from math import gcd
def farey(limit):
'''Fast computation of Farey sequence as a generator'''
# n, d is the start fraction n/d (0,1) initially
# N, D is the stop fraction N/D (1,1) initially
pend = []
n = 0
d = N = D = 1
while True:
mediant_d = d + D
if mediant_d <= limit:
mediant_n = n + N
pend.append((mediant_n, mediant_d, N, D))
N = mediant_n
D = mediant_d
else:
yield n, d
if pend:
n, d, N, D = pend.pop()
else:
break
def simple_gcd(limit):
for A, B in combinations(range(limit+1), 2):
if gcd(A, B) == 1:
yield A, B
I checked if they produce the same output:
>>> count = 0
>>> for i in farey(10000):
count+=1
>>> count
30397486
>>> count = 0
>>> for i in simple_gcd(10000):
count+=1
>>> count
30397486
They do.
Yet my function is faster (even faster when outside of a function.)
>>> import timeit
>>> timeit.timeit("for i in farey(10000):pass", "from __main__ import farey", number=1)
16.637074244167408
>>> timeit.timeit("for i in simple_gcd(10000):pass", "from __main__ import simple_gcd", number=1)
16.504983127784428
>>> timeit.timeit("for A, B in itertools.combinations(range(10001), 2):\n if math.gcd(A, B)==1:pass", "import math, itertools", number=1)
15.035244938807324
So, is Farey Sequence really the fastest way to generate coprime pairs, and if not, what algorithm should I use?