[issue21712] fractions.gcd failure
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. 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 -- 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 <http://bugs.python.org/issue21712> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21712] fractions.gcd failure
Pablo Acosta added the comment: Actually probably int(round(a%b)) would be better. -- ___ Python tracker <http://bugs.python.org/issue21712> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21712] fractions.gcd failure
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.050.023.469446951953614e-18 0.01 -- ___ Python tracker <http://bugs.python.org/issue21712> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue21712] fractions.gcd failure
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 > On Jun 11, 2014, at 2:52 PM, Tim Peters 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 > <http://bugs.python.org/issue21712> > ___ -- ___ Python tracker <http://bugs.python.org/issue21712> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
