[issue21712] fractions.gcd failure

[Pablo Acosta]

New submission from Pablo Acosta:

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.

import fractions
fractions.gcd(48, 18)
6
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

----------
components: Library (Lib)
messages: 220221
nosy: pacosta
priority: normal
severity: normal
status: open
title: fractions.gcd failure
type: behavior
versions: Python 2.7, Python 3.1, Python 3.2, Python 3.3, Python 3.4, Python 3.5

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

[Pablo Acosta]

Pablo Acosta added the comment:

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

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

[Pablo Acosta]

Pablo Acosta added the comment:

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

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

[Ned Deily]

Changes by Ned Deily <nad at acm.org>:


----------
nosy: +mark.dickinson, rhettinger

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

[Tim Peters]

Tim Peters added the comment:

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

----------
nosy: +tim.peters

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

[Raymond Hettinger]

Changes by Raymond Hettinger <raymond.hettinger at gmail.com>:


----------
resolution: -> wont fix
status: open -> closed

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

[Mark Dickinson]

Mark Dickinson added the comment:

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

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

[Tim Peters]

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 at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

[Pablo Acosta]

Pablo Acosta added the comment:

Understood and agreed. My bad too for not reading the documentation more carefully. Thank you for the detailed explanation.

Pablo

Post by Tim Peters

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 at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21712>
_______________________________________