Function: calcFunc-egcd

calcFunc-egcd is an autoloaded and byte-compiled function defined in calc-comb.el.gz.

Signature

(calcFunc-egcd A B)

Source Code

;; Defined in /usr/src/emacs/lisp/calc/calc-comb.el.gz
(defun calcFunc-egcd (a b)   ; Knuth section 4.5.2
  (cond
   ((not (Math-integerp a))
    (if (Math-messy-integerp a)
	(calcFunc-egcd (math-trunc a) b)
      (calc-record-why 'integerp a)
      (list 'calcFunc-egcd a b)))
   ((not (Math-integerp b))
    (if (Math-messy-integerp b)
	(calcFunc-egcd a (math-trunc b))
      (calc-record-why 'integerp b)
      (list 'calcFunc-egcd a b)))
   (t
    (let ((u1 1) (u2 0) (u3 a)
	  (v1 0) (v2 1) (v3 b)
	  t1 t2 q)
      (while (not (eq v3 0))
	(setq q (math-idivmod u3 v3)
	      t1 (math-sub u1 (math-mul v1 (car q)))
	      t2 (math-sub u2 (math-mul v2 (car q)))
	      u1 v1  u2 v2  u3 v3
	      v1 t1  v2 t2  v3 (cdr q)))
      (list 'vec u3 u1 u2)))))