Welcome, guest | Sign In | My Account | Store | Cart
```# 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: