Seite 2 von 2

Re: Square & Multiply beschleunigen

Verfasst: Montag 5. März 2012, 22:02
von 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.

Re: Square & Multiply beschleunigen

Verfasst: Montag 5. März 2012, 22:07
von nomnom
@heiliga horsd und BlackJack: Das habe ich doch weiter oben schon geschrieben:
nomnom hat 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!

Re: Square & Multiply beschleunigen

Verfasst: Sonntag 11. März 2012, 19:02
von 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?

Re: Square & Multiply beschleunigen

Verfasst: Sonntag 11. März 2012, 19:17
von 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 ;))

Re: Square & Multiply beschleunigen

Verfasst: Sonntag 11. März 2012, 20:08
von heiliga horsd
Naja der C-Snippet ist von dir ;)
Ich hab das mit time.time() gemacht.... gibts da so große Abweichungen?

Re: Square & Multiply beschleunigen

Verfasst: Sonntag 11. März 2012, 20:29
von nomnom
heiliga horsd hat geschrieben: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:
timeit.Timer.timeit.__doc__ hat geschrieben: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.

Re: Square & Multiply beschleunigen

Verfasst: Sonntag 11. März 2012, 20:47
von EyDu
nomnom hat geschrieben: 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.

Re: Square & Multiply beschleunigen

Verfasst: Montag 12. März 2012, 18:35
von heiliga horsd
OK dann mess' ich nochmal mit timeit nach. Und stimmt, das Snippet ist von lunar :oops: Er möge es mir verzeihen :oops:
Was ich mich noch frage: Die Bits um 31 Stellen zu verschieben hat bei mir trotzdem das richtige Ergebnis geliefert - wieso?

Re: Square & Multiply beschleunigen

Verfasst: Montag 12. März 2012, 19:03
von nomnom
heiliga horsd hat geschrieben:OK dann mess' ich nochmal mit timeit nach. Und stimmt, das Snippet ist von lunar :oops: Er möge es mir verzeihen :oops:
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. ;-)

Re: Square & Multiply beschleunigen

Verfasst: Montag 12. März 2012, 19:10
von 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.

Re: Square & Multiply beschleunigen

Verfasst: Dienstag 13. März 2012, 14:34
von heiliga horsd
OK, dann belasse ich es nun dabei und danke euch für eure Hilfsbereitschaft & eure Nerven! :wink:

Gruß
heiliga horsd

Re: Square & Multiply beschleunigen

Verfasst: Dienstag 13. März 2012, 14:37
von lunar
@heiliga horsd: Bitte, und danke für die interessante Diskussion :)