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