  The classical technique for proving termination of a generic sequential
computer program involves the synthesis of a ranking function for each loop of
the program. Linear ranking functions are particularly interesting because many
terminating loops admit one and algorithms exist to automatically synthesize
it. In this paper we present two such algorithms: one based on work dated 1991
by Sohn and Van Gelder; the other, due to Podelski and Rybalchenko, dated 2004.
Remarkably, while the two algorithms will synthesize a linear ranking function
under exactly the same set of conditions, the former is mostly unknown to the
community of termination analysis and its general applicability has never been
put forward before the present paper. In this paper we thoroughly justify both
algorithms, we prove their correctness, we compare their worst-case complexity
and experimentally evaluate their efficiency, and we present an open-source
implementation of them that will make it very easy to include
termination-analysis capabilities in automatic program verifiers.
