source: CGBLisp/src/RCS/xgcd.lisp,v@ 1

head    1.4;
access;
symbols;
locks; strict;
comment @;;; @;


1.4
date    2009.01.22.04.09.05;    author marek;   state Exp;
branches;
next    1.3;

1.3
date    2009.01.19.09.32.12;    author marek;   state Exp;
branches;
next    1.2;

1.2
date    2009.01.19.07.53.33;    author marek;   state Exp;
branches;
next    1.1;

1.1
date    2009.01.19.06.41.22;    author marek;   state Exp;
branches;
next    ;


desc
@@


1.4
log
@*** empty log message ***
@
text
@#|
        $Id$
  *--------------------------------------------------------------------------*
  |  Copyright (C) 1994, Marek Rychlik (e-mail: rychlik@@math.arizona.edu)    |
  |    Department of Mathematics, University of Arizona, Tucson, AZ 85721    |
  |                                                                          |
  | Everyone is permitted to copy, distribute and modify the code in this    |
  | directory, as long as this copyright note is preserved verbatim.         |
  *--------------------------------------------------------------------------*
|#

(defpackage "XGCD"
  (:use "COMMON-LISP")
  (:export xgcd))
(in-package "XGCD")

#+debug(proclaim '(optimize (speed 0) (debug 3)))
#-debug(proclaim '(optimize (speed 3) (debug 0)))

(defun xgcd (X Y)
  "Extended gcd; the call
      (xgcd X Y)
returns a multiple value list:
- GCD
- U,V  such that they solve the equation
     GCD=U*X+V*Y
- U1,V1 such that
     LCM=U1*X=V1*Y (up to the sign)."
  (labels ((xgcd-aux (x0 x1 u0 v0 u1 v1)
             (cond 
              ((= x1 0) (values x0 u0 v0 u1 v1))
              (t (multiple-value-bind (n x2) (floor x0 x1)
                   (let ((u2 (- u0 (* n u1)))
                         (v2 (- v0 (* n v1))))
                     (xgcd-aux x1 x2 u1 v1 u2 v2)))))))
    (xgcd-aux X Y 1 0 0 1)))


@


1.3
log
@*** empty log message ***
@
text
@d17 2
a18 2
;;(proclaim '(optimize (speed 0) (debug 3)))
(proclaim '(optimize (speed 3) (debug 0)))
@


1.2
log
@*** empty log message ***
@
text
@d2 1
a2 1
        $Id: xgcd.lisp,v 1.1 2009/01/19 06:41:22 marek Exp marek $
d17 2
a18 1
(proclaim '(optimize (speed 0) (debug 3)))
@


1.1
log
@Initial revision
@
text
@d2 1
a2 1
        $Id: xgcd.lisp,v 1.3 1997/12/07 05:51:11 marek Exp $
d17 2
@