Feedback

Größter gemeinsamer Teiler (2)

VB - Klemens Nanni April 18, 2011
0 Ratings 0/5

Sprache: VB

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 [b]60% effizientere Berechnung[/b] gegenüber dem "normalen" euklidischen Algorithmus: [b]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)[/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
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 algorithm Algorithmus binär binary bitshift bitweise euclid Euklid gcd gemeinsamer ggt größter Iteration iterativ Mathe Rekursion rekursiv shift Stein steinsche teiler

Alte URL: /snippet/groesster-gemeinsamer-teiler-2/1524

2 Kommentare

  1. 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.

    [code]
    Dim b As Boolean
    b = 1 ‚ True
    b = 0 ‚ False
    b = Not 1 ‚ True
    b = Not 0 ‚ True
    [/code]