Message227444
Whether or not gcd(a, b) == gcd(|a|, |b|) depends on the definition if
we believe to Stepanov of C++ STL fame who mentions in his lecture [1]
[1] http://www.stepanovpapers.com/gcd.pdf
that the current implementation that uses two operation __bool__ and
__mod__:
def gcd(a, b):
while b:
a, b = b, a%b
return a
can be applied to Euclidean ring elements (not just positive or
negative integers). Despite Knuth’s objection to gcd(1, -1) = -1,
adding `if a < 0: a = -a` at the end changes the requirements for the
type. Here's the definition from the lecture [1]:
Greatest common divisor is a common divisor that is divisible by any
other common divisor.
I have no opinion on whether or not fractions.gcd() should be changed.
I thought that I should mention that different definitions exist. |
|
Date |
User |
Action |
Args |
2014-09-24 11:43:39 | akira | set | recipients:
+ akira, mark.dickinson, scoder, vstinner, gladman, brg@gladman.plus.com |
2014-09-24 11:43:39 | akira | set | messageid: <1411559019.22.0.206084672255.issue22477@psf.upfronthosting.co.za> |
2014-09-24 11:43:39 | akira | link | issue22477 messages |
2014-09-24 11:43:38 | akira | create | |
|