Extended Euklidean Algorithm (VBA) ·

Abstract

You need to represent a number as a non-negative linear combination of two positive integers?

You can achieve this with the (external link!) extended Euklidean Algorithm:

sbEuklid_en

Note: If your desired result is a multiple of the greatest common divisor of the inputs then there will always be an integer solution, but not necessarily a non-negative one. Example: You can represent 1 with the inputs 5 and 3 because 1 is the GCD of 3 and 5: 1 = 2 * 5 + (-3) * 3. But you cannot achieve this with non-negative integers only.

Another note: There might be more than one non-negative integer solution, with bAllNonNegative = True the algorithm below will return a minimal sum of the output values. When there is an integer solution then there is a countable number of solutions.

Appendix – sbEuklid Code

Please read my Disclaimer.

Possible error returns of the program are:

#NV! - There is no solution
#VALUE! - bAllNonNegative = True but not all inputs are non-negative
#NUM! - bAllNonNegative = True but there is no non-negative integer solution

Option Explicit

Function sbEuklid(lInput1 As Long, _
                  lInput2 As Long, _
                  Optional lDesiredResult As Long, _
                  Optional bAllNonNegative As Boolean = False) As Variant
'Extended Euklidean Algorithm which calculates two factors f1 and f2
'so that lDesiredResult = f1 * lInput1 + f2 * lInput2. If lDesiredResult
'is not given, the greatest common divisor (GCD) of lInput1 and lInput2
'will be calculated. If bAllNonNegative is True then we try to achieve a
'non-negative result of all inputs and outputs with minimal Sum(f1+f2).
'Error return values can be:
'xlErrNA    - There is no solution
'xlErrValue - bAllNonNegative = True but not all inputs are non-negative
'xlErrNum   - bAllNonNegative = True but there is no non-negative solution
'Source (EN): http://www.sulprobil.com/sbeuklid_en/
'Source (DE): http://www.bplumhoff.de/sbeuklid_de/
'(C) (P) by Bernd Plumhoff 20-May-2024 PB V0.4
Dim lDiv                   As Long
Dim lGCD                   As Long
Dim lRest                  As Long
Dim lT1                    As Long
Dim lT2                    As Long
Dim vR                     As Variant
Dim vT                     As Variant

With Application '.WorksheetFunction 'Test with, release without
  lGCD = .Gcd(lInput1, lInput2)
  If IsMissing(lDesiredResult) Then lDesiredResult = lGCD
  lRest = lDesiredResult Mod lGCD
  If lRest <> 0 Then
    sbEuklid = CVErr(xlErrNA) 'There is no solution
  Else
    If bAllNonNegative And (lInput1 < 0 Or lInput2 < 0 Or lDesiredResult < 0) Then
      sbEuklid = CVErr(xlErrValue) 'bAllNonNegative but not all inputs are non-negative
    Else
      'See https://www.arndt-bruenner.de/mathe/scripts/erweitertereuklid.htm
      vR = [{1, 0; 0, 1}]
      vT = [{0, 1; 1, 0}]
      lT1 = lInput1
      lT2 = lInput2
      Do
        lDiv = lT1 \ lT2
        lRest = lT1 Mod lT2
        lT1 = lT2
        lT2 = lRest
        vT(2, 2) = -lDiv
        vR = .MMult(vR, vT)
      Loop While lRest <> 0
      vR = .MMult(Array(lDesiredResult \ lGCD, 0), .Transpose(vR))
      Debug.Assert lDesiredResult = vR(1) * lInput1 + vR(2) * lInput2 'Just assuring
      sbEuklid = vR
      If bAllNonNegative Then
        If lInput1 > lInput2 Then
          lT1 = lDesiredResult \ lInput1 + 1
          Do While lT1 > 0
            lT1 = lT1 - 1
            If (lDesiredResult - lInput1 * lT1) Mod lInput2 = 0 Then GoTo Success1
          Loop
          GoTo ErrorExit
Success1: vR(1) = lT1
          vR(2) = (lDesiredResult - lInput1 * lT1) \ lInput2
        Else
          lT2 = lDesiredResult \ lInput2 + 1
          Do While lT2 > 0
            lT2 = lT2 - 1
            If (lDesiredResult - lInput2 * lT2) Mod lInput1 = 0 Then GoTo Success2
          Loop
          GoTo ErrorExit
Success2: vR(2) = lT2
          vR(1) = (lDesiredResult - lInput2 * lT2) \ lInput1
        End If
        sbEuklid = vR
      End If
    End If
  End If
  'Debug.Assert lDesiredResult = vR(1) * lInput1 + vR(2) * lInput2 'Just testing
Exit Function
ErrorExit:
  sbEuklid = CVErr(xlErrNum)
End With

End Function

Download

Please read my Disclaimer.

sbEuklid.xlsm [25 KB Excel file, open and use at your own risk]