Half-GCD and fast rational recovery
Daniel Lichtblau · 2005
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.