Feedback
dotnet-snippets.de

VB - Binäre Exponentation

Veröffentlicht von am 3/16/2011
(0 Bewertungen)
Die binäre Exponentation ist ein Verfahren zur Rechenoptimierung von Potenzen. Sie reduziert die Anzahl an benötigten Multiplikationen.

Beispiel: 17^9 - Um diesen Ausdruck zu berechnen, benötigen Sie 8 Multiplikationen. Formen Sie in jedoch um, ist es auch mit weniger möglich:
17^9 = 17(17^4)² = 17[(17²)²]²

Sollten sich Ausdrücke innerhalb der Terme wiederholen, können diese in Variablen zwischengespeichert werden, um die Häufung selbiger Op. zu vermeiden.
Function BinExp(ByVal base As Integer, ByVal exp As Integer) As Long
    BinExp = base

    For Each d As Char In Convert.ToString(exp, 2).Remove(0, 1)
        If d = "0" Then BinExp *= BinExp Else BinExp *= BinExp * base
    Next
End Function
Abgelegt unter binär, binary, exp, exponent, exponentation, math, mathe, basis, base.

2 Kommentare zum Snippet

Scavanger schrieb am 3/16/2011:
Hallo,

erstmal sorry, wenn ich schon wieder an deinem Code was aus zusetzen habe...

Zuerst hat sich ein Tippfehler in der zweiten eingeschlichen: 
Dim r As Integer = base


Als Datentypen würde ich ich long vorschlagen, sonst haut dir VB gleich bei bei deinem Beispiel oben (17 ^ 9) eine Overflow Exception um die Ohren.

Ansonsten eine recht "kreative" Lösung des Problems, aber die Lösung per Convert.ToString Überladung finde ich unschön, außerdem verlangsamt die Umwandlung in einen String die Ausführung um das ca. 1,5 - 2 fache.
Schöner gehts mit etwas modularer Arithmetik, hier mal die klassische Implementation:
Function BinExp(ByVal b As Long, ByVal e As Long) As Long
        Dim r As Long = 1
        While (e > 0)
            If (e Mod 2) = 1 Then
                r *= r * b
            Else
                r *= r
            End If
            e /= 2
        End While
        Return r
    End Function



Das lässt sich schöner per
Klemens Nanni schrieb am 3/16/2011:
Der mathem. Weg macht durchaus Sinn, aber wollte ich hier den Fokus auf der Exponentation an sich belassen.
Wählt man ihn doch, empfiehlt sich, das "/= 2" durch ">>= 1" und "mod 2 = 0" durch "& 1" ersetzen. Bitweise Operatoren bringen nochmal einen kleinen Temposchub.
 

Logge dich ein, um hier zu kommentieren!

Ähnliche Snippets

Suche

Letzte Kommentare