/* -*-c-*-
*
- * $Id: mp-gcd.c,v 1.3 1999/12/10 23:18:39 mdw Exp $
+ * $Id: mp-gcd.c,v 1.4 2000/06/17 11:34:46 mdw Exp $
*
* Extended GCD calculation
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-gcd.c,v $
+ * Revision 1.4 2000/06/17 11:34:46 mdw
+ * More hacking for the signs of the outputs.
+ *
* Revision 1.3 1999/12/10 23:18:39 mdw
* Change interface for suggested destinations.
*
/* --- Sort out the signs --- *
*
* Note that %$ax + by = a(x - b) + b(y + a)$%.
+ *
+ * This is currently bodgy. It needs sorting out at some time.
*/
if (yy) {
if (y->f & MP_NEG) {
- y = mp_add(y, y, a);
- x = mp_sub(x, x, b);
+ do {
+ y = mp_add(y, y, a);
+ x = mp_sub(x, x, b);
+ } while (y->f & MP_NEG);
+ } else {
+ while (MP_CMP(y, >=, a)) {
+ y = mp_sub(y, y, a);
+ x = mp_add(x, x, b);
+ }
}
- } else if (x->f & MP_NEG)
- x = mp_add(x, x, b);
+ } else {
+ if (x->f & MP_NEG) {
+ do
+ x = mp_add(x, x, b);
+ while (x->f & MP_NEG);
+ } else {
+ while (MP_CMP(x, >=, b))
+ x = mp_sub(x, x, b);
+ }
+ }
/* --- Twiddle the signs --- */