fractions.gcd failure

[pacosta]

BPO	21712
Nosy	@tim-one, @rhettinger, @mdickinson

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2014-06-11.04:38:15.359>
created_at = <Date 2014-06-11.01:23:56.330>
labels = ['type-bug', 'library']
title = 'fractions.gcd failure'
updated_at = <Date 2014-06-11.18:54:30.741>
user = 'https://bugs.python.org/pacosta'

bugs.python.org fields:

activity = <Date 2014-06-11.18:54:30.741>
actor = 'pacosta'
assignee = 'none'
closed = True
closed_date = <Date 2014-06-11.04:38:15.359>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2014-06-11.01:23:56.330>
creator = 'pacosta'
dependencies = []
files = []
hgrepos = []
issue_num = 21712
keywords = []
message_count = 7.0
messages = ['220221', '220222', '220228', '220231', '220260', '220299', '220301']
nosy_count = 4.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'pacosta']
pr_nums = []
priority = 'normal'
resolution = 'wont fix'
stage = None
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue21712'
versions = ['Python 3.1', 'Python 2.7', 'Python 3.2', 'Python 3.3', 'Python 3.4', 'Python 3.5']

[pacosta]

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

[pacosta]

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

[pacosta]

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

[tim-one]

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

[mdickinson]

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

[tim-one]

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

[pacosta]

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

---