Square & Multiply beschleunigen

[BlackJack]

@nomnom: Ich verstehe ehrlich gesagt auch nicht warum Du diese Funktion aufrufst!? Wenn man eine Int-Zahl hat, dann ist es völlig egal in welcher Reihenfolge die Bytes im Speicher liegen: ``n & 1`` wird *immer* das niederwertigste Bit isolieren. Gehen wir mal von 32-Bit Long aus: wenn die `ntohl()` die Bytes vertauschen muss, dann isoliert ein folgendes ``n & 1`` dagegen das 24. Bit (Zählung startet mit 0 beim Niederwertigsten). Wenn Network und Native Byte Order gleich sind, dann verhält sich Dein Algorithmus anders als wenn sie nicht gleich sind.

[nomnom]

@heiliga horsd und BlackJack: Das habe ich doch weiter oben schon geschrieben:

Die [Reihenfolge] 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)

Würde die Reihenfolge nicht umgekehrt werden, dann würde das Ergebnis verfälscht.
Edit: Ich habe mich wohl geirrt. Da würde nichts verfälscht werden. Ist ja klar: Bei einer reinen Multiplikation spielt die Reihenfolge keine Rolle. *facepalm* Danke, für den Einwand, BlackJack!

[heiliga horsd]

So, hab heute mal Zeit gefunden und das mit Hilfe des C-Schnipsels von nomnom mal überarbeitet/portiert:

Code: Alles auswählen

def bin_multiply(x, k):
    result = 1
    mask = 1 << 31
    while mask: 
        result *= result 
        if (k & mask):
            result *= x;
        mask >>= 1;            
    return result

Ich hab mir auch mal ein Script geschrieben, um zu messen, wann für welche Basis der Algorithmus schneller ist als das BuiltIn... Ergebnis sieht so aus:

http://pastebin.com/VjP5rbH8

Nunja... Selbe Frage wie am Anfang des Threads: Was kann ich wie unter Verwendung von CPython (3.2.2 unter Linux übrigends) noch schneller machen?

[nomnom]

Hm, der Code sieht nach eine Portierung aus, und ich glaube, da ist auch ein Fehler drin.

Code: Alles auswählen

def bin_multiply(x, k):
    result = 1
    # die Bitshift um 31 Stellen funktioniert nur bei Integern mit <= 32 bits
    mask = 1 << 31
    # ich denke, sowas würde funktionieren:
    # mask = 1 << int(math.log(k, 2))
    while mask:
        result *= result
        if (k & mask): # die Klammern sind unnötig
            result *= x; # das Semikolon ist unnötig
        mask >>= 1;
    return result

PS: Übrigens handelt es sich dabei um Lunars Vorschlag, nicht meinen.

Edit:

Code: Alles auswählen

>>> bin_multiply(2, 2**32)
1

Außerdem sagt timeit, dass 3**475 37,3 Nanosekunden bräuchte, während bin_multiply(3, 475) 24,4 Mikrosekunden brauchen solle. (Ein großer Unterschied )

[heiliga horsd]

Naja der C-Snippet ist von dir
Ich hab das mit time.time() gemacht.... gibts da so große Abweichungen?

[nomnom]

Naja der C-Snippet ist von dir
Ich hab das mit time.time() gemacht.... gibts da so große Abweichungen?

Das Snippet ist von Lunar (ich habe es anders gemacht … (schlechter)) und ja, da gibt’s große Abweichungen. `time.time` misst gerade ein mal sekundengenau, während `timeit` da deutlich genauere Ergebnisse liefert:

To be precise, this executes the setup statement once, and then returns the time it takes to execute the main statement a number of times, as a float measured in seconds.

[EyDu]

und ja, da gibt’s große Abweichungen. `time.time` misst gerade ein mal sekundengenau, während `timeit` da deutlich genauere

Da missinterpretierst du die Dokumentation. Die Einheit von `time.time` ist "Sekunde" nicht dessen Auflösung. Wichtig ist allerdings der Hinweise:

Note that even though the time is always returned as a floating point number, not all systems provide time with a better precision than 1 second.

Das ändert natürlich nichts daran, dass man `timeit` verwenden sollte, da es gerade zum Testen existiert.

[heiliga horsd]

OK dann mess' ich nochmal mit timeit nach. Und stimmt, das Snippet ist von lunar Er möge es mir verzeihen
Was ich mich noch frage: Die Bits um 31 Stellen zu verschieben hat bei mir trotzdem das richtige Ergebnis geliefert - wieso?

[nomnom]

OK dann mess' ich nochmal mit timeit nach. Und stimmt, das Snippet ist von lunar Er möge es mir verzeihen
Was ich mich noch frage: Die Bits um 31 Stellen zu verschieben hat bei mir trotzdem das richtige Ergebnis geliefert - wieso?

Wie ich schon im Code geschrieben habe: Es funktioniert nur bei Exponenten mit weniger als 32 Bits (Zahl mit 32 binären Stellen), was du vermutlich nicht ausprobiert hast, das sind aber auch verdammt große Zahlen.

[lunar]

@heiliga horsd: Keine Sorge, dass tut er Ohne nomnom wäre ich ohnehin gar nicht dazu gekommen, mich damit zu beschäftigen.

Was die Zahlen angeht: Anders als in C hat der Typ für Ganzzahlen in Python keine feste Länge, sondern kann beliebig viele Ganzzahlen aufnehmen. Ab Python 2.7 kannst Du die ".bit_length()" Methode verwenden, um die Länge einer Zahl in Bits zu erhalten. Damit funktioniert es dann auch mit Zahlen, die mehr als 32 Bit lang sind.

[heiliga horsd]

OK, dann belasse ich es nun dabei und danke euch für eure Hilfsbereitschaft & eure Nerven!

Gruß
heiliga horsd

[lunar]

@heiliga horsd: Bitte, und danke für die interessante Diskussion