![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to Hgfs.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / engine|
Return to Hgfs.c CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / engine |
1.8 ! noro 1: /* $OpenXM: OpenXM_contrib2/asir2000/engine/Hgfs.c,v 1.7 2001/06/25 06:10:48 noro Exp $ */
1.1 noro 2:
3: #include "ca.h"
4:
5: struct p_pair {
6: UM p0;
7: UM p1;
8: struct p_pair *next;
9: };
10:
11: void canzassf(UM,int,UM *);
12: void lnfsf(int,UM,UM,struct p_pair *,UM,UM);
13: void minipolysf(UM,UM,UM);
14: void czsfum(UM,UM *);
15: void gensqfrsfum(UM,DUM);
1.8 ! noro 16: void sfbmtop(int,BM,V,V,P *);
! 17: void pp_sfp(VL,P,P *);
! 18: void sfcsump(VL,P,P *);
! 19: void mulsfbmarray(int,BM,ML,int,int *,V,V,P *);
1.1 noro 20:
21: void fctrsf(p,dcp)
22: P p;
23: DCP *dcp;
24: {
25: int n,i,j,k;
26: DCP dc,dc0;
27: P lc;
28: P zp;
29: UM mp;
30: UM *tl;
31: struct oDUM *udc,*udc1;
32:
33: simp_ff(p,&zp); p = zp;
34: if ( !p ) {
35: *dcp = 0; return;
36: }
37: mp = W_UMALLOC(UDEG(p));
38: ptosfum(p,mp);
39: if ( (n = DEG(mp)) < 0 ) {
40: *dcp = 0; return;
41: } else if ( n == 0 ) {
42: NEWDC(dc); COEF(dc) = p; DEG(dc) = ONE;
43: NEXT(dc) = 0; *dcp = dc;
44: return;
45: }
46: lc = COEF(DC(p));
47: if ( !_isonesf(COEF(mp)[n]) ) {
48: monicsfum(mp);
49: }
50:
51: W_CALLOC(n+1,struct oDUM,udc);
52: gensqfrsfum(mp,udc);
53:
54: tl = (UM *)ALLOCA((n+1)*sizeof(UM));
55: W_CALLOC(DEG(mp)+1,struct oDUM,udc1);
56:
57: for ( i = 0,j = 0; udc[i].f; i++ )
58: if ( DEG(udc[i].f) == 1 ) {
59: udc1[j].f = udc[i].f; udc1[j].n = udc[i].n; j++;
60: } else {
61: bzero((char *)tl,(n+1)*sizeof(UM));
62: czsfum(udc[i].f,tl);
63: for ( k = 0; tl[k]; k++, j++ ) {
64: udc1[j].f = tl[k]; udc1[j].n = udc[i].n;
65: }
66: }
67: udc = udc1;
68: NEWDC(dc0); COEF(dc0) = lc; DEG(dc0) = ONE; dc = dc0;
69: for ( n = 0; udc[n].f; n++ ) {
70: NEWDC(NEXT(dc)); dc = NEXT(dc);
71: STOQ(udc[n].n,DEG(dc)); sfumtop(VR(p),udc[n].f,&COEF(dc));
72: }
73: NEXT(dc) = 0; *dcp = dc0;
74: }
75:
76: void gensqfrsfum(p,dc)
77: UM p;
78: struct oDUM *dc;
79: {
80: int n,i,j,d,mod;
81: UM t,s,g,f,f1,b;
82:
83: if ( (n = DEG(p)) == 1 ) {
84: dc[0].f = UMALLOC(DEG(p)); cpyum(p,dc[0].f); dc[0].n = 1;
85: return;
86: }
87: t = W_UMALLOC(n); s = W_UMALLOC(n); g = W_UMALLOC(n);
88: f = W_UMALLOC(n); f1 = W_UMALLOC(n); b = W_UMALLOC(n);
89: diffsfum(p,t); cpyum(p,s); gcdsfum(t,s,g);
90: if ( !DEG(g) ) {
91: dc[0].f = UMALLOC(DEG(p)); cpyum(p,dc[0].f); dc[0].n = 1;
92: return;
93: }
94: cpyum(p,b); cpyum(p,t); divsfum(t,g,f);
95: for ( i = 0, d = 0; DEG(f); i++ ) {
96: while ( 1 ) {
97: cpyum(b,t);
98: if ( divsfum(t,f,s) >= 0 )
99: break;
100: else {
101: cpyum(s,b); d++;
102: }
103: }
104: cpyum(b,t); cpyum(f,s); gcdsfum(t,s,f1);
105: divsfum(f,f1,s); cpyum(f1,f);
106: dc[i].f = UMALLOC(DEG(s)); cpyum(s,dc[i].f); dc[i].n = d;
107: }
108: mod = characteristic_sf();
109: if ( DEG(b) > 0 ) {
110: d = 1;
111: while ( 1 ) {
112: cpyum(b,t);
113: for ( j = DEG(t); j >= 0; j-- )
114: if ( COEF(t)[j] && (j % mod) )
115: break;
116: if ( j >= 0 )
117: break;
118: else {
119: DEG(s) = DEG(t)/mod;
120: for ( j = 0; j <= DEG(t); j++ )
121: COEF(s)[j] = COEF(t)[j*mod];
122: cpyum(s,b); d *= mod;
123: }
124: }
125: gensqfrsfum(b,dc+i);
126: for ( j = i; dc[j].f; j++ )
127: dc[j].n *= d;
128: }
129: }
130:
131: void randsfum(d,p)
132: int d;
133: UM p;
134: {
135: int i;
136:
1.2 noro 137: for ( i = 0; i < d; i++ )
1.1 noro 138: COEF(p)[i] = _randomsf();
1.2 noro 139: for ( i = d-1; i >= 0 && !COEF(p)[i]; i-- );
140: p->d = i;
1.1 noro 141: }
142:
143: void pwrmodsfum(p,e,f,pr)
144: int e;
145: UM p,f,pr;
146: {
147: UM wt,ws,q;
148:
149: if ( e == 0 ) {
150: DEG(pr) = 0; COEF(pr)[0] = _onesf();
151: } else if ( DEG(p) < 0 )
152: DEG(pr) = -1;
153: else if ( e == 1 ) {
154: q = W_UMALLOC(DEG(p)); cpyum(p,pr);
155: DEG(pr) = divsfum(pr,f,q);
156: } else if ( DEG(p) == 0 ) {
157: DEG(pr) = 0; COEF(pr)[0] = _pwrsf(COEF(p)[0],e);
158: } else {
159: wt = W_UMALLOC(2*DEG(f)); ws = W_UMALLOC(2*DEG(f));
160: q = W_UMALLOC(2*DEG(f));
161: pwrmodsfum(p,e/2,f,wt);
162: if ( !(e%2) ) {
163: mulsfum(wt,wt,pr); DEG(pr) = divsfum(pr,f,q);
164: } else {
165: mulsfum(wt,wt,ws);
166: DEG(ws) = divsfum(ws,f,q);
167: mulsfum(ws,p,pr);
168: DEG(pr) = divsfum(pr,f,q);
169: }
170: }
171: }
172:
1.2 noro 173: void spwrsfum(m,f,e,r)
1.1 noro 174: UM f,m,r;
175: N e;
176: {
177: UM t,s,q;
178: N e1;
179: int a;
180:
181: if ( !e ) {
182: DEG(r) = 0; COEF(r)[0] = _onesf();
183: } else if ( UNIN(e) )
184: cpyum(f,r);
185: else {
186: a = divin(e,2,&e1);
1.2 noro 187: t = W_UMALLOC(2*DEG(m)); spwrsfum(m,f,e1,t);
1.1 noro 188: s = W_UMALLOC(2*DEG(m)); q = W_UMALLOC(2*DEG(m));
189: mulsfum(t,t,s); DEG(s) = divsfum(s,m,q);
190: if ( a ) {
191: mulsfum(s,f,t); DEG(t) = divsfum(t,m,q); cpyum(t,r);
192: } else
193: cpyum(s,r);
194: }
195: }
196:
1.2 noro 197: void tracemodsfum(m,f,e,r)
198: UM f,m,r;
199: int e;
200: {
201: UM t,s,q,u;
202: int i;
203:
204: q = W_UMALLOC(2*DEG(m)+DEG(f)); /* XXX */
205: t = W_UMALLOC(2*DEG(m));
206: s = W_UMALLOC(2*DEG(m));
207: u = W_UMALLOC(2*DEG(m));
208: DEG(f) = divsfum(f,m,q);
209: cpyum(f,s);
210: cpyum(f,t);
211: for ( i = 1; i < e; i++ ) {
212: mulsfum(t,t,u);
213: DEG(u) = divsfum(u,m,q); cpyum(u,t);
214: addsfum(t,s,u); cpyum(u,s);
215: }
216: cpyum(s,r);
217: }
218:
1.1 noro 219: void make_qmatsf(p,tab,mp)
220: UM p;
221: UM *tab;
222: int ***mp;
223: {
224: int n,i,j;
225: int *c;
226: UM q,r;
227: int **mat;
228: int one;
229:
230: n = DEG(p);
231: *mp = mat = almat(n,n);
232: for ( j = 0; j < n; j++ ) {
233: r = W_UMALLOC(DEG(tab[j])); q = W_UMALLOC(DEG(tab[j]));
234: cpyum(tab[j],r); DEG(r) = divsfum(r,p,q);
235: for ( i = 0, c = COEF(r); i <= DEG(r); i++ )
236: mat[i][j] = c[i];
237: }
238: one = _onesf();
239: for ( i = 0; i < n; i++ )
240: mat[i][i] = _subsf(mat[i][i],one);
241: }
242:
243: void nullsf(mat,n,ind)
244: int **mat;
245: int *ind;
246: int n;
247: {
248: int i,j,l,s,h,inv;
249: int *t,*u;
250:
251: bzero((char *)ind,n*sizeof(int));
252: ind[0] = 0;
253: for ( i = j = 0; j < n; i++, j++ ) {
254: for ( ; j < n; j++ ) {
255: for ( l = i; l < n; l++ )
256: if ( mat[l][j] )
257: break;
258: if ( l < n ) {
259: t = mat[i]; mat[i] = mat[l]; mat[l] = t; break;
260: } else
261: ind[j] = 1;
262: }
263: if ( j == n )
264: break;
265: inv = _invsf(mat[i][j]);
266: for ( s = j, t = mat[i]; s < n; s++ )
267: t[s] = _mulsf(t[s],inv);
268: for ( l = 0; l < n; l++ ) {
269: if ( l == i )
270: continue;
271: u = mat[l]; h = _chsgnsf(u[j]);
272: for ( s = j; s < n; s++ )
273: u[s] = _addsf(_mulsf(h,t[s]),u[s]);
274: }
275: }
276: }
277:
278: void null_to_solsf(mat,ind,n,r)
279: int **mat;
280: int *ind;
281: int n;
282: UM *r;
283: {
284: int i,j,k,l;
285: int *c;
286: UM w;
287:
288: for ( i = 0, l = 0; i < n; i++ ) {
289: if ( !ind[i] )
290: continue;
291: w = UMALLOC(n);
292: for ( j = k = 0, c = COEF(w); j < n; j++ )
293: if ( ind[j] )
294: c[j] = 0;
295: else
296: c[j] = mat[k++][i];
297: c[i] = _chsgnsf(_onesf());
298: for ( j = n; j >= 0; j-- )
299: if ( c[j] )
300: break;
301: DEG(w) = j;
302: r[l++] = w;
303: }
304: }
305: /*
306: make_qmatsf(p,tab,mp)
307: nullsf(mat,n,ind)
308: null_to_solsf(ind,n,r)
309: */
310:
311: void czsfum(f,r)
312: UM f,*r;
313: {
314: int i,j;
315: int d,n,ord;
316: UM s,t,u,v,w,g,x,m,q;
317: UM *base;
318:
319: n = DEG(f); base = (UM *)ALLOCA(n*sizeof(UM));
320: bzero((char *)base,n*sizeof(UM));
321:
322: w = W_UMALLOC(2*n); q = W_UMALLOC(2*n); m = W_UMALLOC(2*n);
323:
324: base[0] = W_UMALLOC(0); DEG(base[0]) = 0; COEF(base[0])[0] = _onesf();
325:
326: t = W_UMALLOC(1); DEG(t) = 1; COEF(t)[0] = 0; COEF(t)[1] = _onesf();
327:
328: ord = field_order_sf();
329: pwrmodsfum(t,ord,f,w);
330: base[1] = W_UMALLOC(DEG(w));
331: cpyum(w,base[1]);
332:
333: for ( i = 2; i < n; i++ ) {
334: mulsfum(base[i-1],base[1],m);
335: DEG(m) = divsfum(m,f,q);
336: base[i] = W_UMALLOC(DEG(m)); cpyum(m,base[i]);
337: }
338:
339: v = W_UMALLOC(n); cpyum(f,v);
340: DEG(w) = 1; COEF(w)[0] = 0; COEF(w)[1] = _onesf();
341: x = W_UMALLOC(1); DEG(x) = 1; COEF(x)[0] = 0; COEF(x)[1] = _onesf();
342: t = W_UMALLOC(n); s = W_UMALLOC(n); u = W_UMALLOC(n); g = W_UMALLOC(n);
343:
344: for ( j = 0, d = 1; 2*d <= DEG(v); d++ ) {
345: for ( DEG(t) = -1, i = 0; i <= DEG(w); i++ )
346: if ( COEF(w)[i] ) {
347: mulssfum(base[i],COEF(w)[i],s);
348: addsfum(s,t,u); cpyum(u,t);
349: }
350: cpyum(t,w); cpyum(v,s); subsfum(w,x,t);
351: gcdsfum(s,t,g);
352: if ( DEG(g) >= 1 ) {
353: berlekampsf(g,d,base,r+j); j += DEG(g)/d;
354: divsfum(v,g,q); cpyum(q,v);
355: DEG(w) = divsfum(w,v,q);
356: for ( i = 0; i < DEG(v); i++ )
357: DEG(base[i]) = divsfum(base[i],v,q);
358: }
359: }
360: if ( DEG(v) ) {
361: r[j] = UMALLOC(DEG(v)); cpyum(v,r[j]); j++;
362: }
363: r[j] = 0;
364: }
365:
366: int berlekampsf(p,df,tab,r)
367: UM p;
368: int df;
369: UM *tab,*r;
370: {
371: int n,i,j,k,nf,d,nr;
372: int **mat;
373: int *ind;
374: UM mp,w,q,gcd,w1,w2;
375: UM *u;
376: int *root;
377:
378: n = DEG(p);
379: ind = ALLOCA(n*sizeof(int));
380: make_qmatsf(p,tab,&mat);
381: nullsf(mat,n,ind);
382: for ( i = 0, d = 0; i < n; i++ )
383: if ( ind[i] )
384: d++;
385: if ( d == 1 ) {
386: r[0] = UMALLOC(n); cpyum(p,r[0]); return 1;
387: }
388: u = ALLOCA(d*sizeof(UM *));
389: r[0] = UMALLOC(n); cpyum(p,r[0]);
390: null_to_solsf(mat,ind,n,u);
391: root = ALLOCA(d*sizeof(int));
392: w = W_UMALLOC(n); mp = W_UMALLOC(d);
393: w1 = W_UMALLOC(n); w2 = W_UMALLOC(n);
394: for ( i = 1, nf = 1; i < d; i++ ) {
395: minipolysf(u[i],p,mp);
396: nr = find_rootsf(mp,root);
397: for ( j = 0; j < nf; j++ ) {
398: if ( DEG(r[j]) == df )
399: continue;
400: for ( k = 0; k < nr; k++ ) {
401: cpyum(u[i],w1); cpyum(r[j],w2);
402: COEF(w1)[0] = _chsgnsf(root[k]);
403: gcdsfum(w1,w2,w);
404: if ( DEG(w) > 0 && DEG(w) < DEG(r[j]) ) {
405: gcd = UMALLOC(DEG(w));
406: q = UMALLOC(DEG(r[j])-DEG(w));
407: cpyum(w,gcd); divsfum(r[j],w,q);
408: r[j] = q; r[nf++] = gcd;
409: }
410: if ( nf == d )
411: return d;
412: }
413: }
414: }
415: }
416:
417: void minipolysf(f,p,mp)
418: UM f,p,mp;
419: {
420: struct p_pair *list,*l,*l1,*lprev;
421: int n,d;
422: UM u,p0,p1,np0,np1,q,w;
423:
424: list = (struct p_pair *)MALLOC(sizeof(struct p_pair));
425: list->p0 = u = W_UMALLOC(0); DEG(u) = 0; COEF(u)[0] = _onesf();
426: list->p1 = W_UMALLOC(0); cpyum(list->p0,list->p1);
427: list->next = 0;
428: n = DEG(p); w = UMALLOC(2*n);
429: p0 = UMALLOC(2*n); cpyum(list->p0,p0);
430: p1 = UMALLOC(2*n); cpyum(list->p1,p1);
431: q = W_UMALLOC(2*n);
432: while ( 1 ) {
433: COEF(p0)[DEG(p0)] = 0; DEG(p0)++; COEF(p0)[DEG(p0)] = _onesf();
434: mulsfum(f,p1,w); DEG(w) = divsfum(w,p,q); cpyum(w,p1);
435: np0 = UMALLOC(n); np1 = UMALLOC(n);
436: lnfsf(n,p0,p1,list,np0,np1);
437: if ( DEG(np1) < 0 ) {
438: cpyum(np0,mp); return;
439: } else {
440: l1 = (struct p_pair *)MALLOC(sizeof(struct p_pair));
441: l1->p0 = np0; l1->p1 = np1;
442: for ( l = list, lprev = 0, d = DEG(np1);
443: l && (DEG(l->p1) > d); lprev = l, l = l->next );
444: if ( lprev ) {
445: lprev->next = l1; l1->next = l;
446: } else {
447: l1->next = list; list = l1;
448: }
449: }
450: }
451: }
452:
453: void lnfsf(n,p0,p1,list,np0,np1)
454: int n;
455: UM p0,p1;
456: struct p_pair *list;
457: UM np0,np1;
458: {
459: int inv,h,d1;
460: UM t0,t1,s0,s1;
461: struct p_pair *l;
462:
463: cpyum(p0,np0); cpyum(p1,np1);
464: t0 = W_UMALLOC(n); t1 = W_UMALLOC(n);
465: s0 = W_UMALLOC(n); s1 = W_UMALLOC(n);
466: for ( l = list; l; l = l->next ) {
467: d1 = DEG(np1);
468: if ( d1 == DEG(l->p1) ) {
469: h = _divsf(COEF(np1)[d1],_chsgnsf(COEF(l->p1)[d1]));
470: mulssfum(l->p0,h,t0); addsfum(np0,t0,s0); cpyum(s0,np0);
471: mulssfum(l->p1,h,t1); addsfum(np1,t1,s1); cpyum(s1,np1);
472: }
473: }
474: }
475:
476: int find_rootsf(p,root)
477: UM p;
478: int *root;
479: {
480: UM *r;
481: int i,j,n;
482:
483: n = DEG(p);
484: r = ALLOCA((DEG(p))*sizeof(UM));
485: canzassf(p,1,r);
486: for ( i = 0; i < n; i++ )
487: root[i] = _chsgnsf(COEF(r[i])[0]);
488: return n;
489: }
490:
491: void canzassf(f,d,r)
492: UM f,*r;
493: int d;
494: {
495: UM t,s,u,w,g,o;
496: N n1,n2,n3,n4,n5;
497: UM *b;
1.2 noro 498: int n,m,i,q,ed;
1.1 noro 499:
500: if ( DEG(f) == d ) {
501: r[0] = UMALLOC(d); cpyum(f,r[0]);
502: return;
503: } else {
504: n = DEG(f); b = (UM *)ALLOCA(n*sizeof(UM));
505: bzero((char *)b,n*sizeof(UM));
506:
507: t = W_UMALLOC(2*d);
508: s = W_UMALLOC(DEG(f)); u = W_UMALLOC(DEG(f));
509: w = W_UMALLOC(DEG(f)); g = W_UMALLOC(DEG(f));
510: o = W_UMALLOC(0); DEG(o) = 0; COEF(o)[0] = _onesf();
511: q = field_order_sf();
1.2 noro 512: if ( q % 2 ) {
513: STON(q,n1); pwrn(n1,d,&n2); subn(n2,ONEN,&n3);
514: STON(2,n4); divsn(n3,n4,&n5);
515: } else
516: ed = d*extdeg_sf();
1.1 noro 517: while ( 1 ) {
1.2 noro 518: randsfum(2*d,t);
519: if ( q % 2 ) {
520: spwrsfum(f,t,n5,s); subsfum(s,o,u);
521: } else
522: tracemodsfum(f,t,ed,u);
523: cpyum(f,w);
524: gcdsfum(w,u,g);
1.1 noro 525: if ( (DEG(g) >= 1) && (DEG(g) < DEG(f)) ) {
526: canzassf(g,d,r);
527: cpyum(f,w); divsfum(w,g,s);
528: canzassf(s,d,r+DEG(g)/d);
529: return;
530: }
531: }
532: }
533: }
534:
1.3 noro 535: /* Hensel related functions */
536:
537: int sfberle(VL,P,int,GFS *,DCP *);
538: void sfgcdgen(P,ML,ML *);
539: void sfhenmain(LUM,ML,ML,ML *);
540: void ptosflum(int,P,LUM);
1.5 noro 541: void sfhenmain2(BM,UM,UM,int,BM *);
542: void ptosfbm(int,P,BM);
1.3 noro 543:
544: /* f = f(x,y) */
545:
1.8 ! noro 546: void sfhensel(count,f,x,evp,sfp,listp)
1.3 noro 547: int count;
548: P f;
549: V x;
1.8 ! noro 550: GFS *evp;
! 551: P *sfp;
1.3 noro 552: ML *listp;
553: {
554: int i,j;
555: int fn,n,bound;
1.4 noro 556: ML rlist;
1.5 noro 557: BM fl;
1.3 noro 558: VL vl,nvl;
559: V y;
1.4 noro 560: int dx,dy,mev;
1.3 noro 561: GFS ev;
1.8 ! noro 562: P f1,t,yev,c,sf;
1.3 noro 563: DCP dc;
1.4 noro 564: UM w,w1,q,fm,hm;
565: UM *gm;
1.3 noro 566:
567: clctv(CO,f,&vl);
568: if ( vl->v != x ) {
569: reordvar(vl,x,&nvl); reorderp(nvl,vl,f,&f1);
570: vl = nvl; f = f1;
571: }
572: y = vl->next->v;
573: dx = getdeg(x,f);
574: dy = getdeg(y,f);
575: if ( dx == 1 ) {
1.4 noro 576: *listp = rlist = MLALLOC(1); rlist->n = 1; rlist->c[0] = 0;
1.3 noro 577: return;
578: }
579: fn = sfberle(vl,f,count,&ev,&dc);
580: if ( fn <= 1 ) {
581: /* fn == 0 => short of evaluation points */
1.4 noro 582: *listp = rlist = MLALLOC(1); rlist->n = fn; rlist->c[0] = 0;
1.3 noro 583: return;
584: }
585: /* pass the the leading coeff. to the first element */
586: c = dc->c; dc = NEXT(dc);
587: mulp(vl,dc->c,c,&t); dc->c = t;
1.4 noro 588:
589: /* convert mod y-a factors into UM */
590: gm = (UM *)ALLOCA(fn*sizeof(UM));
1.3 noro 591: for ( i = 0; i < fn; i++, dc = NEXT(dc) ) {
1.4 noro 592: gm[i] = W_UMALLOC(UDEG(dc->c));
593: ptosfum(dc->c,gm[i]);
1.3 noro 594: }
1.4 noro 595:
596: bound = dy+1;
597: /* f(x,y) -> f(x,y+ev) */
1.5 noro 598: fl = BMALLOC(dx,bound);
599: ptosfbm(bound,f,fl);
600: shiftsfbm(bound,fl,FTOIF(CONT(ev)));
1.4 noro 601:
1.8 ! noro 602: /* sf = f(x+ev) */
! 603: sfbmtop(bound,fl,x,y,&sf);
! 604:
1.4 noro 605: /* fm = fl mod y */
606: fm = W_UMALLOC(dx);
1.5 noro 607: cpyum(COEF(fl)[0],fm);
1.4 noro 608: hm = W_UMALLOC(dx);
609:
610: q = W_UMALLOC(dx);
611: rlist = MLALLOC(fn); rlist->n = fn; rlist->bound = bound;
1.7 noro 612: for ( i = 0; i < fn-1; i++ ) {
1.4 noro 613: fprintf(stderr,"%d\n",i);
614: /* fl = gm[i]*hm mod y */
615: divsfum(fm,gm[i],hm);
616: /* fl is replaced by the cofactor of gk mod y^bound */
617: /* rlist->c[i] = gk */
1.5 noro 618: sfhenmain2(fl,gm[i],hm,bound,(BM *)&rlist->c[i]);
1.4 noro 619: cpyum(hm,fm);
620: }
1.7 noro 621: /* finally, fl must be the lift of gm[fn-1] */
1.4 noro 622: rlist->c[i] = fl;
623:
1.8 ! noro 624: #if 0
1.4 noro 625: /* y -> y-a */
626: mev = _chsgnsf(FTOIF(CONT(ev)));
627: for ( i = 0; i < fn; i++ )
1.5 noro 628: shiftsfbm(bound,(BM)(rlist->c[i]),mev);
1.8 ! noro 629: #endif
! 630: *evp = ev;
! 631: *sfp = sf;
1.4 noro 632: *listp = rlist;
1.3 noro 633: }
634:
635: /* main variable of f = x */
636:
637: int sfberle(vl,f,count,ev,dcp)
638: VL vl;
639: P f;
640: int count;
641: GFS *ev;
642: DCP *dcp;
643: {
644: UM wf,wf1,wf2,wfs,gcd;
645: ML flist;
646: int fn,fn1,n;
647: GFS m,fm;
648: DCP dc,dct,dc0;
649: VL nvl;
650: V x,y;
651: P g,lc,lc0,f0;
652: int j,q1,index,i;
653:
654: clctv(vl,f,&nvl); vl = nvl;
655: x = vl->v; y = vl->next->v;
656: simp_ff(f,&g); g = f;
657: n = QTOS(DEG(DC(f)));
658: wf = W_UMALLOC(n); wf1 = W_UMALLOC(n); wf2 = W_UMALLOC(n);
659: wfs = W_UMALLOC(n); gcd = W_UMALLOC(n);
660: q1 = field_order_sf()-1;
661: lc = DC(f)->c;
662: for ( j = 0, fn = n + 1, index = 0;
1.4 noro 663: index < q1 && j < count && fn > 1; index++ ) {
1.3 noro 664: MKGFS(index,m);
665: substp(vl,lc,y,(P)m,&lc0);
666: if ( lc0 ) {
667: substp(vl,f,y,(P)m,&f0);
1.4 noro 668: ptosfum(f0,wf); cpyum(wf,wf1);
669: diffsfum(wf1,wf2); gcdsfum(wf1,wf2,gcd);
1.3 noro 670: if ( DEG(gcd) == 0 ) {
671: fctrsf(f0,&dc);
672: for ( dct = NEXT(dc), i = 0; dct; dct = NEXT(dct), i++ );
673: if ( i < fn ) {
674: dc0 = dc; fn = i; fm = m;
675: }
676: j++;
677: }
678: }
679: }
680: if ( index == q1 )
681: return 0;
682: else if ( fn == 1 )
683: return 1;
684: else {
685: *dcp = dc0;
686: *ev = fm;
687: return fn;
688: }
689: }
690:
691: void sfgcdgen(f,blist,clistp)
692: P f;
693: ML blist,*clistp;
694: {
695: int i;
696: int n,d,np;
697: UM wf,wm,wx,wy,wu,wv,wa,wb,wg,q,tum;
698: UM *in,*out;
699: ML clist;
700:
701: n = UDEG(f); np = blist->n;
702: d = 2*n;
703: q = W_UMALLOC(d); wf = W_UMALLOC(d);
704: wm = W_UMALLOC(d); wx = W_UMALLOC(d);
705: wy = W_UMALLOC(d); wu = W_UMALLOC(d);
706: wv = W_UMALLOC(d); wg = W_UMALLOC(d);
707: wa = W_UMALLOC(d); wb = W_UMALLOC(d);
708: ptosfum(f,wf); DEG(wg) = 0; COEF(wg)[0] = _onesf();
709: *clistp = clist = MLALLOC(np); clist->n = np;
710: for ( i = 0, in = (UM *)blist->c, out = (UM *)clist->c; i < np; i++ ) {
711: divsfum(wf,in[i],q); tum = wf; wf = q; q = tum;
712: cpyum(wf,wx); cpyum(in[i],wy);
713: eucsfum(wx,wy,wa,wb); mulsfum(wa,wg,wm);
714: DEG(wm) = divsfum(wm,in[i],q); out[i] = UMALLOC(DEG(wm));
715: cpyum(wm,out[i]); mulsfum(q,wf,wu);
716: mulsfum(wg,wb,wv); addsfum(wu,wv,wg);
717: }
718: }
719:
720: /*
721: sfhenmain(fl,bqlist,cqlist,listp)
722: */
723:
724: void sfhenmain(f,bqlist,cqlist,listp)
725: LUM f;
726: ML bqlist,cqlist,*listp;
727: {
728: int i,j,k;
729: int *px,*py;
730: int **pp,**pp1;
731: int n,np,bound,dr,tmp;
732: UM wt,wq0,wq,wr,wm,wm0,wa,q;
733: LUM wb0,wb1,tlum;
734: UM *b,*c;
735: LUM *l;
736: ML list;
737:
738: n = DEG(f); np = bqlist->n; bound = bqlist->bound;
739: *listp = list = MLALLOC(n);
740: list->n = np; list->bound = bound;
741: W_LUMALLOC(n,bound,wb0); W_LUMALLOC(n,bound,wb1);
742: wt = W_UMALLOC(n); wq0 = W_UMALLOC(n); wq = W_UMALLOC(n);
743: wr = W_UMALLOC(n); wm = W_UMALLOC(2*n); wm0 = W_UMALLOC(2*n);
744: wa = W_UMALLOC(2*n); q = W_UMALLOC(2*n);
745: b = (UM *)bqlist->c; c = (UM *)cqlist->c; l = (LUM *)list->c;
746: for ( i = 0; i < np; i++ ) {
747: l[i] = LUMALLOC(DEG(b[i]),bound);
748: for ( j = DEG(b[i]), pp = COEF(l[i]), px = COEF(b[i]); j >= 0; j-- )
749: pp[j][0] = px[j];
750: }
751: for ( i = 1; i < bound; i++ ) {
1.4 noro 752: fprintf(stderr,".");
753: /* at this point, f = l[0]*l[1]*...*l[np-1] mod y^i */
1.3 noro 754: mulsflum(i+1,l[0],l[1],wb0);
755: for ( j = 2; j < np; j++ ) {
756: mulsflum(i+1,l[j],wb0,wb1);
757: tlum = wb0; wb0 = wb1; wb1 = tlum;
758: }
1.5 noro 759: #if 0
1.4 noro 760: /* check */
761: for ( j = 0, pp = COEF(f), pp1 = COEF(wb0); j <= n; j++ )
762: for ( k = 0; k < i; k++ )
763: if ( pp[j][k] != pp1[j][k] )
764: error("henmain : cannot happen");
765: #endif
1.3 noro 766: for ( j = n, px = COEF(wt); j >= 0; j-- )
767: px[j] = 0;
768: for ( j = n, pp = COEF(f), pp1 = COEF(wb0); j >= 0; j-- )
769: COEF(wt)[j] = _subsf(pp[j][i],pp1[j][i]);
770: degum(wt,n);
771: for ( j = n, px = COEF(wq0); j >= 0; j-- )
772: px[j] = 0;
773: for ( j = 1; j < np; j++ ) {
774: mulsfum(wt,c[j],wm); dr = divsfum(wm,b[j],q);
775: for ( k = DEG(q), px = COEF(wq0), py = COEF(q); k >= 0; k-- )
776: px[k] = _addsf(px[k],py[k]);
777: for ( k = dr, pp = COEF(l[j]), px = COEF(wm); k >= 0; k-- )
778: pp[k][i] = px[k];
779: }
780: degum(wq0,n); mulsfum(wq0,b[0],wm);
781: mulsfum(wt,c[0],wm0); addsfum(wm,wm0,wa);
782: for ( j = DEG(wa), pp = COEF(l[0]), px = COEF(wa); j >= 0; j-- )
783: pp[j][i] = px[j];
784: for ( j = n, px = COEF(wq0); j >= 0; j-- )
785: px[j] = 0;
786: }
1.4 noro 787: fprintf(stderr,"\n");
788: }
789:
790: /* f = g0*h0 mod y -> f = gk*hk mod y^bound, f is replaced by hk */
791:
792: void sfhenmain2(f,g0,h0,bound,gp)
1.5 noro 793: BM f;
1.4 noro 794: UM g0,h0;
795: int bound;
1.5 noro 796: BM *gp;
1.4 noro 797: {
798: int i,j,k,l;
799: int *px,*py;
800: int **pp,**pp1;
801: int n,np,dr,tmp;
1.5 noro 802: UM wt,wa,wb,wq,wm,q,w1,w2,wh1,wg1,ws;
1.4 noro 803: UM wc,wd,we,wz;
1.5 noro 804: BM wb0,wb1;
1.4 noro 805: int ng,nh;
1.5 noro 806: BM fk,gk,hk;
1.4 noro 807:
1.8 ! noro 808: n = degsfbm(bound,f);
1.4 noro 809: ng = g0->d;
810: nh = h0->d;
811:
1.5 noro 812: W_BMALLOC(n,bound,wb0); W_BMALLOC(n,bound,wb1);
813: wt = W_UMALLOC(n); ws = W_UMALLOC(n);
814: wq = W_UMALLOC(n); q = W_UMALLOC(2*n);
1.4 noro 815: wg1 = W_UMALLOC(2*n); wh1 = W_UMALLOC(2*n);
1.5 noro 816:
1.4 noro 817: /* fk = gk*hk mod y^k */
1.8 ! noro 818: W_BMALLOC(n,bound,fk);
! 819: cpyum(COEF(f)[0],COEF(fk)[0]);
! 820: gk = BMALLOC(ng,bound);
! 821: cpyum(g0,COEF(gk)[0]);
1.5 noro 822: W_BMALLOC(nh,bound,hk);
823: cpyum(h0,COEF(hk)[0]);
1.4 noro 824:
1.5 noro 825: wc = W_UMALLOC(2*n); wd = W_UMALLOC(2*n);
826: we = W_UMALLOC(2*n); wz = W_UMALLOC(2*n);
1.4 noro 827:
828: /* compute wa,wb s.t. wa*g0+wb*h0 = 1 mod y */
829: w1 = W_UMALLOC(ng); cpyum(g0,w1);
830: w2 = W_UMALLOC(nh); cpyum(h0,w2);
831: wa = W_UMALLOC(2*n); wb = W_UMALLOC(2*n); /* XXX */
832: eucsfum(w1,w2,wa,wb);
833:
834: #if 0
835: mulsfum(wa,g0,wc); mulsfum(wb,h0,wd); addsfum(wc,wd,we);
836: if ( DEG(we) != 0 || COEF(we)[0] != _onesf() )
1.5 noro 837: error("henmain2 : cannot happen(euc)");
1.4 noro 838: #endif
839:
840: fprintf(stderr,"bound=%d\n",bound);
841: for ( k = 1; k < bound; k++ ) {
842: fprintf(stderr,".");
843:
844: /* at this point, f = gk*hk mod y^k */
845: #if 0
1.5 noro 846: for ( j = 0; j < k; j++ )
847: if ( !isequalum(COEF(f)[j],COEF(fk)[j]) )
848: error("henmain2 : cannot happen(history)");
1.4 noro 849: #endif
850:
851: /* clear wt */
852: bzero(COEF(wt),(n+1)*sizeof(int));
853:
854: /* wt = (f-gk*hk)/y^k */
1.5 noro 855: subsfum(COEF(f)[k],COEF(fk)[k],wt);
1.4 noro 856:
857: /* clear wq */
858: bzero(COEF(wq),(n+1)*sizeof(int));
859:
860: /* compute wf1,wg1 s.t. wh1*g0+wg1*h0 = wt */
861: mulsfum(wa,wt,wh1); DEG(wh1) = divsfum(wh1,h0,q);
862: mulsfum(wh1,g0,wc); subsfum(wt,wc,wd); DEG(wd) = divsfum(wd,h0,wg1);
863:
864: /* check */
865: #if 0
866: if ( DEG(wd) >= 0 || DEG(wg1) > ng )
1.5 noro 867: error("henmain2 : cannot happen(adj)");
1.4 noro 868:
869: mulsfum(wg1,h0,wc); mulsfum(wh1,g0,wd); addsfum(wc,wd,we);
870: subsfum(we,wt,wz);
871: if ( DEG(wz) >= 0 )
872: error("henmain2 : cannot happen");
873: #endif
874:
875: /* fk += ((wg1*hk+wh1*gk)*y^k+wg1*wh1*y^(2*k) mod y^bound */
876: /* wb0 = wh1*y^k */
1.5 noro 877: clearsfbm(bound,n,wb0);
878: DEG(wb0) = bound;
879: cpyum(wh1,COEF(wb0)[k]);
880:
1.4 noro 881: /* wb1 = gk*wb0 mod y^bound */
1.5 noro 882: clearsfbm(bound,n,wb1);
883: mulsfbm(bound,gk,wb0,wb1);
1.4 noro 884: /* fk += wb1 */
1.5 noro 885: addtosfbm(bound,wb1,fk);
1.4 noro 886:
887: /* wb0 = wg1*y^k */
1.5 noro 888: clearsfbm(bound,n,wb0);
889: DEG(wb0) = bound;
890: cpyum(wg1,COEF(wb0)[k]);
891:
1.4 noro 892: /* wb1 = hk*wb0 mod y^bound */
1.5 noro 893: clearsfbm(bound,n,wb1);
894: mulsfbm(bound,hk,wb0,wb1);
1.4 noro 895: /* fk += wb1 */
1.5 noro 896: addtosfbm(bound,wb1,fk);
1.4 noro 897:
898: /* fk += wg1*wh1*y^(2*k) mod y^bound */
899: if ( 2*k < bound ) {
1.5 noro 900: mulsfum(wg1,wh1,wt); addsfum(COEF(fk)[2*k],wt,ws);
901: cpyum(ws,COEF(fk)[2*k]);
1.4 noro 902: }
903:
904: /* gk += wg1*y^k, hk += wh1*y^k */
1.5 noro 905: cpyum(wg1,COEF(gk)[k]);
906: cpyum(wh1,COEF(hk)[k]);
1.4 noro 907: }
908: fprintf(stderr,"\n");
909: *gp = gk;
1.5 noro 910: DEG(f) = bound;
911: for ( i = 0; i < bound; i++ )
912: cpyum(COEF(hk)[i],COEF(f)[i]);
1.3 noro 913: }
914:
915: void ptosflum(bound,f,fl)
916: int bound;
917: P f;
918: LUM fl;
919: {
920: DCP dc;
921: int **pp;
922: int d;
923: UM t;
924:
925: t = UMALLOC(bound);
926: for ( dc = DC(f), pp = COEF(fl); dc; dc = NEXT(dc) ) {
927: d = QTOS(DEG(dc));
928: ptosfum(COEF(dc),t);
929: bcopy(t->c,pp[d],(t->d+1)*sizeof(int));
930: }
1.4 noro 931: }
932:
1.5 noro 933: /* fl->c[i] = coef_y(f,i) */
934:
935: void ptosfbm(bound,f,fl)
936: int bound;
937: P f;
938: BM fl;
939: {
940: DCP dc;
941: int d,i,n;
942: UM t;
943:
944: DEG(fl) = bound;
945: t = UMALLOC(bound);
946: for ( dc = DC(f); dc; dc = NEXT(dc) ) {
947: d = QTOS(DEG(dc));
948: ptosfum(COEF(dc),t);
949: for ( i = 0; i <= DEG(t); i++ )
950: COEF(COEF(fl)[i])[d] = COEF(t)[i];
951: }
1.8 ! noro 952: n = QTOS(DEG(DC(f)));
! 953: for ( i = 0; i < bound; i++ )
1.5 noro 954: degum(COEF(fl)[i],n);
955: }
956:
1.4 noro 957: /* x : main variable */
958:
959: void sflumtop(bound,fl,x,y,fp)
960: int bound;
961: LUM fl;
962: V x,y;
963: P *fp;
964: {
965: int i,j,n;
966: int **c;
967: UM w;
968: int *coef;
969: DCP dc,dct;
970:
971: n = fl->d;
972: c = fl->c;
973: w = W_UMALLOC(bound);
974: for ( i = 0, dc = 0; i <= n; i++ ) {
975: coef = c[i];
976: for ( j = bound-1; j >= 0 && coef[j] == 0; j-- );
977: if ( j < 0 )
978: continue;
979: DEG(w) = j; bcopy(coef,COEF(w),(j+1)*sizeof(int));
980: NEWDC(dct); STOQ(i,DEG(dct));
981: sfumtop(y,w,&COEF(dct)); NEXT(dct) = dc; dc = dct;
982: }
983: MKP(x,dc,*fp);
1.5 noro 984: }
985:
986: /* x : main variable */
987:
1.8 ! noro 988: void sfbmtop(bound,f,x,y,fp)
1.5 noro 989: int bound;
990: BM f;
991: V x,y;
992: P *fp;
993: {
994: UM *c;
1.8 ! noro 995: int i,j,d,a;
! 996: GFS b;
! 997: DCP dc0,dc,dct;
! 998:
! 999: c = COEF(f);
! 1000: d = DEG(c[0]);
! 1001: for ( i = 1; i < bound; i++ )
! 1002: d = MAX(DEG(c[i]),d);
! 1003:
! 1004: dc0 = 0;
! 1005: for ( i = 0; i <= d; i++ ) {
! 1006: dc = 0;
! 1007: for ( j = 0; j < bound; j++ ) {
! 1008: if ( DEG(c[j]) >= i && (a = COEF(c[j])[i]) ) {
! 1009: NEWDC(dct);
! 1010: STOQ(j,DEG(dct));
! 1011: MKGFS(IFTOF(a),b);
! 1012: COEF(dct) = (P)b;
! 1013: NEXT(dct) = dc;
! 1014: dc = dct;
! 1015: }
! 1016: }
! 1017: if ( dc ) {
! 1018: NEWDC(dct);
! 1019: STOQ(i,DEG(dct));
! 1020: MKP(y,dc,COEF(dct));
! 1021: NEXT(dct) = dc0;
! 1022: dc0 = dct;
! 1023: }
! 1024: }
! 1025: if ( dc0 )
! 1026: MKP(x,dc0,*fp);
! 1027: else
! 1028: *fp = 0;
! 1029: }
! 1030:
! 1031: void sfdtest(P,ML,V,V,DCP *);
! 1032:
! 1033: void sfbfctr(f,x,y,evp,dcp)
! 1034: P f;
! 1035: V x,y;
! 1036: GFS *evp;
! 1037: DCP *dcp;
! 1038: {
! 1039: ML list;
! 1040: P sf;
! 1041:
! 1042: /* sf(x) = f(x+ev) = list->c[0]*list->c[1]*... */
! 1043: sfhensel(5,f,x,evp,&sf,&list);
! 1044: sfdtest(sf,list,x,y,dcp);
! 1045: }
! 1046:
! 1047: /* f = f(x,y) = list->c[0]*list->c[1]*... mod y^list->bound */
! 1048:
! 1049: void sfdtest(f,list,x,y,dcp)
! 1050: P f;
! 1051: ML list;
! 1052: V x,y;
! 1053: DCP *dcp;
! 1054: {
! 1055: int n,np,bound;
! 1056: int i,j,k;
! 1057: int *win;
! 1058: P g,lcg,factor,cofactor,lcyx;
! 1059: P csum,csumt;
! 1060: DCP dcf,dcf0,dc;
! 1061: BM *c;
! 1062: BM lcy;
! 1063: ML wlist;
! 1064: struct oVL vl1,vl0;
! 1065: VL vl;
! 1066: int z;
! 1067:
! 1068: /* vl = [x,y] */
! 1069: vl0.v = x; vl0.next = &vl1; vl1.v = y; vl1.next = 0; vl = &vl0;
! 1070:
! 1071: n = UDEG(f); np = list->n; bound = list->bound; win = W_ALLOC(np+1);
! 1072:
! 1073: /* csum = lc(f)*f(1) */
! 1074: sfcsump(vl,f,&csum); mulp(vl,csum,COEF(DC(f)),&csumt); csum = csumt;
! 1075:
! 1076: wlist = W_MLALLOC(np); wlist->n = list->n;
! 1077: wlist->bound = list->bound;
! 1078: c = (BM *)COEF(wlist);
! 1079: bcopy((char *)COEF(list),(char *)c,(int)(sizeof(BM)*np));
! 1080:
! 1081: /* initialize g by f */
! 1082: g = f; mulp(vl,g,COEF(DC(g)),&lcg);
! 1083:
! 1084: /* initialize lcy by LC(f) */
! 1085: W_BMALLOC(0,bound,lcy);
! 1086: NEWDC(dc); COEF(dc) = COEF(DC(g));
! 1087: DEG(dc) = 0;
! 1088: NEWP(lcyx); VR(lcyx) = x; DC(lcyx) = dc;
! 1089: ptosfbm(bound,lcyx,lcy);
! 1090:
! 1091: fprintf(stderr,"np = %d\n",np);
! 1092: for ( g = f, k = 1, dcf = dcf0 = 0, win[0] = 1, --np, z = 0; ; z++ ) {
! 1093: if ( !(z % 1000) ) fprintf(stderr,".");
! 1094: if ( sfdtestmain(vl,lcg,lcy,csum,wlist,k,win,&factor,&cofactor) ) {
! 1095: NEXTDC(dcf0,dcf); DEG(dcf) = ONE; COEF(dcf) = factor;
! 1096: g = cofactor;
! 1097:
! 1098: /* update csum */
! 1099: sfcsump(vl,g,&csum); mulp(vl,csum,COEF(DC(g)),&csumt); csum = csumt;
! 1100:
! 1101: /* update lcg */
! 1102: mulp(vl,g,COEF(DC(g)),&lcg);
! 1103:
! 1104: /* update lcy */
! 1105: clearsfbm(bound,0,lcy);
! 1106: COEF(dc) = COEF(DC(g)); ptosfbm(bound,lcyx,lcy);
! 1107:
! 1108: for ( i = 0; i < k - 1; i++ )
! 1109: for ( j = win[i] + 1; j < win[i + 1]; j++ )
! 1110: c[j-i-1] = c[j];
! 1111: for ( j = win[k-1] + 1; j <= np; j++ )
! 1112: c[j-k] = c[j];
! 1113: if ( ( np -= k ) < k )
! 1114: break;
! 1115: if ( np - win[0] + 1 < k )
! 1116: if ( ++k > np )
! 1117: break;
! 1118: else
! 1119: for ( i = 0; i < k; i++ )
! 1120: win[i] = i + 1;
! 1121: else
! 1122: for ( i = 1; i < k; i++ )
! 1123: win[i] = win[0] + i;
! 1124: } else if ( !ncombi(1,np,k,win) )
! 1125: if ( k == np )
! 1126: break;
! 1127: else
! 1128: for ( i = 0, ++k; i < k; i++ )
! 1129: win[i] = i + 1;
! 1130: }
! 1131: fprintf(stderr,"\n");
! 1132: NEXTDC(dcf0,dcf); COEF(dcf) = g;
! 1133: DEG(dcf) = ONE; NEXT(dcf) = 0; *dcp = dcf0;
! 1134: }
! 1135:
! 1136: /* lcy = LC(g), lcg = lcy*g */
! 1137: int sfdtestmain(vl,lcg,lcy,csum,list,k,in,fp,cofp)
! 1138: VL vl;
! 1139: P lcg;
! 1140: BM lcy;
! 1141: P csum;
! 1142: ML list;
! 1143: int k;
! 1144: int *in;
! 1145: P *fp,*cofp;
! 1146: {
! 1147: P fmul,csumg,q;
! 1148: V x,y;
! 1149:
! 1150: x = vl->v;
! 1151: y = vl->next->v;
! 1152: #if 0
! 1153: if (!sfctest(g,list,k,in))
! 1154: return 0;
! 1155: #endif
! 1156: mulsfbmarray(UDEG(lcg),lcy,list,k,in,x,y,&fmul);
! 1157: if ( csum ) {
! 1158: sfcsump(vl,fmul,&csumg);
! 1159: if ( csumg ) {
! 1160: if ( !divtp(vl,csum,csumg,&q) )
! 1161: return 0;
! 1162: }
! 1163: }
! 1164: if ( divtp(vl,lcg,fmul,&q) ) {
! 1165: pp_sfp(vl,fmul,fp);
! 1166: pp_sfp(vl,q,cofp);
! 1167: return 1;
! 1168: } else
! 1169: return 0;
! 1170: }
! 1171:
! 1172: #if 0
! 1173: int sfctest(g,list,k,in)
! 1174: P g;
! 1175: ML list;
! 1176: int k;
! 1177: int *in;
! 1178: {
! 1179: register int i;
! 1180: int q,bound;
! 1181: int *wm,*wm1,*tmpp;
! 1182: DCP dc;
! 1183: Q dvr;
! 1184: N lcn,cstn,dndn,dmyn,rn;
! 1185: LUM *l;
! 1186:
! 1187: for ( dc = DC(g); dc && DEG(dc); dc = NEXT(dc) );
! 1188: if ( dc )
! 1189: cstn = NM((Q)COEF(dc));
! 1190: else
! 1191: return 1;
! 1192: q = list->mod; bound = list->bound;
! 1193: ntobn(q,NM((Q)COEF(DC(g))),&lcn);;
! 1194: W_CALLOC(bound+1,int,wm); W_CALLOC(bound+1,int,wm1);
! 1195: for ( i = 0; i < PL(lcn); i++ )
! 1196: wm[i] = BD(lcn)[i];
! 1197: for ( i = 0, l = (LUM *)list->c; i < k; i++ ) {
! 1198: mulpadic(q,bound,wm,COEF(l[in[i]])[0],wm1);
! 1199: tmpp = wm; wm = wm1; wm1 = tmpp;
! 1200: }
! 1201: padictoq(q,bound,wm,&dvr);
! 1202: kmuln(NM((Q)COEF(DC(g))),cstn,&dndn); divn(dndn,NM(dvr),&dmyn,&rn);
! 1203: return rn ? 0 : 1;
! 1204: }
! 1205: #endif
! 1206:
! 1207: /* main var of f is x */
! 1208:
! 1209: void mulsfbmarray(n,lcy,list,k,in,x,y,g)
! 1210: int n;
! 1211: BM lcy;
! 1212: ML list;
! 1213: int k;
! 1214: int *in;
! 1215: V x,y;
! 1216: P *g;
! 1217: {
! 1218: int bound,i;
! 1219: BM wb0,wb1,t,lcbm;
! 1220: BM *l;
! 1221:
! 1222: bound = list->bound;
! 1223: W_BMALLOC(n,bound,wb0); W_BMALLOC(n,bound,wb1);
! 1224: l = (BM *)list->c;
! 1225: clearsfbm(bound,n,wb0);
! 1226: mulsfbm(bound,lcy,l[in[0]],wb0);
! 1227: for ( i = 1; i < k; i++ ) {
! 1228: clearsfbm(bound,n,wb1);
! 1229: mulsfbm(bound,l[in[i]],wb0,wb1);
! 1230: t = wb0; wb0 = wb1; wb1 = t;
! 1231: }
! 1232: sfbmtop(bound,wb0,x,y,g);
! 1233: }
! 1234:
! 1235: void sfcsump(vl,f,s)
! 1236: VL vl;
! 1237: P f;
! 1238: P *s;
! 1239: {
! 1240: P t,u;
! 1241: DCP dc;
! 1242:
! 1243: for ( dc = DC(f), t = 0; dc; dc = NEXT(dc) ) {
! 1244: addp(vl,COEF(dc),t,&u); t = u;
! 1245: }
! 1246: *s = t;
! 1247: }
! 1248:
! 1249: /* *fp = primitive part of f w.r.t. x */
! 1250:
! 1251: void pp_sfp(vl,f,fp)
! 1252: VL vl;
! 1253: P f;
! 1254: P *fp;
! 1255: {
! 1256: V x,y;
! 1257: int d;
! 1258: UM t,s,gcd;
! 1259: DCP dc;
! 1260: P dvr;
1.5 noro 1261:
1.8 ! noro 1262: x = vl->v;
! 1263: y = vl->next->v;
! 1264: d = getdeg(y,f);
! 1265: if ( d == 0 )
! 1266: *fp = f; /* XXX */
! 1267: else {
! 1268: t = W_UMALLOC(2*d);
! 1269: s = W_UMALLOC(2*d);
! 1270: gcd = W_UMALLOC(2*d);
! 1271: dc = DC(f);
! 1272: ptosfum(COEF(dc),gcd);
! 1273: for ( dc = NEXT(dc); dc; dc = NEXT(dc) ) {
! 1274: ptosfum(COEF(dc),t);
! 1275: gcdsfum(gcd,t,s);
! 1276: cpyum(s,gcd);
! 1277: }
! 1278: sfumtop(y,gcd,&dvr);
! 1279: divsp(vl,f,dvr,fp);
1.5 noro 1280: }
1.3 noro 1281: }