#   This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: Type: fractions.gcd failure behavior Library (Lib) Python 3.1, Python 3.2, Python 3.3, Python 3.4, Python 3.5, Python 2.7
process
Status: Resolution: closed wont fix mark.dickinson, pacosta, rhettinger, tim.peters normal

Created on 2014-06-11 01:23 by pacosta, last changed 2022-04-11 14:58 by admin. This issue is now closed.

Messages (7)
msg220221 - (view) Author: Pablo Acosta (pacosta) Date: 2014-06-11 01:23
```The Greatest Common Divisor (gcd) algorithm sometimes breaks because the modulo operation does not always return a strict integer number, but one very, very close to one. This is enough to drive the algorithm astray from that point on.

Example:

>> import fractions
>> fractions.gcd(48, 18)
>> 6

Which is corret, but:

>> fractions.gcd(2.7, 107.3)
>> 8.881784197001252e-16

when the answer should be 1. The fix seems simple, just cast the mod() operation in the algorithm:

while b:
a, b = b, int(a%b)
return a```
msg220222 - (view) Author: Pablo Acosta (pacosta) Date: 2014-06-11 01:26
`Actually probably int(round(a%b)) would be better.`
msg220228 - (view) Author: Pablo Acosta (pacosta) Date: 2014-06-11 02:14
```I will correct myself one more time (hopefully the last):

while b:
a, b = b, round(a % b, 10)
return a

a	b	fractions.gcd		proposed_algorithm
----------------------------------------------------------
48	18	6			6
3	4	1			1
2.7	107.3	8.881784197001252e-16	0.1
200.1	333	2.842170943040401e-14	0.3
0.05	0.02	3.469446951953614e-18	0.01```
msg220231 - (view) Author: Tim Peters (tim.peters) * Date: 2014-06-11 02:43
```The gcd function is documented as taking two integer arguments:

"Return the greatest common divisor of the integers a and b."

I'm -0 on generalizing it, and also -0 on burning cycles to enforce the restriction to integer arguments.  It's just silly ;-)```
msg220260 - (view) Author: Mark Dickinson (mark.dickinson) * Date: 2014-06-11 12:25
```Agreed with Tim.

Oddly enough, remembering that with binary floating-point numbers, what you see is not what you get, it turns out that 8.881784197001252e-16 (= Fraction(1, 1125899906842624)) is in fact *exactly* the right answer, in that it's a generator for the additive subgroup of the rationals generated by 2.7 (= Fraction(3039929748475085, 1125899906842624)) and 107.3 (=Fraction(7550566250263347, 70368744177664)).

 Actually not so odd, given that % is a perfectly exact operation when applied to two positive finite floats.
 https://docs.python.org/2/tutorial/floatingpoint.html```
msg220299 - (view) Author: Tim Peters (tim.peters) * Date: 2014-06-11 18:52
```@pacosta, if Mark's answer is too abstract, here's a complete session showing that the result you got for gcd(2.7, 107.3) is in fact exactly correct:

>>> import fractions
>>> f1 = fractions.Fraction(2.7)
>>> f2 = fractions.Fraction(107.3)
>>> f1
Fraction(3039929748475085, 1125899906842624) # the true value of "2.7"
>>> f2
Fraction(7550566250263347, 70368744177664)   # the true value of "107.3"
>>> fractions.gcd(f1, f2)  # computed exactly with rational arithmetic
Fraction(1, 1125899906842624)
>>> float(_)
8.881784197001252e-16

But this will be surprising to most people, and probably useless to all people.  For that reason, passing non-integers to gcd() is simply a Bad Idea ;-)```
msg220301 - (view) Author: Pablo Acosta (pacosta) Date: 2014-06-11 18:54
```Understood and agreed. My bad too for not reading the documentation more carefully. Thank you for the detailed explanation.

Pablo

> On Jun 11, 2014, at 2:52 PM, Tim Peters <report@bugs.python.org> wrote:
>
>
> Tim Peters added the comment:
>
> @pacosta, if Mark's answer is too abstract, here's a complete session showing that the result you got for gcd(2.7, 107.3) is in fact exactly correct:
>
>>>> import fractions
>>>> f1 = fractions.Fraction(2.7)
>>>> f2 = fractions.Fraction(107.3)
>>>> f1
> Fraction(3039929748475085, 1125899906842624) # the true value of "2.7"
>>>> f2
> Fraction(7550566250263347, 70368744177664)   # the true value of "107.3"
>>>> fractions.gcd(f1, f2)  # computed exactly with rational arithmetic
> Fraction(1, 1125899906842624)
>>>> float(_)
> 8.881784197001252e-16
>
> But this will be surprising to most people, and probably useless to all people.  For that reason, passing non-integers to gcd() is simply a Bad Idea ;-)
>
> ----------
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <http://bugs.python.org/issue21712>
> _______________________________________```
History
Date User Action Args