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:
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

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?
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

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.

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!
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
