half-gcd and fast rational recovery
Over the past few decades several variations on a "half GCD" algorithm for obtaining the pair of terms in the middle of a Euclidean sequence have been proposed. In the integer case algorithm design and proof of correctness are complicated by the effect of carries. This paper will demonstrate a variant with a relatively simple proof of correctness. We then apply this to the task of rational recovery for a linear algebra solver.
rational recovery subquadratic arithmetic integer gcd