 The computational efficiency of Euclid's algorithm has been studied thoroughly.This efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step.The first known analysis of Euclid's algorithm is due to A.