Is Farey Sequence the fastest way to generate coprime pairs?

Viewed 646

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?

0 Answers
Related