1 // Origin: abbott@dima.unige.it
4 extern void * malloc (__SIZE_TYPE__
);
5 extern void * calloc (__SIZE_TYPE__
, __SIZE_TYPE__
);
7 typedef unsigned int FFelem
;
9 FFelem
FFmul(const FFelem x
, const FFelem y
)
22 typedef struct DUPFFstruct
*DUPFF
;
25 int DUPFFdeg(const DUPFF f
)
31 DUPFF
DUPFFnew(const int maxdeg
)
33 DUPFF ans
= (DUPFF
)malloc(sizeof(struct DUPFFstruct
));
35 if (maxdeg
>= 0) ans
->coeffs
= (FFelem
*)calloc(maxdeg
+1,sizeof(FFelem
));
41 void DUPFFfree(DUPFF x
)
45 void DUPFFswap(DUPFF x
, DUPFF y
)
50 DUPFF
DUPFFcopy(const DUPFF x
)
56 void DUPFFshift_add(DUPFF f
, const DUPFF g
, int deg
, const FFelem coeff
)
61 DUPFF
DUPFFexgcd(DUPFF
*fcofac
, DUPFF
*gcofac
, const DUPFF f
, const DUPFF g
)
63 DUPFF u
, v
, uf
, ug
, vf
, vg
;
64 FFelem q
, lcu
, lcvrecip
, p
;
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 ******/
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 */
79 uf
= DUPFFnew(dg
); uf
->coeffs
[0] = 1; uf
->deg
= 0;
82 vg
= DUPFFnew(df
); vg
->coeffs
[0] = 1; vg
->deg
= 0;
84 while (DUPFFdeg(v
) > 0)
87 lcvrecip
= FFmul(1, v
->coeffs
[dv
]);
88 while (DUPFFdeg(u
) >= dv
)
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
);
101 if (DUPFFdeg(v
) == 0)
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;
123 printf("calling DUPFFexgcd on degrees %d and %d\n", DUPFFdeg(f
), DUPFFdeg(g
)) ;
124 h
= DUPFFexgcd(&cf
, &cg
, f
, g
);