Implementing the Thull-Yap Algorithm for Computing Euclidean Remainder Sequences

There are two types of integer gcd algorithms: those which compute the sequence of remainders of Euclid's algorithm and those which build different sequences. The former are more difficult to validate and analyse, whereas the latter are simpler and more efficient. When one wants the euclidean remainders (for instance if one wants to compute continued fractions), only the former can be used. Our main focus is the subquadratic time Thull-Yap GCD algorithm, and in fact on its core computing a half gcd (TYHGCD). This algorithm is tricky due to the difficulty in correcting the remainder sequence that comes back from a recursive call. The aim of this work is to revise TYHGCD in order to implement it using GMP. We clarify some points of the algorithm, in particular the stopping conditions that are always difficult to set correctly. We add a base case to speed up the whole algorithm, using Jebelean's quadratic algorithm with a stopping condition. We give our own modified version and add the proofs where needed. We insist on the test phase for this algorithm, giving families of hard cases for all branches, some of which are rarely activated. We give some details on our implementation in GMP using low-level functions, adding some remarks on the use of fast multiplications techniques. We pay attention to the data structure needed to store partial quotients, enabling to navigate rapidly back and forth in the sequence of Euclidean remainders. Benchmarks are provided. Some comments are made on Lichtblau's algorithm, which is close in spirit to the Thull-Yap algorithm.