Das deutsche Python-Forum

lunar hat geschrieben:@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.

lunar hat geschrieben:"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.:

@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

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

„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.

Aber ich muss es doch gar nicht umdrehen??

@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.

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

So, hab heute mal Zeit gefunden und das mit Hilfe des C-Schnipsels von nomnom mal überarbeitet/portiert:
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?

Hm, der Code sieht nach eine Portierung aus, und ich glaube, da ist auch ein Fehler drin.
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 )

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

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.

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.

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?

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.

@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.

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

Gruß
heiliga horsd

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