Half-GCD and fast rational recovery

D. Lichtblau


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. Last we show a different method based on lattice reduction which, while not fast, is of independent interest as yet another interesting thing one can do with lattice reduction.