-
- Show that the above algorithm
computes the GCD of
and
.
-
- Assume that
and
are two machine integers.
Let
and
the number of bits (in binary-expansion) of
and
respectively.
Give an upper bound for the number of machine word operations
(comparison of two machine integers, subtraction, shift,
accessing a bit of a machine integer) needed for
computing
.
-
- Adapt the above algorithm for computing GDCs in
, that is
for univariate polynomials with integer coefficients modulo
.
Marc Moreno Maza
2008-03-18