Größter gemeinsamer Teiler zweier ganzer Zahlen (VB)

Sprache / Programm: VBA ab Office 95

Beschreibung

Wie kürzt man ganzzahlige Brüche?

Die mathematische Beschreibung dazu lieferte bereits der Grieche Euklid und sie wurde unter dem Namen euklidischer Algorithmus bekannt.

Die Funktion ermittelt aus zwei ganzen Zahlen den größten gemeinsamen Teiler (ggT). Die Funktion kann auch in Access-Abfragen angewendet werden.

Die Variante 1 ermittelt den ggT nach Euklids klassischer Methode durch fortgesetzte Subtraktion (langsam, wenn das Verhältnis zwischen den Zahlen groß ist), die Variante 2 und 3 nach dem Divisionsalgorithmus (schnell).

VBA-Quelltext

Function GGT1(a As Long, b As Long) As Long
While a <> b
If a > b Then
a = a - b
Else
b = b - a
End If
Loop While a <> b
GGT1 = a
End Function

Function GGT2(ByVal a As Long, ByVal b As Long) As Long
While (a > 0) And (b > 0) ' Abbruch, sobald a*b <= 0
If a > b Then ' Der größere Wert wird überschrieben
a = a Mod b
Else
b = b Mod a
End If
Wend
GGT2 = a + b ' Ein Summand ist sicher 0
End Function

Public Function ggT3(A, B) As Long
Dim Rest As Long, TempA As Long, TempB As Long

' Fehlerprüfung
If IsNull(A) Or IsNull(B) Then Exit Function
If (A = 0) Or (A <> Int(A)) Then Exit Function
If (B = 0) Or (B <> Int(B)) Then Exit Function

ggT3 = 1
TempA = Abs(A)
TempB = Abs(B)

Do
Rest = TempA Mod TempB
TempA = TempB
TempB = Rest
Loop While (Rest <> 0)

ggT3 = TempA
End Function

Argumente der Funktion/Prozedur

A: Beliebige positive Ganzzahl
B: Beliebige positive Ganzzahl

Für den Algorithmus ist es ist egal, welche der beiden Zahlen größer ist. Die längsten Rechenzeiten ergeben sich für Version 2 und 3 bei benachbarten Fibonacci-Zahlen

Rückgabewert

Der größte gemeinsamer Teiler wird zurückgegeben.

Falls eine der beiden Eingaben Null oder keine Ganzzahl war, wird 1 zurückgegeben.

Hinweis

Mit Hilfe dieser Funktion kann auch das kleinste gemeinsame Vielfache (kgV) aus zwei Zahlen a und b berechnet werden:

kgV(a,b) = a × b / ggt(a,b)

Zeitkomplexität: Man kann zeigen, dass die schnelle Implementation des Euklidischen Algorithmus (Division und Modulo-Funktion statt Subtraktion) aus ganzen Zahlen a und b nach spätestens n Schritten n <= 2* log₂(max(a, b)) den ggT(a, b) liefert.

Anwendungsgebiete, Fehler und Warnungen

Diese Funktion ist nur für zwei positive ganze Zahlen definiert.