# Author: Sam Erickson
# Date: 2/23/2016
#
# Program Description: This program gives the integer coefficients x,y to the
# equation ax+by=gcd(a,b) given by the extended Euclidean Algorithm.
def extendedEuclid(a,b):
"""
Preconditions - a and b are both positive integers.
Posconditions - The equation for ax+by=gcd(a,b) has been returned where
x and y are solved.
Input - a : int, b : int
Output - ax+by=gcd(a,b) : string
"""
b,a=max(a,b),min(a,b)
# Format of euclidList is for back-substitution
euclidList=[[b%a,1,b,-1*(b//a),a]]
while b%a>0:
b,a=a,b%a
euclidList.append([b%a,1,b,-1*(b//a),a])
if len(euclidList)>1:
euclidList.pop()
euclidList=euclidList[::-1]
for i in range(1,len(euclidList)):
euclidList[i][1]*=euclidList[i-1][3]
euclidList[i][3]*=euclidList[i-1][3]
euclidList[i][3]+=euclidList[i-1][1]
expr=euclidList[len(euclidList)-1]
strExpr=str(expr[1])+"*"+str(expr[2])+" + "+str(expr[3])+"*"+str(expr[4]) \
+" = "+str(euclidList[0][0])
return strExpr
Diff to Previous Revision
--- revision 1 2013-08-09 06:06:58
+++ revision 2 2016-03-03 07:12:28
@@ -1,89 +1,32 @@
# Author: Sam Erickson
-# Date: 7/14/2013
+# Date: 2/23/2016
#
# Program Description: This program gives the integer coefficients x,y to the
-# equation ax+by=gcd(a,b) given by the extended Euclidean Algorithm. Note that
-# this program does not use the typical extended Euclidean Algorithm to find
-# ax+by=gcd(a,b).
-"""
-General algorithm for program:
-1. Get integers a and b from user.
+# equation ax+by=gcd(a,b) given by the extended Euclidean Algorithm.
-2. Call test(a,b) and assign to get one integer coefficient for the equation
-(1/gcd(a,b))*[a*x+b*y=gcd(a,b)].
-
-
-3. Call getCoffic(min2,aNew,bNew,GCD) to return a string for of the equation
-a*x+b*y=gcd(a,b) for printing.
-"""
-
-def test(a,b):
+def extendedEuclid(a,b):
"""
- Input: a and b must be integers.
-
- Output: If solutionsDict isn't empty, then the min positive integer along
- with a/gcd(a,b), b/gcd(a,b), and gcd(a,b) will be returned. If solutionsDict
- does not contain positive integers the max negative integer will be returned
- instead of the least positive integer.
- Otherwise if solutionsDict is empty, None,None,None,None will be returned.
+ Preconditions - a and b are both positive integers.
+ Posconditions - The equation for ax+by=gcd(a,b) has been returned where
+ x and y are solved.
+ Input - a : int, b : int
+ Output - ax+by=gcd(a,b) : string
"""
- from fractions import gcd
- # Test which of a and b is larger.
- if b>a:
- a,b=b,a
-
- solutionsDict={}
-
- # Iterate range(1,aNew+1) to find solutions to [1-bNew*x]%aNew==0
- for x in range(1,abs(a//gcd(a,b))):
- if (1-(b//gcd(a,b))*x)%(a//gcd(a,b))==0:
- solutionsDict[x]=x
- # Determine if solutionsDict is empty.
- if len(solutionsDict)!=0:
- # Make sure solutionsDict contains positive integers
- ct=0
- for x in solutionsDict:
- if x>0:
- ct+=1
- break
+ b,a=max(a,b),min(a,b)
+ # Format of euclidList is for back-substitution
+ euclidList=[[b%a,1,b,-1*(b//a),a]]
+ while b%a>0:
+ b,a=a,b%a
+ euclidList.append([b%a,1,b,-1*(b//a),a])
+ if len(euclidList)>1:
+ euclidList.pop()
+ euclidList=euclidList[::-1]
+ for i in range(1,len(euclidList)):
+ euclidList[i][1]*=euclidList[i-1][3]
+ euclidList[i][3]*=euclidList[i-1][3]
+ euclidList[i][3]+=euclidList[i-1][1]
- # If solutionsDict contains positive integers get least positive integer
- if ct>0:
- while min(solutionsDict)<=0:
- del d1[min(solutionsDict)]
-
- return min(solutionsDict),a//gcd(a,b),b//gcd(a,b),gcd(a,b)
-
- else:
- return max(solutionsDict),a//gcd(a,b),b//gcd(a,b),gcd(a,b)
-
- else:
- return None,None,None,None
-
-def getCoeffic(Min,aPrime,bPrime,GCD):
- """
- Input: Min,aPrime,bPrime,GCD is the 4-tuple obtained from test(a,b), in the
- same order.
-
- Output: If the final expression ax+by really does equal gcd(a,b),and if
- Min isn't None, the string "ax+by=gcd(a,b)" will be returned. Otherwise
- if Min=None or output string "ax+by" is not equal to gcd(a,b), error
- messages will be printed accordingly.
- """
-
- # Create string for ax+by=gcd(a,b)
- if Min!=None:
- cA=int((1-Min*bPrime)/aPrime)
- cB=Min
- s1=str(cA)+"*"+str(aPrime*GCD)+" + "+str(cB)+"*"+str(bPrime*GCD)
- s2="="+str(GCD)
-
- # Test that string expression is correct before returning it
- if eval(s1)==GCD:
- return s1+s2
- # Print Error Message
- else:
- print("The program must have a bug since in the final expression ax+by was not equal to gcd(a,b).")
- # Print Error Message
- else:
- print("Either program bug caused no results or algorithm failed.")
+ expr=euclidList[len(euclidList)-1]
+ strExpr=str(expr[1])+"*"+str(expr[2])+" + "+str(expr[3])+"*"+str(expr[4]) \
+ +" = "+str(euclidList[0][0])
+ return strExpr
