euclid code

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

« Newer Snippets

Older Snippets »

Showing 1-3 of 3 total RSS

Modular linear equation solver

Prints the roots of this equation:
ax = b (mod n)

Relies on Euclid's extended algorithm:
http://snippets.dzone.com/posts/show/4192

def solveLinearModularEquation(a, b, n):
  d, xx, yy = euclidExtended(a, n)
  if (b % d == 0):
    x0 = (xx * (b / d)) % n
    for i in xrange(0, d):
      print (x0 + i * (n / d)) % n,
  else:
    print "No solution"
  print

to python euclid linear equation modular by scvalex on Jun 22, 2007

Euclid's extended algorithm

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 Jun 22, 2007

Euclid's algorithm

Euclid(a, b) calculates the largest common denominator d, and returns it.

Uses the well-known Euclid's algorithm.

def euclid(a, b):
  while b != 0:
    r = a % b
    a = b
    b = r
  return a

to python algorithm euclid lcd by scvalex on Jun 22, 2007