Never been to DZone Snippets before?

Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Euclid's extended algorithm (See related posts)

Basically Euclid's algorithm for finding the largest common denominator, this one is modified in order to obtain the numbers d, x, y, where d is the dennominator and they check the following equation:
d = ax + by

def euclidExtended(a, b):
  if b == 0:
    return a, 1, 0
  dd, xx, yy = euclidExtended(b, a % b)
  d, x, y = dd, yy, xx - int(a / b) * yy
  return d, x, y
to c numbers algorithm Prime euclid by scvalex on Fri Jun 22 10:59:27 -0400 2007

You need to create an account or log in to post comments to this site.


Click here to browse all 4857 code snippets

Related Posts