Visual Basic .NET: Diophantische Gleichung

Erklärung

Dass die Gleichung nicht immer lösbar ist, kann durch das Beispiel $a=b=0$ und $c=1$ veranschaulicht werden. Es gibt auch nicht so triviale Beispiele, z. B. wenn $a$ und $b$ beide gerade, $c$ jedoch ungerade ist. Die linke Seite wäre immer gerade und die rechte ungerade.

Der nächsten beiden Tipps sind für die Implementierung besonders wertvoll. Der erste gibt einen Hinweis auf eine mögliche Signatur der Funktion. Zum zweiten: Nun, wenn $c=0$ gilt, können wir mit $x=y=0$ sofort eine einfache Lösung angeben. Vor allem aber können wir in den folgenden Überlegungen immer $c\neq 0$ annehmen, da dieser Fall ja gerade behandelt wurde.

Nun überlegen wir uns, was $a=0$ bedeutet. $a$ und $b$ sind vertauschbar, wenn wir die danach die Lösungen vertauschen. Wenn nun auch $b=0$ gilt gewinnen wir damit zwar nichts, aber wir können es ja extra behandeln, denn dieser Fall ist sehr einfach: Die linke Seite ist unabhängig von $x$ und $y$ immer $0$. Die rechte Seite ist $c$, von dem wir ausgeschlossen haben, dass es $0$ ist. Also gibt es keine Lösung. Für den Fall $b\neq 0$ wenden wir die erwähnte Methode mit Vertauschen an. Wir verlassen uns dabei darauf, dass wir die Aufgabe dann lösen können

Jetzt kommt der wesentliche Algorithmus. Wenn wir die vorhergehenden Überlegungen zusammenfassen, wissen wir an dieser Stelle nur, dass $a\neq 0$ und $c\neq 0$ gilt. Wenn wir nun auch noch $b=0$ annehmen, reduziert sich die Gleichung auf $ax=c$. Weil wir ja mit ganzen Zahlen arbeiten, ist das nur lösbar, wenn $a$ ein Teiler von $c$ ist; mit anderen Worten, der Divisionsrest von $c$ geteilt durch $a$ ist $0$. Der Quotient ist dann die Lösung $x$, und wir können $y=0$ setzen.

Für den anderen Fall, also $b\neq 0$, behandeln, werden uns eine recht klare Anweisungen gegeben. Unter Umständen können wir die Schritte noch optimieren.

Aus den Überlegungen folgt, dass der Algorithmus terminiert wenn er es für $a,b,c\neq 0$ tut. In allen anderen Fällen können wir die Lösung direkt angeben oder erkennen, dass sie nicht existiert. Wenn wir den rekursiven Aufruf betrachten, erkennen wir, dass dort wo $b$ eingesetzt wird, $r$ steht. Aus der Angabe wissen wir, dass $|r|<|b|$ gilt. Also spätestens nach $|b|$ Schritten wird für $r$, d. h. für $b$ der Wert $0$ eingesetzt. Dann terminiert die Funktion bekanntermaßen.

Code

Code:  

' Die Signatur wird uns schon auf dem Silbertablett serviert.
Private Function Diophant(ByVal a As Integer, ByVal b As Integer, ByVal c As Integer, ByRef x As Integer, ByRef y As Integer) As Boolean
    ' Behandlung der Trivialfälle.
    If c = 0 Then
        x = 0 ' Wir geben die Lösungen an.
        y = 0
        Return True ' Wir haben Lösungen, also True.
    ElseIf a = 0 Then
        If b = 0 Then Return False ' c <> 0, also keine Lösung.
        Return Diophant(b, a, c, y, x) ' Hier vertauschen wir geschickt a und b sowie x und y.
    End If
    
    ' Nun der eigentliche Algorithmus:
    If b = 0 Then
        ' Dass Mod den Divisionsrest liefert, sollte bekannt sein.
        If c Mod a = 0 Then
            x = c \ a ' Der ganzzahlige Divisionsoperator \ sollte bekannt sein.
            y = 0
            Return True
        Else
            Return False
        End If
    Else
        Dim q = a  \  b,
            r = a Mod b
        ' Beachte: Hier sind x und y vertauscht! Damit wird die Zuordnung x = y' ohne extra Anweisung erledigt.
        If Diophant(b, r, c, y, x) Then
            ' Wenn wir hier sind, war das bisherige Lösen erfolgreich und wir können die Lösung nach Anleitung angeben.
            ' in der Zuweisung für y müssen wir x' und y' vertauschen, also steht da: y = y' - q * x'.
            ' x' und y' sind schon in Form von x und y vorhanden.
            y -= q * x ' bleibt als einziges zu tun.
            Return True
        Else
            Return False
        End If
    End If
End Function

Dieser Code ist mit den obigen Erklärungen gut verständlich. Potenzial für Optimierungen gibt es durchaus, sie beziehen sich auf die Abschnitte mit Else Return False und es ist verhältnismäßig gering.

Die imperative Methode

Nun wollen wir uns noch an die Implementierung des imperativen Algorithmus wagen. Wenn wir die rekursive Lösung betrachten so fällt uns auf, dass wir nach dem rekursiven Aufruf nur noch $q$ zusätzlich benötigen. Alles andere wird durch Parameter weitergegeben. Da jeder rekursive Aufruf sein eigenes $q$ hat, gibt es nicht ein $q$, sondern eine ganze Reihe. Sie wird genau in umgekehrter Reihenfolge auf- und abgebaut, entspricht also einem Stapel, auch Stack oder Kellerspeicher genannt. Im .NET Framework gibt es die Klasse System.Collections.Generics.Stack(Of T), die uns einen vorgefertigten Stapelspeicher zur Verfügung stellt. Mit Push legen wir etwas oben drauf, mit Pop nehmen wir etwas herunter.

Code:  

Private Function Diophant(ByVal a As Integer, ByVal b As Integer, ByVal c As Integer, ByRef x As Integer, ByRef y As Integer) As Boolean
    ' Behandlung der Trivialfälle erfolgt wie vorhin. Der einzelne rekursive Aufruf soll uns nicht stören; er ist verschmerzbar, da er höchstens einmal auftritt.
    Dim stack As New Stack(Of Integer)
    While b <> 0
        Dim q = a  \  b,
            r = a Mod b
        stack.Push(q)
        a = b
        b = r
    Wend
    ' Ab hier gilt b = 0.
    If c Mod a <> 0 Then Return False
    x = c \ a
    y = 0
    While stack.Count > 0
        Dim q = stack.Pop
        ' Hier kommen wir leider um eine Hilfsvariable nicht herum.
        Dim h = x
        x = y
        y = h - q * y
    Wend
    Return True
End Function

Auch dieser Code ist optimierbar. Jedoch leidet dann die Verständlichkeit arg darunter.