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