/
IEGCD.c,v
99 lines (84 loc) · 1.76 KB
/
IEGCD.c,v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
head 1.2;
access;
symbols;
locks
saclib:1.2; strict;
comment @ * @;
1.2
date 94.01.09.16.42.09; author George; state algo;
branches;
next 1.1;
1.1
date 94.01.09.16.41.45; author saclib; state init;
branches;
next ;
desc
@Integer extended greatest common divisor algorithm.
@
1.2
log
@Calls to IQ have been replaced by calls to IEQ.
@
text
@/*===========================================================================
IEGCD(a,b; c,u1,v1)
Integer extended greatest common divisor algorithm.
Inputs
a,b : in Z.
Outputs
c : gcd(a,b)
u1,v1 : in Z such that a * u1 + b * v1 = c.
If a /= 0 and b /= 0 then
abs(u1) <= abs(b)/(2*c),
abs(v1) <= abs(a)/(2*c).
Otherwise
u1 = sign(a),
v1 = sign(b).
===========================================================================*/
#include "saclib.h"
void IEGCD(a,b, c_,u1_,v1_)
Word a,b, *c_,*u1_,*v1_;
{
Word c,u1,v1;
Step1: /* Compute. */
IHEGCD(a,b,&c,&v1);
if (a == 0)
u1 = 0;
else
u1 = IEQ(IDIF(c,IPROD(b,v1)),a);
Return: /* Prepare for return. */
*c_ = c;
*u1_ = u1;
*v1_ = v1;
return;
}
@
1.1
log
@Initial revision
@
text
@d1 1
a1 1
/*======================================================================
d7 1
a7 1
a, b : in Z.
d10 9
a18 9
c : gcd(a,b)
u1, v1 : in Z such that a * u1 + b * v1 = c.
If a /= 0 and b /= 0 then
abs(u1) <= abs(b)/(2*c),
abs(v1) <= abs(a)/(2*c).
Otherwise
u1=sign(a),
v1 = sign(b).
======================================================================*/
d29 1
a29 1
u1 = 0;
d31 1
a31 1
u1 = IQ(IDIF(c,IPROD(b,v1)),a);
@