// Origin: abbott@dima.unige.it
|
// Origin: abbott@dima.unige.it
|
// PR c/5120
|
// PR c/5120
|
|
|
extern void * malloc (__SIZE_TYPE__);
|
extern void * malloc (__SIZE_TYPE__);
|
extern void * calloc (__SIZE_TYPE__, __SIZE_TYPE__);
|
extern void * calloc (__SIZE_TYPE__, __SIZE_TYPE__);
|
|
|
typedef unsigned int FFelem;
|
typedef unsigned int FFelem;
|
|
|
FFelem FFmul(const FFelem x, const FFelem y)
|
FFelem FFmul(const FFelem x, const FFelem y)
|
{
|
{
|
return x;
|
return x;
|
}
|
}
|
|
|
|
|
struct DUPFFstruct
|
struct DUPFFstruct
|
{
|
{
|
int maxdeg;
|
int maxdeg;
|
int deg;
|
int deg;
|
FFelem *coeffs;
|
FFelem *coeffs;
|
};
|
};
|
|
|
typedef struct DUPFFstruct *DUPFF;
|
typedef struct DUPFFstruct *DUPFF;
|
|
|
|
|
int DUPFFdeg(const DUPFF f)
|
int DUPFFdeg(const DUPFF f)
|
{
|
{
|
return f->deg;
|
return f->deg;
|
}
|
}
|
|
|
|
|
DUPFF DUPFFnew(const int maxdeg)
|
DUPFF DUPFFnew(const int maxdeg)
|
{
|
{
|
DUPFF ans = (DUPFF)malloc(sizeof(struct DUPFFstruct));
|
DUPFF ans = (DUPFF)malloc(sizeof(struct DUPFFstruct));
|
ans->coeffs = 0;
|
ans->coeffs = 0;
|
if (maxdeg >= 0) ans->coeffs = (FFelem*)calloc(maxdeg+1,sizeof(FFelem));
|
if (maxdeg >= 0) ans->coeffs = (FFelem*)calloc(maxdeg+1,sizeof(FFelem));
|
ans->maxdeg = maxdeg;
|
ans->maxdeg = maxdeg;
|
ans->deg = -1;
|
ans->deg = -1;
|
return ans;
|
return ans;
|
}
|
}
|
|
|
void DUPFFfree(DUPFF x)
|
void DUPFFfree(DUPFF x)
|
{
|
{
|
}
|
}
|
|
|
void DUPFFswap(DUPFF x, DUPFF y)
|
void DUPFFswap(DUPFF x, DUPFF y)
|
{
|
{
|
}
|
}
|
|
|
|
|
DUPFF DUPFFcopy(const DUPFF x)
|
DUPFF DUPFFcopy(const DUPFF x)
|
{
|
{
|
return x;
|
return x;
|
}
|
}
|
|
|
|
|
void DUPFFshift_add(DUPFF f, const DUPFF g, int deg, const FFelem coeff)
|
void DUPFFshift_add(DUPFF f, const DUPFF g, int deg, const FFelem coeff)
|
{
|
{
|
}
|
}
|
|
|
|
|
DUPFF DUPFFexgcd(DUPFF *fcofac, DUPFF *gcofac, const DUPFF f, const DUPFF g)
|
DUPFF DUPFFexgcd(DUPFF *fcofac, DUPFF *gcofac, const DUPFF f, const DUPFF g)
|
{
|
{
|
DUPFF u, v, uf, ug, vf, vg;
|
DUPFF u, v, uf, ug, vf, vg;
|
FFelem q, lcu, lcvrecip, p;
|
FFelem q, lcu, lcvrecip, p;
|
int df, dg, du, dv;
|
int df, dg, du, dv;
|
|
|
printf("DUPFFexgcd called on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g));
|
printf("DUPFFexgcd called on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g));
|
if (DUPFFdeg(f) < DUPFFdeg(g)) return DUPFFexgcd(gcofac, fcofac, g, f); /*** BUG IN THIS LINE ***/
|
if (DUPFFdeg(f) < DUPFFdeg(g)) return DUPFFexgcd(gcofac, fcofac, g, f); /*** BUG IN THIS LINE ***/
|
if (DUPFFdeg(f) != 2 || DUPFFdeg(g) != 1) abort();
|
if (DUPFFdeg(f) != 2 || DUPFFdeg(g) != 1) abort();
|
if (f->coeffs[0] == 0) return f;
|
if (f->coeffs[0] == 0) return f;
|
/****** NEVER REACH HERE IN THE EXAMPLE ******/
|
/****** NEVER REACH HERE IN THE EXAMPLE ******/
|
p = 2;
|
p = 2;
|
|
|
df = DUPFFdeg(f); if (df < 0) df = 0; /* both inputs are zero */
|
df = DUPFFdeg(f); if (df < 0) df = 0; /* both inputs are zero */
|
dg = DUPFFdeg(g); if (dg < 0) dg = 0; /* one input is zero */
|
dg = DUPFFdeg(g); if (dg < 0) dg = 0; /* one input is zero */
|
u = DUPFFcopy(f);
|
u = DUPFFcopy(f);
|
v = DUPFFcopy(g);
|
v = DUPFFcopy(g);
|
|
|
uf = DUPFFnew(dg); uf->coeffs[0] = 1; uf->deg = 0;
|
uf = DUPFFnew(dg); uf->coeffs[0] = 1; uf->deg = 0;
|
ug = DUPFFnew(df);
|
ug = DUPFFnew(df);
|
vf = DUPFFnew(dg);
|
vf = DUPFFnew(dg);
|
vg = DUPFFnew(df); vg->coeffs[0] = 1; vg->deg = 0;
|
vg = DUPFFnew(df); vg->coeffs[0] = 1; vg->deg = 0;
|
|
|
while (DUPFFdeg(v) > 0)
|
while (DUPFFdeg(v) > 0)
|
{
|
{
|
dv = DUPFFdeg(v);
|
dv = DUPFFdeg(v);
|
lcvrecip = FFmul(1, v->coeffs[dv]);
|
lcvrecip = FFmul(1, v->coeffs[dv]);
|
while (DUPFFdeg(u) >= dv)
|
while (DUPFFdeg(u) >= dv)
|
{
|
{
|
du = DUPFFdeg(u);
|
du = DUPFFdeg(u);
|
lcu = u->coeffs[du];
|
lcu = u->coeffs[du];
|
q = FFmul(lcu, lcvrecip);
|
q = FFmul(lcu, lcvrecip);
|
DUPFFshift_add(u, v, du-dv, p-q);
|
DUPFFshift_add(u, v, du-dv, p-q);
|
DUPFFshift_add(uf, vf, du-dv, p-q);
|
DUPFFshift_add(uf, vf, du-dv, p-q);
|
DUPFFshift_add(ug, vg, du-dv, p-q);
|
DUPFFshift_add(ug, vg, du-dv, p-q);
|
}
|
}
|
DUPFFswap(u, v);
|
DUPFFswap(u, v);
|
DUPFFswap(uf, vf);
|
DUPFFswap(uf, vf);
|
DUPFFswap(ug, vg);
|
DUPFFswap(ug, vg);
|
}
|
}
|
if (DUPFFdeg(v) == 0)
|
if (DUPFFdeg(v) == 0)
|
{
|
{
|
DUPFFswap(u, v);
|
DUPFFswap(u, v);
|
DUPFFswap(uf, vf);
|
DUPFFswap(uf, vf);
|
DUPFFswap(ug, vg);
|
DUPFFswap(ug, vg);
|
}
|
}
|
DUPFFfree(vf);
|
DUPFFfree(vf);
|
DUPFFfree(vg);
|
DUPFFfree(vg);
|
DUPFFfree(v);
|
DUPFFfree(v);
|
*fcofac = uf;
|
*fcofac = uf;
|
*gcofac = ug;
|
*gcofac = ug;
|
return u;
|
return u;
|
}
|
}
|
|
|
|
|
|
|
int main()
|
int main()
|
{
|
{
|
DUPFF f, g, cf, cg, h;
|
DUPFF f, g, cf, cg, h;
|
f = DUPFFnew(1); f->coeffs[1] = 1; f->deg = 1;
|
f = DUPFFnew(1); f->coeffs[1] = 1; f->deg = 1;
|
g = DUPFFnew(2); g->coeffs[2] = 1; g->deg = 2;
|
g = DUPFFnew(2); g->coeffs[2] = 1; g->deg = 2;
|
|
|
printf("calling DUPFFexgcd on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g)) ;
|
printf("calling DUPFFexgcd on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g)) ;
|
h = DUPFFexgcd(&cf, &cg, f, g);
|
h = DUPFFexgcd(&cf, &cg, f, g);
|
return 0;
|
return 0;
|
}
|
}
|
|
|