well, COMPUTE THE GCD AND LCM OF TWO NUMBERS
' TOGETHER WITH A BEZOUT EQUALITY
' The rationale is to use the Euclides algorithm
' and to memorize the results in a 2x2 Matrix Dn
' such that
' a Rn-1
' = Dn .
' b Rn-2
'
' if Rn = Qn x Rn-1 + Rn+1
' then Dn+1 = Dn . Q , where
'
' Qn 1
' Q =
' 1 0
' (Qo being the identity matrix)
'
' For performance reasons the matrix D is kept in variables
' d1 through d4
Const computeCaption As String = "&Compute GCD(a,b)," & _
vbCr _
& "LCM(a,b) and" & vbCr _
& "Bezout relationship"
Const newValCaption = "Enter &new" & vbCr & "values"
' the numbers whose GDC and LCM are wanted
Dim A As Long, B As Long
' the matrix and temp storage variables
Dim d1 As Long, d2 As Long, d3 As Long, d4 As Long
Dim dPrim1 As Long, dPrim3 As Long
Dim det As Long ' determinant of D
' the inverse of matrix D
Dim b1 As Long, b2 As Long
' Dim b3 As Long, b4 As Long
' the variables for Euclides algorithm
Dim X As Long, Y As Long, Q As Long, R As Long
Dim LCM As Double
' miscellaneous
Dim sizW As Long, sizH As Long
Const minMargin As Long = 200
Const timerTick As Long = 1000 ' 5 seconds
Private Sub cmdCompute_Click()
If cmdCompute.Caption = computeCaption Then
If txtA.Text = "" Then
txtA.SetFocus: Exit Sub
Else
If txtB.Text = "" Then txtB.SetFocus: Exit Sub
End If
' compute GCD, etc.
txtA.Enabled = False
txtB.Enabled = False
If getAandB Then
cmdCompute.Enabled = False
' initialize the matrix to Identity
d1 = 1: d2 = 0: d3 = 0: d4 = 1
' set A as larger of the numbers
If A < B Then R = A: A = B: B = R
X = A: Y = B: Q = 0: R = A
txtA.Text = CStr(A)
txtB.Text = CStr(B)
det = 1
' Euclides algorithm is just in the 6 lines below !
Do While R <> 0
euclDiv
multMat
X = Y
Y = R
Loop
' Here we've got (A,B) = D . (X,0) and X = GCD (A,B)
' and A = d1 * X , B = d3 * X , LCM(A,B) = d1 * d3 * X
' we inverse the matrix (just as much as necessary)
' to get a Bezout relationship
invMat
lblResul t.Caption = "GCD(" & CStr(A) & "," & CStr(B) & _
") = " & CStr(X) & vbCr
If X = 1 Then
lblResult.Caption = lblResult.Caption & _
"(" & CStr(A) & " and " & CStr(B) & " are relatively " & _
"prime)" & vbCr
End If
lblResult.Caption = lblResult.Caption & _
CStr(A) & " = " & CStr(d1) & " * " & CStr(X) & vbCr & _
_
CStr(B) & " = " & CStr(d3) & " * " & CStr(X) & vbCr
' we have GCD(A,B) = X = b1 * A + b2 * B
' we check it if we can (using the LCM variable for
' capacity reasons)
On Error Resume Next
LCM = b1 * A + b2 * B
If Err.Number = 0 Then
If LCM <> X Then
MsgBox "Fatal error #03 - Must quit", vbCritical, _
"Fatal error #03 in Bezout"
End
End If
End If
Err.Clear
LCM = d1 * d3 * X ' LCM(a,b)
If Err.Number = 0 Then
lblResult.Caption = lblResult.Caption & vbCr & _
"LCM(" & CStr(A) & "," & CStr(B) & ") = " & _
CStr(LCM) & vbCr & _
CStr(LCM) & " = " & CStr(A) & " * " & CStr(d3) & _
vbCr & _
CStr(LCM) & " = " & CStr(B) & " * " & CStr(d1)
Else
lblResult.Capt ion = lblResult.Caption
Answered by
Romi
, an ibibo Master,
at
2:42 PM on June 27, 2008
