Line data Source code
1 : #line 2 "../src/kernel/none/gcdext.c"
2 : /* Copyright (C) 2003 The PARI group.
3 :
4 : This file is part of the PARI/GP package.
5 :
6 : PARI/GP is free software; you can redistribute it and/or modify it under the
7 : terms of the GNU General Public License as published by the Free Software
8 : Foundation; either version 2 of the License, or (at your option) any later
9 : version. It is distributed in the hope that it will be useful, but WITHOUT
10 : ANY WARRANTY WHATSOEVER.
11 :
12 : Check the License for details. You should have received a copy of it, along
13 : with the package; see the file 'COPYING'. If not, write to the Free Software
14 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
15 :
16 : /*==================================
17 : * bezout(a,b,pu,pv)
18 : *==================================
19 : * Return g = gcd(a,b) >= 0, and assign GENs u,v through pointers pu,pv
20 : * such that g = u*a + v*b.
21 : * Special cases:
22 : * a == b == 0 ==> pick u=1, v=0
23 : * a != 0 == b ==> keep v=0
24 : * a == 0 != b ==> keep u=0
25 : * |a| == |b| != 0 ==> keep u=0, set v=+-1
26 : * Assignments through pu,pv will be suppressed when the corresponding
27 : * pointer is NULL (but the computations will happen nonetheless).
28 : */
29 :
30 : static GEN
31 59011332 : bezout_lehmer(GEN a, GEN b, GEN *pu, GEN *pv)
32 : {
33 : GEN t,u,u1,v,v1,d,d1,q,r;
34 : GEN *pt;
35 : pari_sp av, av1;
36 : long s, sa, sb;
37 : ulong g;
38 : ulong xu,xu1,xv,xv1; /* Lehmer stage recurrence matrix */
39 : int lhmres; /* Lehmer stage return value */
40 :
41 59011332 : s = abscmpii(a,b);
42 59011332 : if (s < 0)
43 : {
44 37246764 : t=b; b=a; a=t;
45 37246764 : pt=pu; pu=pv; pv=pt;
46 : }
47 : /* now |a| >= |b| */
48 :
49 59011332 : sa = signe(a); sb = signe(b);
50 59011332 : if (!sb)
51 : {
52 1023504 : if (pv) *pv = gen_0;
53 1023504 : switch(sa)
54 : {
55 3 : case 0: if (pu) *pu = gen_0; return gen_0;
56 1020684 : case 1: if (pu) *pu = gen_1; return icopy(a);
57 2817 : case -1: if (pu) *pu = gen_m1; return(negi(a));
58 : }
59 : }
60 57987828 : if (s == 0) /* |a| == |b| != 0 */
61 : {
62 7001136 : if (pu) *pu = gen_0;
63 7001136 : if (sb > 0)
64 6623076 : { if (pv) *pv = gen_1; return icopy(b); }
65 : else
66 378060 : { if (pv) *pv = gen_m1; return(negi(b)); }
67 : }
68 : /* now |a| > |b| > 0 */
69 :
70 50986692 : if (lgefint(a) == 3) /* single-word affair */
71 : {
72 49032006 : g = xxgcduu(uel(a,2), uel(b,2), 0, &xu, &xu1, &xv, &xv1, &s);
73 49032006 : sa = s > 0 ? sa : -sa;
74 49032006 : sb = s > 0 ? -sb : sb;
75 49032006 : if (pu)
76 : {
77 26580369 : if (xu == 0) *pu = gen_0; /* can happen when b divides a */
78 9210702 : else if (xu == 1) *pu = sa < 0 ? gen_m1 : gen_1;
79 5217768 : else if (xu == 2) *pu = sa < 0 ? gen_m2 : gen_2;
80 : else
81 : {
82 4658430 : *pu = cgeti(3);
83 4658430 : (*pu)[1] = evalsigne(sa)|evallgefint(3);
84 4658430 : (*pu)[2] = xu;
85 : }
86 : }
87 49032006 : if (pv)
88 : {
89 44982255 : if (xv == 1) *pv = sb < 0 ? gen_m1 : gen_1;
90 18308433 : else if (xv == 2) *pv = sb < 0 ? gen_m2 : gen_2;
91 : else
92 : {
93 16688745 : *pv = cgeti(3);
94 16688745 : (*pv)[1] = evalsigne(sb)|evallgefint(3);
95 16688745 : (*pv)[2] = xv;
96 : }
97 : }
98 49032006 : if (g == 1) return gen_1;
99 17223798 : else if (g == 2) return gen_2;
100 11912865 : else return utoipos(g);
101 : }
102 :
103 : /* general case */
104 1954686 : av = avma;
105 1954686 : (void)new_chunk(lgefint(b) + (lgefint(a)<<1)); /* room for u,v,gcd */
106 : /* if a is significantly larger than b, calling lgcdii() is not the best
107 : * way to start -- reduce a mod b first
108 : */
109 1954686 : if (lgefint(a) > lgefint(b))
110 : {
111 1478550 : d = absi_shallow(b);
112 1478550 : q = dvmdii(absi_shallow(a), d, &d1);
113 1478550 : if (!signe(d1)) /* a == qb */
114 : {
115 1253673 : set_avma(av);
116 1253673 : if (pu) *pu = gen_0;
117 1253673 : if (pv) *pv = sb < 0 ? gen_m1 : gen_1;
118 1253673 : return icopy(d);
119 : }
120 : else
121 : {
122 224877 : u = gen_0;
123 224877 : u1 = v = gen_1;
124 224877 : v1 = negi(q);
125 : }
126 : /* if this results in lgefint(d) == 3, will fall past main loop */
127 : }
128 : else
129 : {
130 476136 : d = absi_shallow(a);
131 476136 : d1 = absi_shallow(b);
132 476136 : u = v1 = gen_1; u1 = v = gen_0;
133 : }
134 701013 : av1 = avma;
135 :
136 : /* main loop is almost identical to that of invmod() */
137 2202237 : while (lgefint(d) > 3 && signe(d1))
138 : {
139 1501224 : lhmres = lgcdii((ulong *)d, (ulong *)d1, &xu, &xu1, &xv, &xv1, ULONG_MAX);
140 1501224 : if (lhmres != 0) /* check progress */
141 : { /* apply matrix */
142 1131459 : if ((lhmres == 1) || (lhmres == -1))
143 : {
144 64851 : if (xv1 == 1)
145 : {
146 31446 : r = subii(d,d1); d=d1; d1=r;
147 31446 : a = subii(u,u1); u=u1; u1=a;
148 31446 : a = subii(v,v1); v=v1; v1=a;
149 : }
150 : else
151 : {
152 33405 : r = subii(d, mului(xv1,d1)); d=d1; d1=r;
153 33405 : a = subii(u, mului(xv1,u1)); u=u1; u1=a;
154 33405 : a = subii(v, mului(xv1,v1)); v=v1; v1=a;
155 : }
156 : }
157 : else
158 : {
159 1066608 : r = subii(muliu(d,xu), muliu(d1,xv));
160 1066608 : d1 = subii(muliu(d,xu1), muliu(d1,xv1)); d = r;
161 1066608 : a = subii(muliu(u,xu), muliu(u1,xv));
162 1066608 : u1 = subii(muliu(u,xu1), muliu(u1,xv1)); u = a;
163 1066608 : a = subii(muliu(v,xu), muliu(v1,xv));
164 1066608 : v1 = subii(muliu(v,xu1), muliu(v1,xv1)); v = a;
165 1066608 : if (lhmres&1) { togglesign(d); togglesign(u); togglesign(v); }
166 542589 : else { togglesign(d1); togglesign(u1); togglesign(v1); }
167 : }
168 : }
169 1501224 : if (lhmres <= 0 && signe(d1))
170 : {
171 398358 : q = dvmdii(d,d1,&r);
172 398358 : a = subii(u,mulii(q,u1));
173 398358 : u=u1; u1=a;
174 398358 : a = subii(v,mulii(q,v1));
175 398358 : v=v1; v1=a;
176 398358 : d=d1; d1=r;
177 : }
178 1501224 : if (gc_needed(av,1))
179 : {
180 0 : if(DEBUGMEM>1) pari_warn(warnmem,"bezout");
181 0 : gerepileall(av1,6, &d,&d1,&u,&u1,&v,&v1);
182 : }
183 : } /* end while */
184 :
185 : /* Postprocessing - final sprint */
186 701013 : if (signe(d1))
187 : {
188 : /* Assertions: lgefint(d)==lgefint(d1)==3, and
189 : * gcd(d,d1) is nonzero and fits into one word
190 : */
191 329445 : g = xxgcduu(uel(d,2), uel(d1,2), 0, &xu, &xu1, &xv, &xv1, &s);
192 329445 : u = subii(muliu(u,xu), muliu(u1, xv));
193 329445 : v = subii(muliu(v,xu), muliu(v1, xv));
194 329445 : if (s < 0) { sa = -sa; sb = -sb; }
195 329445 : set_avma(av);
196 329445 : if (pu) *pu = sa < 0 ? negi(u) : icopy(u);
197 329445 : if (pv) *pv = sb < 0 ? negi(v) : icopy(v);
198 329445 : if (g == 1) return gen_1;
199 259911 : else if (g == 2) return gen_2;
200 243336 : else return utoipos(g);
201 : }
202 : /* get here when the final sprint was skipped (d1 was zero already).
203 : * Now the matrix is final, and d contains the gcd.
204 : */
205 371568 : set_avma(av);
206 371568 : if (pu) *pu = sa < 0 ? negi(u) : icopy(u);
207 371568 : if (pv) *pv = sb < 0 ? negi(v) : icopy(v);
208 371568 : return icopy(d);
209 : }
210 :
211 : static GEN
212 390 : addmulmul(GEN u, GEN v, GEN x, GEN y)
213 390 : { return addii(mulii(u, x),mulii(v, y)); }
214 :
215 : static GEN
216 222 : bezout_halfgcd(GEN x, GEN y, GEN *ptu, GEN *ptv)
217 : {
218 222 : pari_sp av=avma;
219 222 : GEN u, v, R = matid2();
220 564 : while (lgefint(y)-2 >= EXTGCD_HALFGCD_LIMIT)
221 : {
222 342 : GEN M = HGCD0(x,y);
223 342 : R = ZM2_mul(R, gel(M, 1));
224 342 : x = gel(M,2); y = gel(M,3);
225 342 : if (signe(y) && expi(y)<magic_threshold(x))
226 : {
227 138 : GEN r, q = dvmdii(x, y, &r);
228 138 : x = y; y = r;
229 138 : R = mulq(R, q);
230 : }
231 342 : if (gc_needed(av, 1))
232 0 : gerepileall(av,3,&x,&y,&R);
233 : }
234 222 : y = bezout_lehmer(x,y,&u,&v);
235 222 : R = ZM_inv2(R);
236 222 : if (ptu) *ptu = addmulmul(u,v,gcoeff(R,1,1),gcoeff(R,2,1));
237 222 : if (ptv) *ptv = addmulmul(u,v,gcoeff(R,1,2),gcoeff(R,2,2));
238 222 : return y;
239 : }
240 :
241 : GEN
242 59011332 : bezout(GEN x, GEN y, GEN *ptu, GEN *ptv)
243 : {
244 59011332 : pari_sp av = avma;
245 : GEN d;
246 59011332 : if (lgefint(y)-2 >= EXTGCD_HALFGCD_LIMIT)
247 222 : d = bezout_halfgcd(x, y, ptu, ptv);
248 : else
249 59011110 : d = bezout_lehmer(x, y, ptu, ptv);
250 59011332 : if (ptv) return gc_all(av,ptu?3:2, &d, ptv, ptu);
251 29812143 : return gc_all(av, ptu?2:1, &d, ptu);
252 : }
|
