VB - Größter gemeinsamer Teiler (2)

Veröffentlicht von Klemens Nanni am 4/18/2011

(0 Bewertungen)

Nach dem kleinen Fauxpas beim ersten Snippet hier eine andere Implementierung.

Der sog. steinsche Algorithmus kommt ganz mit bitweisen Operatoren aus und bietet somit unter Umsetzung folgender Regeln eine bis zu 60% effizientere Berechnung gegenüber dem "normalen" euklidischen Algorithmus:

1. a und b gerade -> gcd(a, b) = 2gcd(a/2, b/2)
2. a und b ungerade -> gcd(a, b) = gcd([a-b]/2, b)
3. nur a gerade -> gcd(a, b) = gcd(a/2, b)

erstes Snippet: http://dotnet-snippets.de/dns/groesster-gemeinsamer-teiler-SID1361.aspx

Function gcd(ByVal a As Integer, ByVal b As Integer) As Integer
	Dim k As Integer = 0
	While 0 = (a And 1 Or b And 1)
		a >>= 1
		b >>= 1
		k += 1
	End While
		
	Dim t As Integer = If(a And 1, -b, a)
	While Not t = 0
		While Not t And 1
			t >>= 1
		End While
			
		If t > 0 Then a = t Else b = -t
		t = a - b
	End While
		
	Return a << k
End Function

Abgelegt unter größter, gemeinsamer, Teiler, ggT, gcd, iterativ, Iteration, rekursiv, Rekursion, mathe, Euklid, euclid, binär, binary, bitweise, shift, bitshift, Stein, steinsche, Algorithmus, algorithm.

2 Kommentare zum Snippet

Scavanger schrieb am 4/18/2011:

Na, der ggt scheint dir nicht zu liegen. ;)
Auch hier hat sich ein kleiner Fauxpas eingeschlichen, die Bedingung der ersten While-Schleife muss lauten:

While ((a And 1 Or b And 1) = 0)

ansonsten wird eine Endlosschleife erzeugt bis irgendwann
eine OverflowException fliegt.

In Vb kann zwar u.U. ein Integer in ein bool gecastet werden aber nicht in Verbiegung mit Not, das Ergebnis ist dann immer True.


Dim b As Boolean
b = 1 ' True
b = 0 ' False
b = Not 1 ' True
b = Not 0 ' True

Klemens Nanni schrieb am 4/19/2011:

..und wieder das gelernt. (:

Logge dich ein, um hier zu kommentieren!

VB - Größter gemeinsamer Teiler (2)

2 Kommentare zum Snippet

Ähnliche Snippets

Suche

Letzte Kommentare