Cofactor canonicalisation of mpn_gcdext
Torbjorn Granlund
tg at gmplib.org
Mon Nov 23 14:43:00 CET 2009
nisse at lysator.liu.se (Niels Möller) writes:
It almost spells out the result we're talking about. Part (v) says, in
our notation:
|t| <= u / r_{\lambda-1}, |s| <= v / r_{\lambda-1}
where
r_{\lambda-1} = r_\lambda q_\lambda = g q_\lambda
is the last-but-one nonzero remainder in the remainder sequence.
So equality, |t| = u / g or |s| = v/g, is not ruled out, as far as I
see. When does that happen, and which border is hit? When v/g is even,
one could choose between the ranges
I suppose u = 0 or v = 0 both give equality. And so does |u| = |v|. I
suppose these are the only cases where we get equality, but I have no
proof...
--
Torbjörn
More information about the gmp-devel
mailing list