text: However, in many cases this is not really an optimization: whereas the former algorithm is not susceptible to overflow when used with machine integers (that is, integers with a fixed upper bound of digits), the multiplication of old_s * a in computation of bezout_t can overflow, limiting this optimization to inputs which can be represented in less than half the maximal size. When using integers of unbounded size, the time needed for multiplication and division grows quadratically with the size of the integers. This implies that the "optimisation" replaces a sequence of multiplications/divisions of small integers by a single multiplication/division, which requires more computing time than the operations that it replaces, taken together.
  Simplification of fractions
  A fraction  is in canonical simplified form if  and  are coprime and  is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by
  if  then output "Division by zero"
  if  then ;     (for avoiding negative denominators)
  if  then output         (for avoiding denominators equal to 1)
  output
  The proof of this algorithm relies on the fact that  and  are two coprime integers such that , and thus . To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.