Paper with an improved bound for half-gcd matrix sizes
nisse at lysator.liu.se
Wed Feb 8 19:57:26 CET 2023
Juraj Sukop and myself just published a short paper with an improved
bound (+ one correction) to my older gcd paper which describes the
algorithm used in GMP.
>From my perspective, it's a stronger and more rigorous argument, related
to this comment at
/* Furthermore, assume M ends with a quotient (1, q; 0, 1),
then either q or q + 1 is a correct quotient, and M1 will
start with either (1, 0; 1, 1) or (2, 1; 1, 1). This
rules out the case that the size of M * M1 is much
smaller than the expected M->n + M1->n. */
and it clarifies some of the subtler details.
Thanks to Paul for helping out in getting the paper published, and
suggesting publishing on HAL.
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel