Quotient sequence with symmetric signed quotients?
nisse at lysator.liu.se
Tue Apr 23 10:39:31 UTC 2019
nisse at lysator.liu.se (Niels Möller) writes:
> Algorithm description was most recently posted here:
Rereading these old notes, I see this footnote,
Even though we cannot rule out the existence of a left-to-right \GCD
algorithm which is a constant factor faster than Jacobi. Such an
algorithm would lie outside the class of ``generic left-to-right \GCD
algorithms'' we describe in this paper, e.g., it might use
intermediate reduced values of varying signs and quotients that are
rounded towards the nearest integer rather than towards $-\infty$.
Is there any analysis of Euclid's algorithm, with different rounding of
the quotients? E.g., for the fibonacci inputs gcd(21, 13), we have a
standard quotient sequence of (1,1,1,1,1,1,1), taking 7 steps to get
from (21,13) to (1,0).
If we instead try quotients rounded to nearest, we get
(21,13) ----> (13, -5) ----> (-5, -2) ----> (-2, -1) ----> (-1, 0)
q = 2 q =-3 q = 2 q = 2
with 4 quotients rather than 7, and different from the standard continued
To possibly gain any performance, question is what happens to Lehmer's
algorithm. One would then want a signed hgcd2, with inputs being two
signed 128 bits numbers (two's complement), or possibly normalized so
that one is positive and the other signed, and output a 2x2 matrix with
elements being signed 64-bit numbers (the current unsigned hgdcd2
produces 63-bit unsigned matrix elements). If progress per hgcd2 step is
the same, then the quadratic component of the running time would be the
What I find interesting is that the current gcd algorithms in gmp try
hard to rule out underflow; all reduction matrices correspond to a
quotient sequences (q_1, q_2, ..., q_k) where either this is a corrrect
prefix of the quotient sequence/continued fraction expansion of the
original numbers, or (q_1, q_2, ..., q_k + 1) is a correct prefix. One
would get a bit more flexibility without that requirement.
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel