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