Square & Multiply beschleunigen

[heiliga horsd]

Moin,

Code: Alles auswählen

x = int(input("Basis: "))
k = int(input("Potenz: "))

def to_bin(k):
    return "{0:b}".format(k)

def bin_multiply(x, k):
    result = 1
    for bit in to_bin(k):    
        result = result**2
        if bit == "1":
            result *= x             
    return result

Ich wollte mal fragen, ob man hier mit Mitteln von CPython den "Square and Multiply"-Algorithmus noch ein wenig beschleunigen kann, die Potenzen müssen in meinen Tests schon sehr sehr groß werden, damit ich einen Geschwindigkeitsvorsprung gegenüber "x**k" erhalte. Kann man vielleicht to_bin(k) noch ein wenig "tunen"? Komme ich vielleicht an der if-Bedingung in den Zeilen 11 und 12 irgendwie herum?

Gruß,
heiliga horsd

[lunar]

@heiliga horsd: Eine erste Idee wäre, direkt binäre Operationen anzuwenden, anstatt binäre Operationen über die Zeichenkettendarstellung zu "emulieren".

[heiliga horsd]

Ah, wusste gar nicht, dass man auch

Code: Alles auswählen

return bin(k)

machen kann. War das das, was du meintest? Oder kann man auch direkt mit Binärzahlen rechnen?

Gruß
heiliga horsd

[lunar]

@heiliga horsd: Selbstverständlich kann man direkt binäre Operationen auf Zahlen anwenden. Einfach nur "return bin(k)" zu schreiben, ändern genau gar nichts am Algorithmus, und war keinesfalls das, was ich meinte.

[heiliga horsd]

OK, aber wenn ich das richtig verstanden habe kann ich dann damit nur mit 2^n multiplizieren und/oder dividieren?

[nomnom]

Das wäre meine C-Lösung mit den binären Operatoren (wollte nicht lange nach einer Methode suchen, die Bitreihenfolge zu ändern …), ich denke aber, dass man es auch ungefähr so auf Python übertragen kann.

Edit: Bitreihenfolge ändern war eine schlechte Idee. Der Code funktioniert jetzt nur für Zahlen, deren LSB „1“ ist.

[lunar]

@heiliga horsd: Nein, damit kannst Du alle Zeichenketten-Operationen in Deiner Implementierung ersetzen. Wenn Dir das nicht klar ist, dann lese erst einmal nach, wie binäre Zahlen aussehen, und was man damit alles tun kann. Die entsprechenden Wikipedia-Artikel sind bestimmt ein guter Einstieg.

Anders gesagt, ich habe das Gefühl, dass Dir überhaupt gar nicht klar ist, wie man mit binären Zahlen arbeiten kann, und dann ist die binäre Exponentiation vielleicht nicht unbedingt der richtige Algorithmus für den Einstieg, sondern vielleicht erstmal ein paar Experimente mit den binären Operatoren im interaktiven Interpreter.

[nomnom]

Hab meine C-„Lösung“ mal überarbeitet, sodass sie funktioniert …

[Leonidas]

Hab meine C-„Lösung“ mal überarbeitet, sodass sie funktioniert …

``arpa/inet.h``? Was willst du denn damit? Außerdem werden üblicherweise die Preprocessor-Instruktionen gleich hinter die Rauten geschrieben. Aber gut, bin jetzt auch kein Profi was idiomatischen C-Code angeht.

[nomnom]

``arpa/inet.h``? Was willst du denn damit? Außerdem werden üblicherweise die Preprocessor-Instruktionen gleich hinter die Rauten geschrieben. Aber gut, bin jetzt auch kein Profi was idiomatischen C-Code angeht.

„arpa/inet.h“ beinhaltet die Funktionen zum Umkehren der Bitreihenfolge. Und was die Rauten angeht … hm, es gibt auch Leute, die hinter ihre Rauten Leerzeichen schreiben. (Letzte Version von mir)

[Leonidas]

Seltsam, dann werden die Prototypen bei mir eingebunden selbst wenn man das weglässt. *sigh*

[lunar]

@Leonidas: Sicher, dass das nicht lediglich implizite Deklarationen waren?

@nomnom: Wieso drehst Du da überhaupt die Byte-Reihenfolge um?

[Leonidas]

@Leonidas: Sicher, dass das nicht lediglich implizite Deklarationen waren?

Ja, du hast Recht. Da lässt man einmal ``-Wall`` weg und dann das :-/

[nomnom]

@nomnom: Wieso drehst Du da überhaupt die Byte-Reihenfolge um?

Die dreh ich um, um mittels `& 1' zu überprüfen, ob ein Bit 1 oder 0 ist, und dabei nicht die Reihenfolge zu verdrehen. (Quadrieren → multiplizieren ist was anderes als multiplizieren → quadrieren)

[lunar]

@nomnom: Mir ist schon klar, warum Du bei Deiner Variante die Reihenfolge umkehren musst. Mir ist dagegen nicht klar, warum Du überhaupt diese Variante wählst, anstatt einfach eine Bit-Maske beginnend beim höchstwertigen Bit über "k" zu verschieben. Vielleicht habe ich etwas übersehen, ist schon länger her, dass ich mit Bitschieberei beschäftigt habe, aber ein kurzer Blick auf die Ausgabe meiner Variante sagt mir, dass sie die korrekten Ergebnisse berechnet.

"powl(x, 2)" ist übrigens dasselbe wie "x =<< 1".

[nomnom]

@nomnom: Mir ist schon klar, warum Du bei Deiner Variante die Reihenfolge umkehren musst. Mir ist dagegen nicht klar, warum Du überhaupt diese Variante wählst, anstatt einfach eine Bit-Maske beginnend beim höchstwertigen Bit über "k" zu verschieben.

Der Grund ist, dass ich nicht auf diese Idee gekommen bin.

"powl(x, 2)" ist übrigens dasselbe wie "x =<< 1".

Nicht ganz: `x << 1' ist dasselbe wie `x * 2' (zumindest bei mir?). Das `powl' habe ich in meiner überarbeiteten Fassung übrigens auch durch `x *= x' ersetzt. (Habe mir erlaubt, dein Programm zu korrigieren.)
Bei der Ausführung deines Codes erhalte ich als Ausgabe z. B.:

Code: Alles auswählen

1^2 = 4294967296
1^3 = 4294967296
...
6^11 = 927712935936
6^12 = 154618822656
...
8^11 = 2199023255552
8^12 = 274877906944
...

[lunar]

@nomnom: Stimmt, da hast Du natürlich vollkommen recht. Die richtigen Ergebnisse hatte ich auch nur vor dieser "Verbesserung", mit "res =<< 1" habe ich das gar nicht mehr getestet. Da erhalte ich dann dieselben unsinnigen Ergebnisse. Peinlich

Mit Deiner Korrektur erhalte ich dann allerdings korrekte Ergebnisse, zumindest soweit ich das im Kopf nachrechnen kann Vielen Dank für die Verbesserung

[heiliga horsd]

Hallo,

erstmal vielen Dank für die vielen Antworten!

@lunar: Naja, das mit den binären Zahlen ist schon ne Zeit her Und das rechnen damit fand ich auch nicht sehr ansprechend (Vielleicht war Schieberegister rekonstruieren damals auch einfach zu viel für mich). Aber ich habe mir deinen Rat zu Herzen genommen und mich bei Wikipedia eingelesen; jetzt ist mir auch klar geworden, dass mit AND und OR nicht die bool'schen Vergleiche, wie ich dachte, gemeint waren.

@nomnom: Vielen Dank für dein C-Beispiel! Mir ist leider nicht ganz klar, was

Code: Alles auswählen

k = ntohl(k);

(Zeile 10) an sich macht. Vielleicht könntest du das noch ein wenig näher erläutern. Da du unsigned-Typen verwendest, ist mir auch erst richtig klar geworden, dass das ganze nur für x und k als Element der natürlichen Zahlen definiert ist - Kann man den Algorithmus rein theoretisch auch auf Floats (3^(1/2)) und negative Zahlen (-3^5) erweitern? Hier brauche ich kein Code-Snippet, es würde mich nur interessieren

@all: Ich habe mal mein Coding for Fun Buch raus gekramt; dort wird RSA in Python realisiert und auch einmal der Square & Multiply-Algorithmus angesprochen und verwendet. Hierzu zwei Fragen:

a) Der Autor verwendet keine Strings, sondern prüft mit modulo 2, ob er nun multiplizieren oder nur quadrieren muss. Das ist aber nicht recht viel effektiver als mein (anscheinend nicht so rosiger) Ansatz von oben, oder?
b) Es wird behauptet, man könne das Zwischenergebnis von jedem Durchlauf Modulo n reduzieren, was natürlich bei großen Zahlen enorm Speicher und die Berechnung evtl. schneller macht. Ist das an sich korrekt oder sollte ich da lieber die Finger davon lassen?

Ansonsten: Ich lese mich jetzt mal wieder in das ganze binäre Rechenzeug ein und versuche demnächst/irgendwann mal etwas lauffähiges hier zu posten.


Gruß,
heiliga horsd

[nomnom]

Code: Alles auswählen

k = ntohl(k);

„ntohl“ ist eine Funktion, mit der die Byte-/Bitreihenfolge umgekehrt werden kann. Das Kürzel steht für „network to host long“ („long“ steht bei der Funktion für eine 32-bitige Ganzzahl. Es gibt auch eine Funktion für 16-bitige Ganzzahlen, die heißt „ntohs“ („s“ für „short“)). Über das Internet werden, soweit ich weiß, Daten mit dem Least-Significant-Bit an erster Stelle verschickt, natürliche Zahlen werden aber typischerweise in C andersherum dargestellt, deswegen ist die Funktion auch in „arpa/inet.h“ vorzufinden.

Da du unsigned-Typen verwendest, ist mir auch erst richtig klar geworden, dass das ganze nur für x und k als Element der natürlichen Zahlen definiert ist - Kann man den Algorithmus rein theoretisch auch auf Floats (3^(1/2)) und negative Zahlen (-3^5) erweitern?

Nur der Exponent muss bei der binären Exponentiation natürlich sein. Die Basis darf auch ein Dezimalbruch oder negativ sein. Allerdings hat mein Lösungsansatz da nicht funktioniert. Nur jedes zweite Ergebnis war richtig.

[heiliga horsd]

Aber ich muss es doch gar nicht umdrehen??