Skip to content

GCD - Greatest Common Divisor

Author: Mark Gotham

integer_gcd_pair 

integer_gcd_pair(a: int, b: int) -> int

Calculates the greatest common divisor (GCD) of two integers using the Euclidean algorithm.

integer_gcd_pair(0, 2) 2

integer_gcd_pair(15, 16) 1

integer_gcd_pair(8, 16) 8

Source code in amads/algorithms/gcd.py 
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def integer_gcd_pair(a: int, b: int) -> int:
    """
    Calculates the greatest common divisor (GCD) of two integers using the
    Euclidean algorithm.

    >>> integer_gcd_pair(0, 2)
    2

    >>> integer_gcd_pair(15, 16)
    1

    >>> integer_gcd_pair(8, 16)
    8

    """
    while b:
        a, b = b, a % b
    return a

float_gcd_pair 

float_gcd_pair(
    a: float, b: float = 1.0, rtol=1e-05, atol=1e-08
) -> float

Calculate approximate greatest common divisor (GCD) for values a and b given the specified relative and absolute tolerance (rtol and atol). With thanks to Euclid, fractions.gcd, and stackexchange <https://stackoverflow.com/questions/45323619/>_.

Tolerance values should be set in relation to the granularity (e.g., pre-rounding) of the input data.

Warning 
Float GCD calcualtion is inherently approximate.
Mixing floats with other types in
`calculate_gcd` will reduce reliability.
Prefer `Fraction` where possible.
For solutions specific to music, see other modeules in this repo,
notably `grid`.

Parameters:

  • a (float) –

    Any float value.

  • b (float, default: 1.0 ) –

    Any float value, though typically 1.0 (default) for our use case of measure-relative positioning.

  • rtol –

    the relative tolerance

  • atol –

    the absolute tolerance

Examples:

At risk of failure in both directions. Default tolerance values fail simple cases (2 / 3 to 4d.p.):

>>> round(float_gcd_pair(0.6667), 3) # failure
0.0

Leaving the value the same, but changing the tolerance to accommodate:

>>> round(float_gcd_pair(0.6667, atol=0.001, rtol=0.001), 3) # success
0.333

But this same kind of tolerance adjustment can make errors for other, common musical values. 15/16 is a common musical value for which the finer tolerance is effective:

>>> fifteen_sixteenths = 15/16
>>> round(1 / float_gcd_pair(fifteen_sixteenths)) # success
16

>>> round(1 / float_gcd_pair(fifteen_sixteenths, atol=0.001, rtol=0.001)) # success
16

>>> fifteen_sixteenths_3dp = round(fifteen_sixteenths, 3)
>>> round(1 / float_gcd_pair(fifteen_sixteenths_3dp)) # failure
500

>>> round(1 / float_gcd_pair(fifteen_sixteenths_3dp, atol=0.001, rtol=0.001)) # failure
500

Note that both-zero inputs return zero:

>>> float_gcd_pair(0.0, 0.0)
0.0
Source code in amads/algorithms/gcd.py 
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
def float_gcd_pair(a: float, b: float = 1.0, rtol=1e-05, atol=1e-08) -> float:
    """
    Calculate approximate greatest common divisor (GCD) for values a and b given the specified
    relative and absolute tolerance (`rtol` and `atol`).
    With thanks to Euclid,
    `fractions.gcd`, and
    `stackexchange <https://stackoverflow.com/questions/45323619/>`_.

    Tolerance values should be set in relation to the granularity
    (e.g., pre-rounding) of the input data.

    Warning
    -------
        Float GCD calcualtion is inherently approximate.
        Mixing floats with other types in
        `calculate_gcd` will reduce reliability.
        Prefer `Fraction` where possible.
        For solutions specific to music, see other modeules in this repo,
        notably `grid`.

    Parameters
    ----------
    a: float
        Any float value.
    b: float
        Any float value, though typically 1.0 (default) for our use case
        of measure-relative positioning.
    rtol
        the relative tolerance
    atol
        the absolute tolerance

    Examples
    --------
    At risk of failure in both directions.
    Default tolerance values fail simple cases (2 / 3 to 4d.p.):
    >>> round(float_gcd_pair(0.6667), 3) # failure
    0.0

    Leaving the value the same, but changing the tolerance to accommodate:
    >>> round(float_gcd_pair(0.6667, atol=0.001, rtol=0.001), 3) # success
    0.333

    But this same kind of tolerance adjustment can make errors for other,
    common musical values.
    15/16 is a common musical value for which the finer tolerance is effective:

    >>> fifteen_sixteenths = 15/16
    >>> round(1 / float_gcd_pair(fifteen_sixteenths)) # success
    16

    >>> round(1 / float_gcd_pair(fifteen_sixteenths, atol=0.001, rtol=0.001)) # success
    16

    >>> fifteen_sixteenths_3dp = round(fifteen_sixteenths, 3)
    >>> round(1 / float_gcd_pair(fifteen_sixteenths_3dp)) # failure
    500

    >>> round(1 / float_gcd_pair(fifteen_sixteenths_3dp, atol=0.001, rtol=0.001)) # failure
    500

    Note that both-zero inputs return zero:
    >>> float_gcd_pair(0.0, 0.0)
    0.0

    """
    if a == 0.0 and b == 0.0:
        return 0.0
    t = min(abs(a), abs(b))
    while abs(b) > rtol * t + atol:
        a, b = b, a % b
    return a

lcm_pair 

lcm_pair(a: int, b: int) -> int

Compute the Lowest Common Multiple (LCM) of two integers.

lcm_pair(8, 16) 16

lcm_pair(2, 3) 6

Source code in amads/algorithms/gcd.py 
119
120
121
122
123
124
125
126
127
128
129
130
def lcm_pair(a: int, b: int) -> int:
    """
    Compute the Lowest Common Multiple (LCM) of two integers.

    >>> lcm_pair(8, 16)
    16

    >>> lcm_pair(2, 3)
    6

    """
    return a * b // integer_gcd_pair(a, b)

fraction_gcd_pair 

fraction_gcd_pair(x: Fraction, y: Fraction) -> Fraction

Compute the GCD of two fractions using the equivalence between gcd(a/b, c/d) and gcd(a, c)/lcm(b, d)

This function compares exactly two fractions (x and y). For a longer list, use fraction_gcd.

Returns:

  • Fraction –

    The GCD of x and y, which is always simplified.

Examples:

>>> fraction_gcd_pair(Fraction(1, 2), Fraction(2, 3))
Fraction(1, 6)
Source code in amads/algorithms/gcd.py 
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
def fraction_gcd_pair(x: Fraction, y: Fraction) -> Fraction:
    """
    Compute the GCD of two fractions using the
    equivalence between gcd(a/b, c/d) and gcd(a, c)/lcm(b, d)

    This function compares exactly two fractions (x and y).
    For a longer list, use `fraction_gcd`.

    Returns
    -------
    Fraction
        The GCD of `x` and `y`, which is always simplified.

    Examples
    --------
    >>> fraction_gcd_pair(Fraction(1, 2), Fraction(2, 3))
    Fraction(1, 6)

    """
    return Fraction(
        integer_gcd_pair(x.numerator, y.numerator),
        lcm_pair(x.denominator, y.denominator),
    )

fraction_gcd 

fraction_gcd(fractions: Sequence[Fraction]) -> Fraction

Compute GCD where all elements are known/asserted to be Fractions. See fraction_gcd_pair.

Raises:

  • ValueError –

    If fractions is empty.

Returns:

  • Fraction –

    The GCD of all Fractions in fractions.

Examples:

>>> fraction_gcd([Fraction(1, 2), Fraction(2, 3), Fraction(5, 12)])
Fraction(1, 12)
Source code in amads/algorithms/gcd.py 
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
def fraction_gcd(fractions: Sequence[Fraction]) -> Fraction:
    """
    Compute GCD where all elements are known/asserted to be Fractions.
    See `fraction_gcd_pair`.

    Raises
    ------
    ValueError
        If `fractions` is empty.

    Returns
    -------
    Fraction
        The GCD of all Fractions in `fractions`.

    Examples
    --------
    >>> fraction_gcd([Fraction(1, 2), Fraction(2, 3), Fraction(5, 12)])
    Fraction(1, 12)

    """
    if not fractions:
        raise ValueError("fractions must not be empty")
    gcd = fractions[0]
    for i in range(1, len(fractions)):
        gcd = fraction_gcd_pair(gcd, fractions[i])
    return gcd

float_gcd 

float_gcd(floats: Sequence[float], rtol=1e-05, atol=1e-08) -> float

Calculate GCD for a list of floats given the specified relative and absolute tolerance (rtol and atol).

If the values are known to be integers use integer_gcd, known to be Fractions use fraction_gcd, and if the type is not known use calculate_gcd.

Warning 
Float GCD is inherently approximate.
See `float_gcd_pair` for details.

Raises:

  • ValueError –

    If floats is empty.

Parameters:

  • floats (Sequence[float]) –

    Any float values.

  • rtol –

    the relative tolerance

  • atol –

    the absolute tolerance

Source code in amads/algorithms/gcd.py 
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
def float_gcd(floats: Sequence[float], rtol=1e-05, atol=1e-08) -> float:
    """
    Calculate GCD for a list of floats given the specified
    relative and absolute tolerance (`rtol` and `atol`).

    If the values are known to be integers use `integer_gcd`, known to be
    Fractions use `fraction_gcd`, and if the type is not known use
    `calculate_gcd`.

    Warning
    -------
        Float GCD is inherently approximate.
        See `float_gcd_pair` for details.

    Raises
    ------
    ValueError
        If `floats` is empty.

    Parameters
    ----------
    floats: list[float]
        Any float values.
    rtol
        the relative tolerance
    atol
        the absolute tolerance

    """
    if not floats:
        raise ValueError("floats must not be empty")
    gcd = floats[0]
    for i in range(1, len(floats)):
        gcd = float_gcd_pair(gcd, floats[i], rtol=rtol, atol=atol)
    return gcd

integer_gcd 

integer_gcd(integers: Sequence[int]) -> int

Compute GCD where the elements are known/asserted to be integers. See integer_gcd_pair.

Raises:

  • ValueError –

    If integers is empty. Note that this diverges from math.gcd.

Returns:

  • int –

    The GCD of all elements in the list.

Examples:

>>> integer_gcd([0, 2, 4])
2

>>> integer_gcd([0, 15, 16])
1

>>> integer_gcd([0, 8, 16])
8

Zero returns 0 ...

>>> integer_gcd([0])
0

... but nothing raises an error.

>>> integer_gcd([])
Traceback (most recent call last):
ValueError: integers must not be empty
Source code in amads/algorithms/gcd.py 
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
def integer_gcd(integers: Sequence[int]) -> int:
    """
    Compute GCD where the elements are known/asserted to be integers.
    See `integer_gcd_pair`.

    Raises
    ------
    ValueError
        If `integers` is empty.
        Note that this diverges from `math.gcd`.

    Returns
    -------
    int
        The GCD of all elements in the list.

    Examples
    --------
    >>> integer_gcd([0, 2, 4])
    2

    >>> integer_gcd([0, 15, 16])
    1

    >>> integer_gcd([0, 8, 16])
    8

    Zero returns 0 ...
    >>> integer_gcd([0])
    0

    ... but nothing raises an error.
    >>> integer_gcd([])
    Traceback (most recent call last):
    ValueError: integers must not be empty

    """
    if not integers:
        raise ValueError("integers must not be empty")
    gcd = integers[0]
    for i in range(1, len(integers)):
        gcd = integer_gcd_pair(gcd, integers[i])
    return gcd

calculate_gcd 

calculate_gcd(numbers: Sequence)

Compute GCD. Wrapper function when you don't know the type of the numeric data. If the value type is known (integer, fractions, float), use the more specific {type}_gcd function.

Integers and fractions are lossless and processed first, before any floats.

Warning 
Mixing floats with other numeric types reduces reliability.
Prefer `Fraction` where possible.

Raises:

  • ValueError –

    If numbers is empty.

  • >>> calculate_gcd([1, 2]) –
  • Fraction(1, 1) –
  • >>> calculate_gcd([1, Fraction(1, 2), 2]) –
  • Fraction(1, 2) –
  • >>> calculate_gcd([0, 1/2]) –
  • 0.5 –
  • >>> calculate_gcd([0, Fraction(1, 2), 1/2]) –
  • Fraction(1, 2) –
  • >>> gcd = calculate_gcd([0, Fraction(1, 2), 4/12]) –
  • >>> round(gcd, 3) –
  • 0.167 –
  • All-float input is supported: –
  • >>> calculate_gcd([0.5, 0.25]) –
  • 0.25 –
Source code in amads/algorithms/gcd.py 
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
def calculate_gcd(numbers: Sequence):
    """
    Compute GCD.
    Wrapper function when you don't know the type of the numeric data.
    If the value type is known (integer, fractions, float),
    use the more specific ``{type}_gcd`` function.

    Integers and fractions are lossless and processed first, before any floats.

    Warning
    -------
        Mixing floats with other numeric types reduces reliability.
        Prefer `Fraction` where possible.

    Raises
    ------
    ValueError
        If `numbers` is empty.

    >>> calculate_gcd([1, 2])
    Fraction(1, 1)

    >>> calculate_gcd([1, Fraction(1, 2), 2])
    Fraction(1, 2)

    >>> calculate_gcd([0, 1/2])
    0.5

    >>> calculate_gcd([0, Fraction(1, 2), 1/2])
    Fraction(1, 2)

    >>> gcd = calculate_gcd([0, Fraction(1, 2), 4/12])
    >>> round(gcd, 3)
    0.167

    All-float input is supported:
    >>> calculate_gcd([0.5, 0.25])
    0.25

    """
    if not numbers:
        raise ValueError("numbers must not be empty")

    floats = [num for num in numbers if isinstance(num, float)]
    ints_fractions = [num for num in numbers if not isinstance(num, float)]

    if ints_fractions:
        gcd = Fraction(ints_fractions[0])
        for num in ints_fractions[1:]:
            gcd = fraction_gcd_pair(Fraction(num), gcd)
        for f in floats:
            gcd = float_gcd_pair(f, gcd)
    else:
        # All floats
        gcd = floats[0]
        for f in floats[1:]:
            gcd = float_gcd_pair(f, gcd)

    return gcd