3

I'd like to compute the Greatest Common Divisor of two rational numbers implemented as fractions.Fraction instances. It works as expected although deprecation warning is printed:

In [1]: gcd(Fraction(2, 3), Fraction(2, 3))
/usr/local/bin/ipython:1: DeprecationWarning: fractions.gcd() is deprecated. Use math.gcd() instead.
  #!/usr/local/opt/python3/bin/python3.6
Out[1]: Fraction(1, 6)

Looking at the documentation I can see that fractions.gcd() is indeed deprecated and that users are invited to use math.gcd() instead. The problem is that the latter does not support rational numbers:

In [2]: gcd(Fraction(2, 3), Fraction(2, 3))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-c3ad2389f290> in <module>()
----> 1 gcd(Fraction(2, 3), Fraction(2, 3))

TypeError: 'Fraction' object cannot be interpreted as an integer

Which function can I use in replacement of fractions.gcd()? I'm not looking for the actual algorithm used here, but the replacement for the deprecated function.

SuperStormer
  • 4,997
  • 5
  • 25
  • 35
Jean-Baptiste
  • 907
  • 8
  • 17
  • 3
    As you appear to be using an undocumented feature of `fractions.gcd()` (documentation says "Return the greatest common divisor of the **integers** a and b"), there may not be one. – glibdud Apr 23 '18 at 12:45
  • You are right, I missed that! It definitely is not an expected behavior from what I can see in the actual implementation (https://github.com/python/cpython/blob/3.6/Lib/fractions.py)... Thanks! – Jean-Baptiste Apr 23 '18 at 12:53
  • 2
    I would consider `fractions.gcd()` working on fractions to be an expected behavior... – endolith Nov 19 '18 at 00:35
  • Your formula doesn't make sense; `denom_lcm` is a tuple – endolith Nov 19 '18 at 00:42

2 Answers2

5

You might have to write one. gcd(a/b, c/d) = gcd(a, c)/lcm(b, d), so this isn't too bad. math doesn't provide a lcm, so I'm using the one written here.

from fractions import Fraction
from math import gcd

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)

def fraction_gcd(x, y):
    a = x.numerator
    b = x.denominator
    c = y.numerator
    d = y.denominator
    return Fraction(gcd(a, c), lcm(b, d))

print(fraction_gcd(Fraction(2, 3), Fraction(2, 3)))
# 2/3
Patrick Haugh
  • 59,226
  • 13
  • 88
  • 96
0

Note: The following was originally edited into the question body itself by the original poster. I have moved it into a separate answer.

As mentioned by @glibdud in his comment, using fractions.gcd() with rational numbers is not an expected behavior and certainly not documented... and it can easily be implemented using:

def gcd(numbers):
"""Compute Greastest Common Divisor of rational numbers.

Args:
    numbers: list of rational numbers.

Returns:
    Greatest Common Divisor of rational numbers.
"""
# Treat the two-number case and reduce
def _gcd(a, b):
    if b == 0:
        return a
    if isinstance(a, int) and isinstance(b, int):
        _gcd(b, a % b)
    a = Fraction(a)
    b = Fraction(b)
    return Fraction(gcd([a.numerator, b.numerator]), lcm([a.denominator, b.denominator]))

return reduce(_gcd, numbers)

def lcm(numbers):
    """Compute Least Common Multiple of rational numbers.

    Args:
        numbers: list of rational numbers.

    Returns:
        Least Common Multiple of rational numbers.
    """
    # Treat the two-number case and reduce
    def _lcm(a, b):
        if b == 0:
            return a
        if isinstance(a, int) and isinstance(b, int):
            return a * b // gcd([a, b])
        a = Fraction(a)
        b = Fraction(b)
        return Fraction(lcm([a.numerator, b.numerator]), gcd([a.denominator, b.denominator]))

    return reduce(_lcm, numbers)

The formula is derived and explained here: https://math.stackexchange.com/questions/44836/rational-numbers-lcm-and-hcf.

SuperStormer
  • 4,997
  • 5
  • 25
  • 35