[1] | 1 | head 1.4;
|
---|
| 2 | access;
|
---|
| 3 | symbols;
|
---|
| 4 | locks; strict;
|
---|
| 5 | comment @;;; @;
|
---|
| 6 |
|
---|
| 7 |
|
---|
| 8 | 1.4
|
---|
| 9 | date 2009.01.22.04.09.05; author marek; state Exp;
|
---|
| 10 | branches;
|
---|
| 11 | next 1.3;
|
---|
| 12 |
|
---|
| 13 | 1.3
|
---|
| 14 | date 2009.01.19.09.32.12; author marek; state Exp;
|
---|
| 15 | branches;
|
---|
| 16 | next 1.2;
|
---|
| 17 |
|
---|
| 18 | 1.2
|
---|
| 19 | date 2009.01.19.07.53.33; author marek; state Exp;
|
---|
| 20 | branches;
|
---|
| 21 | next 1.1;
|
---|
| 22 |
|
---|
| 23 | 1.1
|
---|
| 24 | date 2009.01.19.06.41.22; author marek; state Exp;
|
---|
| 25 | branches;
|
---|
| 26 | next ;
|
---|
| 27 |
|
---|
| 28 |
|
---|
| 29 | desc
|
---|
| 30 | @@
|
---|
| 31 |
|
---|
| 32 |
|
---|
| 33 | 1.4
|
---|
| 34 | log
|
---|
| 35 | @*** empty log message ***
|
---|
| 36 | @
|
---|
| 37 | text
|
---|
| 38 | @#|
|
---|
| 39 | $Id$
|
---|
| 40 | *--------------------------------------------------------------------------*
|
---|
| 41 | | Copyright (C) 1994, Marek Rychlik (e-mail: rychlik@@math.arizona.edu) |
|
---|
| 42 | | Department of Mathematics, University of Arizona, Tucson, AZ 85721 |
|
---|
| 43 | | |
|
---|
| 44 | | Everyone is permitted to copy, distribute and modify the code in this |
|
---|
| 45 | | directory, as long as this copyright note is preserved verbatim. |
|
---|
| 46 | *--------------------------------------------------------------------------*
|
---|
| 47 | |#
|
---|
| 48 |
|
---|
| 49 | (defpackage "XGCD"
|
---|
| 50 | (:use "COMMON-LISP")
|
---|
| 51 | (:export xgcd))
|
---|
| 52 | (in-package "XGCD")
|
---|
| 53 |
|
---|
| 54 | #+debug(proclaim '(optimize (speed 0) (debug 3)))
|
---|
| 55 | #-debug(proclaim '(optimize (speed 3) (debug 0)))
|
---|
| 56 |
|
---|
| 57 | (defun xgcd (X Y)
|
---|
| 58 | "Extended gcd; the call
|
---|
| 59 | (xgcd X Y)
|
---|
| 60 | returns a multiple value list:
|
---|
| 61 | - GCD
|
---|
| 62 | - U,V such that they solve the equation
|
---|
| 63 | GCD=U*X+V*Y
|
---|
| 64 | - U1,V1 such that
|
---|
| 65 | LCM=U1*X=V1*Y (up to the sign)."
|
---|
| 66 | (labels ((xgcd-aux (x0 x1 u0 v0 u1 v1)
|
---|
| 67 | (cond
|
---|
| 68 | ((= x1 0) (values x0 u0 v0 u1 v1))
|
---|
| 69 | (t (multiple-value-bind (n x2) (floor x0 x1)
|
---|
| 70 | (let ((u2 (- u0 (* n u1)))
|
---|
| 71 | (v2 (- v0 (* n v1))))
|
---|
| 72 | (xgcd-aux x1 x2 u1 v1 u2 v2)))))))
|
---|
| 73 | (xgcd-aux X Y 1 0 0 1)))
|
---|
| 74 |
|
---|
| 75 |
|
---|
| 76 | @
|
---|
| 77 |
|
---|
| 78 |
|
---|
| 79 | 1.3
|
---|
| 80 | log
|
---|
| 81 | @*** empty log message ***
|
---|
| 82 | @
|
---|
| 83 | text
|
---|
| 84 | @d17 2
|
---|
| 85 | a18 2
|
---|
| 86 | ;;(proclaim '(optimize (speed 0) (debug 3)))
|
---|
| 87 | (proclaim '(optimize (speed 3) (debug 0)))
|
---|
| 88 | @
|
---|
| 89 |
|
---|
| 90 |
|
---|
| 91 | 1.2
|
---|
| 92 | log
|
---|
| 93 | @*** empty log message ***
|
---|
| 94 | @
|
---|
| 95 | text
|
---|
| 96 | @d2 1
|
---|
| 97 | a2 1
|
---|
| 98 | $Id: xgcd.lisp,v 1.1 2009/01/19 06:41:22 marek Exp marek $
|
---|
| 99 | d17 2
|
---|
| 100 | a18 1
|
---|
| 101 | (proclaim '(optimize (speed 0) (debug 3)))
|
---|
| 102 | @
|
---|
| 103 |
|
---|
| 104 |
|
---|
| 105 | 1.1
|
---|
| 106 | log
|
---|
| 107 | @Initial revision
|
---|
| 108 | @
|
---|
| 109 | text
|
---|
| 110 | @d2 1
|
---|
| 111 | a2 1
|
---|
| 112 | $Id: xgcd.lisp,v 1.3 1997/12/07 05:51:11 marek Exp $
|
---|
| 113 | d17 2
|
---|
| 114 | @
|
---|