Bijvoorbeeld in A1:
=ExtendedEuclideanWithSteps(1190;672;33;11;TRUE)
Function ExtendedEuclideanWithSteps(a As Long, b As Long, ByRef x As Long, ByRef y As Long, Optional showSteps As Boolean = False) As Long
' Extended Euclidean Algorithm with step-by-step explanation
Dim temp As Long
Dim x1 As Long, x2 As Long, y1 As Long, y2 As Long
Dim q As Long, r As Long
Dim stepCount As Integer
Dim result As String
Dim originalA As Long, originalB As Long
' Store original values
originalA = a
originalB = b
' Ensure positive numbers
a = Abs(a)
b = Abs(b)
' Handle zero cases
If a = 0 And b = 0 Then
x = 0: y = 0
ExtendedEuclideanWithSteps = 0
Exit Function
End If
If a = 0 Then
x = 0: y = Sgn(b)
ExtendedEuclideanWithSteps = b
Exit Function
End If
If b = 0 Then
x = Sgn(a): y = 0
ExtendedEuclideanWithSteps = a
Exit Function
End If
' Initialize coefficients and step counter
x1 = 1: x2 = 0
y1 = 0: y2 = 1
stepCount = 0
If showSteps Then
result = "Extended Euclidean Algorithm Steps:" & vbCrLf & vbCrLf
result = result & "Find GCD(" & originalA & ", " & originalB & ") and coefficients x, y" & vbCrLf
result = result & "such that: " & originalA & "x + " & originalB & "y = GCD" & vbCrLf & vbCrLf
result = result & "Step " & stepCount & ":" & vbCrLf
result = result & "a = " & a & ", b = " & b & vbCrLf
result = result & "x1 = " & x1 & ", x2 = " & x2 & vbCrLf
result = result & "y1 = " & y1 & ", y2 = " & y2 & vbCrLf & vbCrLf
End If
' Extended Euclidean Algorithm
Do While b <> 0
stepCount = stepCount + 1
q = a \ b
r = a Mod b
If showSteps Then
result = result & "Step " & stepCount & ":" & vbCrLf
result = result & a & " = " & b & " * " & q & " + " & r & vbCrLf
End If
' Update coefficients
temp = x2
x2 = x1 - q * x2
x1 = temp
temp = y2
y2 = y1 - q * y2
y1 = temp
If showSteps Then
result = result & "New coefficients: x1 = " & x1 & ", x2 = " & x2 & vbCrLf
result = result & " y1 = " & y1 & ", y2 = " & y2 & vbCrLf & vbCrLf
End If
' Update a and b
a = b
b = r
Loop
' Set results
x = x1
y = y1
ExtendedEuclideanWithSteps = a
If showSteps Then
result = result & "Final Result:" & vbCrLf
result = result & "GCD(" & originalA & ", " & originalB & ") = " & a & vbCrLf
result = result & "Coefficients: x = " & x & ", y = " & y & vbCrLf
result = result & "Verification: " & originalA & "*" & x & " + " & originalB & "*" & y & " = "
result = result & (originalA * x + originalB * y) & " = " & a
MsgBox result
End If
End Function