The Euclidean Algorithm only needs %. The*Extended* Euclidean Algorithm can
use divmod.
The code below is from my cryptography course last semester, where I wanted
to use polymorphism and have the xgcd also work for my polynomial classes
implementing finite fields. Hence I do not take absolute values that give
the official definition with integers. I kept the function docs for
integers, and they would get a lot shorter if you just threw in the absolute
value (or assume nonnegative inputs).
Andy
#! /usr/bin/python
def gcd(a,b):
"""Returns the gcd of its inputs times the sign of b if b is nonzero,
and times the sign of a if b is 0.
"""
while b != 0:
a,b = b, a % b
return a
def xgcd(a,b):
"""Extended GCD:
Returns (gcd, x, y) where gcd is the greatest common divisor of a and b
with the sign of b if b is nonzero, and with the sign of a if b is 0.
The numbers x,y are such that gcd = ax+by."""
prevx, x = 1, 0; prevy, y = 0, 1
while b:
q, r = divmod(a,b)
x, prevx = prevx - q*x, x
y, prevy = prevy - q*y, y
a, b = b, r
return a, prevx, prevy
# EXPLANATION:
# Mathematical analysis reveals that at each stage in the calculation
# the current remainder can be expressed in the form ax + by for some
# integers x, y. Moreover, the x-sequence and y-sequence are
# generated by the recursion (where q is the integer quotient of the
# current division):
#
# new x = prev x - q * x; new y = prev y - q * y
#
# and where the initial values are x = 0, prev x = 1, y = 1, prev y = 0.
# Moreover, upon termination the x and y sequences have gone one step
# too far, (as has the remainder), so return the previous x, y values.
def mgcd(a,b):
"""Returns (gcd, x, y, s, t) where
gcd is the greatest common divisor of a and b, with the sign of b
if b is nonzero, and with the sign of a if b is 0;
the numbers x,y, s, t are such that
gcd = xa+yb
0 = sa+tb
and abs(xt-ys) = 1
Otherwise put: the determinant of matrix (hence m in name)
x y
s t
has magnitude 1, and multiplied by column vector
a
b
is column vector
gcd
0
"""
prevx, x = 1, 0; prevy, y = 0, 1
while b:
q, r = divmod(a, b)
x, prevx = prevx - q*x, x
y, prevy = prevy - q*y, y
a, b = b, r
return a, prevx, prevy, x, y
## Change from xgcd:
## The coefficients for next iteration of xgcd that give 0 there,
## and are excluded on purpose, are just included here as the last two
## returned values, so only the end of the last line is differentfrom
xgcd.
On Thu, Jan 13, 2011 at 4:49 AM, Andre Alexander Bell <n...@andre-bell.de>wrote:
> Hello Michel,
>
> On 13.01.2011 07:16, michel paul wrote:
> > But then, what if we want to think about it in purely mathematical
> > terms? If we agree that, for whatever reason, we cannot convert to
> > strings, how might we think about reversing digits using purely
> > functional reasoning, just % and recursion? That's how I initially
> > presented it, and then a kid suggested using divmod, and I was
> > delighted. It totally simplified the expression.
>
> You mean it simplified to something like this:
>
> n = 0
> d = 1234
> while d!=0:
> d,r = divmod(d,10)
> n = n*10 + r
>
> > I think it would be great to come up with a list of divmod math
> > problems. Anybody have some? I think developing fluency in divmod
> > sorts of reasoning would do a whole lot of good for understanding
> > ratio. Our current state of high school mathematical literacy that
> > equates a rational number with some bizarre decimal is horrible.
>
> I think that is an interesting point. Actually the Euclid Algorithm is
> another good divmod example.
> On the other hand you might as well argue that numbers in the given
> number system should have an access method to their digits like strings
> to their chars. In that case however, it would feel more natural if the
> indices are reverse. Then each index directly maps to the power of the
> base used. Example:
>
> i = 1234
> i[0] == 4
> i[1] == 3
> i[2] == 2
> i[3] == 1
>
> This would allow for
>
> a = 0
> a[3] = 1
> a == 1000
>
> Regards
>
>
> Andre
>
> _______________________________________________
> Edu-sig mailing list
> Edu-sig@python.org
> http://mail.python.org/mailman/listinfo/edu-sig
>
--
Dr. Andrew N. Harrington
Computer Science Department
Loyola University Chicago
512B Lewis Towers (office)
Snail mail to Lewis Towers 416
820 North Michigan Avenue
Chicago, Illinois 60611
http://www.cs.luc.edu/~anh
Phone: 312-915-7982
Fax: 312-915-7998
ahar...@luc.edu
_______________________________________________
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
