Extending the binary gcd algorithms (Q2764238)

The extended binary gcd algorithm, that finds \(u,v\), and \((A,B)\) for given \(A\) and \(B\) such that \(uA+ vB= (A,B)\), is speeded up by arranging for shifts as large as possible to be used at each stage. Various algorithms are given in detail and results of experiments, on 40000 pairs \(A,B\) for each of 24 different lengths of numbers up to 1030 bits, are reported. The results indicate that execution time is roughly halved.NEWLINENEWLINEFor the entire collection see [Zbl 0976.00054].