Feedback

VB - Größter gemeinsamer Teiler (2)

Veröffentlicht von am 18.04.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
GFU-Schulungen  [Anzeige]

VB.NET Komplett

Sie stehen vo der Aufgabe, individuelle Anwendungen für Windows zu schreiben. Hier ist VB.NET die optimale Sprache. Sie erlernt sich recht leicht und passt sich komplett in die .NET Umgebung von Microsoft ein. Nach der Schulung entwickeln Sie anwenderfreundliche Programme in VB.NET . Mit den objektorientierten Modellen in VB.NET erzeugen Sie außerdem wiederverwendbare Komponenten.

VB.NET 2017/2015/2013 Einführung

Das Seminar befähigt Sie zur eigenständigen Entwicklung von anwenderorientierten Programmen in VB.NET, worin auch der Einsatz von Datenbanken enthalten ist.

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

2 Kommentare zum Snippet

Scavanger schrieb am 18.04.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 19.04.2011:
..und wieder das gelernt. (:
 

Logge dich ein, um hier zu kommentieren!