Quotient sequence with symmetric signed quotients?

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> Algorithm description was most recently posted here:
> https://gmplib.org/list-archives/gmp-bugs/2017-August/004190.html

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
fraction expansion.

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
same.

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.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.