[Edu-sig] the importance of divmod

[Andrew Harrington]

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 <news at 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 at 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
aharrin at luc.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20110113/2c9f499b/attachment.html>