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

Actually probably int(round(a%b)) would be better.

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

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 ;-)

Agreed with Tim.

Oddly enough[1], remembering that with binary floating-point numbers, what you see is not what you get[2], 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)).

[1] Actually not so odd, given that % is a perfectly exact operation when applied to two positive finite floats.
[2] https://docs.python.org/2/tutorial/floatingpoint.html

@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 ;-)

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>
> _______________________________________