1// Origin: abbott@dima.unige.it 2// PR c/5120 3 4extern void * malloc (__SIZE_TYPE__); 5extern void * calloc (__SIZE_TYPE__, __SIZE_TYPE__); 6 7typedef unsigned int FFelem; 8 9FFelem FFmul(const FFelem x, const FFelem y) 10{ 11 return x; 12} 13 14 15struct DUPFFstruct 16{ 17 int maxdeg; 18 int deg; 19 FFelem *coeffs; 20}; 21 22typedef struct DUPFFstruct *DUPFF; 23 24 25int DUPFFdeg(const DUPFF f) 26{ 27 return f->deg; 28} 29 30 31DUPFF DUPFFnew(const int maxdeg) 32{ 33 DUPFF ans = (DUPFF)malloc(sizeof(struct DUPFFstruct)); 34 ans->coeffs = 0; 35 if (maxdeg >= 0) ans->coeffs = (FFelem*)calloc(maxdeg+1,sizeof(FFelem)); 36 ans->maxdeg = maxdeg; 37 ans->deg = -1; 38 return ans; 39} 40 41void DUPFFfree(DUPFF x) 42{ 43} 44 45void DUPFFswap(DUPFF x, DUPFF y) 46{ 47} 48 49 50DUPFF DUPFFcopy(const DUPFF x) 51{ 52 return x; 53} 54 55 56void DUPFFshift_add(DUPFF f, const DUPFF g, int deg, const FFelem coeff) 57{ 58} 59 60 61DUPFF DUPFFexgcd(DUPFF *fcofac, DUPFF *gcofac, const DUPFF f, const DUPFF g) 62{ 63 DUPFF u, v, uf, ug, vf, vg; 64 FFelem q, lcu, lcvrecip, p; 65 int df, dg, du, dv; 66 67 printf("DUPFFexgcd called on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g)); 68 if (DUPFFdeg(f) < DUPFFdeg(g)) return DUPFFexgcd(gcofac, fcofac, g, f); /*** BUG IN THIS LINE ***/ 69 if (DUPFFdeg(f) != 2 || DUPFFdeg(g) != 1) abort(); 70 if (f->coeffs[0] == 0) return f; 71 /****** NEVER REACH HERE IN THE EXAMPLE ******/ 72 p = 2; 73 74 df = DUPFFdeg(f); if (df < 0) df = 0; /* both inputs are zero */ 75 dg = DUPFFdeg(g); if (dg < 0) dg = 0; /* one input is zero */ 76 u = DUPFFcopy(f); 77 v = DUPFFcopy(g); 78 79 uf = DUPFFnew(dg); uf->coeffs[0] = 1; uf->deg = 0; 80 ug = DUPFFnew(df); 81 vf = DUPFFnew(dg); 82 vg = DUPFFnew(df); vg->coeffs[0] = 1; vg->deg = 0; 83 84 while (DUPFFdeg(v) > 0) 85 { 86 dv = DUPFFdeg(v); 87 lcvrecip = FFmul(1, v->coeffs[dv]); 88 while (DUPFFdeg(u) >= dv) 89 { 90 du = DUPFFdeg(u); 91 lcu = u->coeffs[du]; 92 q = FFmul(lcu, lcvrecip); 93 DUPFFshift_add(u, v, du-dv, p-q); 94 DUPFFshift_add(uf, vf, du-dv, p-q); 95 DUPFFshift_add(ug, vg, du-dv, p-q); 96 } 97 DUPFFswap(u, v); 98 DUPFFswap(uf, vf); 99 DUPFFswap(ug, vg); 100 } 101 if (DUPFFdeg(v) == 0) 102 { 103 DUPFFswap(u, v); 104 DUPFFswap(uf, vf); 105 DUPFFswap(ug, vg); 106 } 107 DUPFFfree(vf); 108 DUPFFfree(vg); 109 DUPFFfree(v); 110 *fcofac = uf; 111 *gcofac = ug; 112 return u; 113} 114 115 116 117int main() 118{ 119 DUPFF f, g, cf, cg, h; 120 f = DUPFFnew(1); f->coeffs[1] = 1; f->deg = 1; 121 g = DUPFFnew(2); g->coeffs[2] = 1; g->deg = 2; 122 123 printf("calling DUPFFexgcd on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g)) ; 124 h = DUPFFexgcd(&cf, &cg, f, g); 125 return 0; 126} 127