Uitgebreid Euclidisch Algoritme

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

Leave a Reply

Your email address will not be published. Required fields are marked *