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