Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Ermitteln, ob eine Zahl eine Zweierpotenz ist.
BenBE - Mo 13.12.04 12:00
Titel: Ermitteln, ob eine Zahl eine Zweierpotenz ist.
Dies ist ein Wettbewerb für unsere Optimierungsspezies:
Wie kann man am effektivsten feststellen, ob eine Zahl eine Zweierpotenz ist.
ASM erwünscht, aber nicht notwendig. Ich poste meine bisherige Version sobald die ersten Vorschläge kamen.
Motzi - Mo 13.12.04 12:16
Einfach zählen wieviele einsen die Binär-Darstellung hat - eine Zweierpotenz ist immer nur durch eine einzige 1 darstellbar... das ganze in einen Algo umzusetzen überlass ich aber dir.. ;)
MrSaint - Mo 13.12.04 12:19
Also mir würden auf Anhieb mal zwei Möglichkeiteneinfallen:
Entweder wir teilen die Zahl so lange durch zwei bis mod 2 <> 0 ist oder wir bei zahl = 2 angekommen sind.
Oder genau die Rückrichtung. Wir lassen die Zahl so stehen und fangen an diese mod 2 zu nhemen. Dann mod 2², dann mod 2³ und wenns irgendwann mal <> 0 is, isses keine Zweierpotenz.
MrSaint
EDIT: Oha, da gibts aber schon bessere Lösungen ;) Also nehm ich meinen Vorschlag mal zurück ;)
jasocul - Mo 13.12.04 13:40
Mein Versuch:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| Function IstZweierPotenz(i : Integer) : Boolean; var a : Integer; begin a := 1; while a < i do a:= a shl 1; Result := (a = i); end; |
Wenn man das noch in asm umbaut, dann dürfte das ganz flott sein.
Udontknow - Mo 13.12.04 13:42
Wie liegt denn die Zahl überhaupt vor? Was für Zahlen sind zu erwarten?
Cu,
Udontknow
jasocul - Mo 13.12.04 13:55
Das dürfte schneller sein, als mein erste Variante.
Delphi-Quelltext
1: 2: 3: 4: 5:
| Function IstZweierPotenz(i : Integer) : Boolean; begin while (not Odd(i)) and (i > 1) do i := i shr 1; result := (i = 1); end; |
BenBE - Mo 13.12.04 14:35
Zahlen: Z.Zt. Umgesetzt für DWORD, theoretisch aber beliebige Größe, mit 2^n Bits.
Hab's mal rekursiv gelöst, geht aber noch wesentlich zu optimieren. Erstmal hier nur der versprochene Vorschlag von mir. Bin mal auf eure Verbesserungen gespannt:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35:
| function IsPowerOfTwo(Number:Integer): Boolean;
function BitCount(const Number: DWORD; const Count:Byte): Byte; var Temp1:DWORD; Temp2:DWORD; Mask: DWORD; CntHalf:Byte; Begin If Count = 1 Then Begin Result := Number and 1; Exit; end;
CntHalf := Count shr 1; Mask := 1 shl CntHalf - 1;
Temp1 := Number and Mask; Temp2 := (Number shr CntHalf) and Mask;
If Temp1 <> 0 Then Result := BitCount(Temp1, CntHalf) else Result := 0;
If Result > 1 Then Exit;
If Temp2 <> 0 Then Result := Result + BitCount(Temp2, CntHalf); end;
begin Result := BitCount(Number, 32) = 1; end; |
jasocul - Mo 13.12.04 15:07
Wert testet denn jetzt, was schneller ist?
Übersichtlicher finde ich meins. :wink:
IngoD7 - Mo 13.12.04 15:29
Delphi-Quelltext
1:
| if Frac(Log2(Zahl))=0 then <Zahl ist Zweierpotenz>; |
Motzi - Mo 13.12.04 15:46
jasocul hat folgendes geschrieben: |
Wert testet denn jetzt, was schneller ist?
Übersichtlicher finde ich meins. :wink: |
Also schneller als deine Implementierung gehts wohl nicht mehr.. das ist schon das absolute Minimum (wie raziels Messungen zeigen ;))..!
jasocul - Mo 13.12.04 15:50
@BenBE:
Was hab ich jetzt gewonnen? :dance: :dance2: :beer: 8)
Danke für die Messungen, raziel.
IngoD7 - Mo 13.12.04 16:11
jasocul hat folgendes geschrieben: |
@BenBE:
Was hab ich jetzt gewonnen? :dance: :dance2: :beer: 8)
|
Nix da! :twisted: Wo steht geschrieben, dass Effizienz und Effektivität (hiervon sprach BenBE) immer nur Geschwindigkeit bedeutet??
In der Kürze liegt die Würze. Ich glaube, ich habe gewonnen ... :lol:
jasocul - Mo 13.12.04 16:16
Auf jeden Fall sind unsere Sourcen viel schöner als der von BenBE. Bei seinem muss ich ja nachdenken. :wink:
IngoD7 - Mo 13.12.04 16:18
jasocul hat folgendes geschrieben: |
Auf jeden Fall sind unsere Sourcen viel schöner als der von BenBE. |
Vollkommen einverstanden! :beer: :D
I.MacLeod - Mo 13.12.04 16:29
Dann werf ich doch auch mal meins in die Runde:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| function IsPowerOfTwo(A: DWORD): boolean; asm test eax, eax jz @@end @@loop: shl eax, 1 jo @@testit jmp @@loop @@testit: shl eax, 1 jz @@true xor al, al jmp @@end @@true: mov al, 1 @@end: end; |
Dürfte ganz gut klappen, aber die Geschwindigkeit hab ich nicht überprüft. ;-)
raziel - Mo 13.12.04 16:35
Jo, klappt ganz gut, aber jasocul is immer noch auf Platz 1, dicht gefolgt von I.Macleod ;)
I.MacLeod - Mo 13.12.04 17:50
Gibts einen Extrapreis für Kürze? ;
-)
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| function IsPowerOfTwo(A: DWORD): boolean; asm test eax, eax jz @@end @@loop: shl eax, 1 jno @@loop shl eax, 1 setz al @@end: end; |
14 Bytes :P
//Edit: Ich habe übrigens seltsame Unregelmäßigkeiten festgestellt, wenn ich die selbe Fkt zweimal hintereinander mit dem oben genannten Code teste. (Fast immer hat eine der beiden ein paar Zyklen mehr als die andere)
BenBE - Mo 13.12.04 20:24
Gut, bei den DWORDs geb ich mich geschlagen :D Bleiben noch die von mir erwähnten großen Zahlen von 2^n Bits (Das heißt auch 1KB große Zahlen ;-))
Vorschlag:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32:
| Type TBigNumber = Array of Byte;
Function IsPowerOfTwo(const Number: TBigNumber): Boolean; asm PUSH EDI LEA EDI, DWORD PTR [Number] MOV ECX, DWORD PTR [EDI-$04]
XOR EAX, EAX REPZ SCASB JZ @@FinishFalse
MOVZX EAX, BYTE PTR [EDI-$01]
@@Loop: SHL EAX, 1 JNO @@Loop
SHL EAX, 1 JNZ @@FinishFalse
REPZ SCASB SETZ AL JMP @@Finish
@@FinishFalse: XOR EAX, EAX
@@Finish: POP EDI end; |
Moderiert von Motzi: Delphi-Tags repariert.
Spaceguide - So 09.01.05 21:02
Delphi-Quelltext
1: 2: 3: 4:
| function IsPowerOfTwo(d : dword) : boolean; begin Result := (d>0) and (d and (d - 1) = 0); end; |
Moderiert von Motzi: Delphi-Tags hinzugefügt.
Spaceguide - Do 13.01.05 19:25
Hey, bewundert mal diese Eleganz :)
IngoD7 - Do 13.01.05 20:26
Spaceguide hat folgendes geschrieben: |
Hey, bewundert mal diese Eleganz :) |
Hast du gerade im Baströckchen "Schwanensee" getanzt? Sorry, habe ich verpasst .... :lol:
Oder meinst du deinen Code? Doch, ist ganz nett und leichter zu merken und schwerer zu durchschauen, als mein Vorschlag.
Spaceguide - Do 13.01.05 20:33
... und um einiges performanter :)
zudem darf man = nicht mit fliesskommazahlen verwenden.
BenBE - Fr 14.01.05 00:19
Spaceguide hat folgendes geschrieben: |
Delphi-Quelltext 1: 2: 3: 4:
| function IsPowerOfTwo(d : dword) : boolean; begin Result := (d>0) and (d and (d - 1) = 0); end; |
Moderiert von BenBE: Mod-Tag durch eigenen ersetzt |
Wäre also in ASM:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
| function IsPowerOfTwo(Const Value : DWORD) : Boolean; asm TEST EAX, EAX JZ @@FinishZ
MOV EDX, EAX DEC EDX
TEST EAX, EDX
SETZ AL OR AL, AL @@FinishZ: SETNZ AL end; |
Aber die Grundidee ist cool! Muss man wirklich drauf kommen. Absolutes Lob!
I.MacLeod - Sa 15.01.05 16:30
Wirklich nicht schlecht ;-)
Spaceguide hat folgendes geschrieben: |
zudem darf man = nicht mit fliesskommazahlen verwenden. |
Darf man glaub ich nur nicht mit Fließkommazahlen verschiedener Typen machen. Solange man Extended mit Extended und Real mit Single (*g*) vergleicht ist alles ok.
@BenBE:
Das or al, al würde ich einfach durch ein ret ersetzen, dann sparst du dir das or und noch ein setCC, und letzteres wird IIRC auf P4s ziemlich langsam ausgeführt.
Hier ist meine Variante:
mir ist noch aufgefallen dass AL ja sowieso schon 0 ist wenn der Sprung genommen wird.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
| function IsPowerOfTwo(const Value: DWORD) : Boolean; asm TEST EAX, EAX JZ @@done
MOV EDX, EAX DEC EDX TEST EAX, EDX
SETZ AL @@done: end; |
Ich nehme an die LEA-Variante ist langsamer, aber überprüft hab ichs jetzt nicht.
BenBE - Sa 15.01.05 19:11
I.MacLeod hat folgendes geschrieben: |
@BenBE:
Das or al, al würde ich einfach durch ein ret ersetzen, dann sparst du dir das or und noch ein setCC, und letzteres wird IIRC auf P4s ziemlich langsam ausgeführt. |
I.MacLeod hat folgendes geschrieben: |
Hier ist meine Variante:
mir ist noch aufgefallen dass AL ja sowieso schon 0 ist wenn der Sprung genommen wird. |
Das ist richtig. Hab ich glatt übersehen :D. Hab nur erstmal das übersetzt, wie's der Compiler generieren würde ;-)
I.MacLeod hat folgendes geschrieben: |
Ich nehme an die LEA-Variante ist langsamer, aber überprüft hab ichs jetzt nicht. |
Ne, ganz im Gegenteil, die LEA ist sogar schneller, da du eine Anweisung sparst ... Wenn man ASM-Anweisungen sparen kann, soll mans machen :D
Wäre also die schnellste (bisher gefundene) Variante folgende:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| {$W-} function IsPowerOfTwo(const Value: DWORD) : Boolean; register; assembler; asm TEST EAX, EAX RETZ
LEA EDX, [EAX-1] TEST EAX, EDX SETZ AL end; |
uall@ogc - Sa 15.01.05 19:28
RETZ kennt der delphi compiler net ;> und gibbet auch net
=>
jnz @blub
xor eax, eax
ret
@blub
BenBE - Sa 15.01.05 20:14
Da sind ja Z80-Prozessoren fortschrittlicher :D Die können das nämlich :D
Hieße dann korrigiert:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| function IsPowerOfTwo(const Value: DWORD) : Boolean; register; assembler; asm TEST EAX, EAX JZ @@Done
LEA EDX, [EAX-1] TEST EAX, EDX SETZ AL @@Done: end; |
Naja, kann passieren, wenn man I386 und Z80 mischt :D
AXMD - Sa 15.01.05 20:15
@Ben: du solltest den Delphi-Tag beim Öffnen nicht schließen :lol:
AXMD
I.MacLeod - Sa 15.01.05 21:34
BenBE hat folgendes geschrieben: |
Ne, ganz im Gegenteil, die LEA ist sogar schneller, da du eine Anweisung sparst ... Wenn man ASM-Anweisungen sparen kann, soll mans machen :D |
Nja, nicht unbedingt. Wenn ich zwei "einfache" durch eine "exotische" Anweisung ersetze würde ich mich lieber nicht darauf verlassen, dass es danach schneller ist (Womit ich nicht sagen will dass LEA exotisch ist). :roll:
Zitat: |
Hieße dann korrigiert: |
Kann es sein dass du einfach meine Version nochmal kopiert hast? :P
BenBE - So 16.01.05 00:10
I.MacLeod hat folgendes geschrieben: |
Zitat: | Hieße dann korrigiert: |
Kann es sein dass du einfach meine Version nochmal kopiert hast? :P |
:P Naja, angefangen hab ich, mit ASM, aber stimmt schon, an meiner Version bist Du nicht ganz unschuldig :P
Aber im Grundegenommen würde das Patent auf diese Methode Spaceguide zustehen ;-) Wir haben da nur dran Optimiert :P
grayfox - So 16.01.05 00:24
Zitat: |
RETZ kennt der delphi compiler net ;> und gibbet auch net |
na, dann werd ich dem compiler mal auf die sprünge helfen ;)
--> retz [
http://www.tiscover.at/retz]
BenBE - So 16.01.05 00:49
I.MacLeod hat folgendes geschrieben: |
BenBE hat folgendes geschrieben: | Ne, ganz im Gegenteil, die LEA ist sogar schneller, da du eine Anweisung sparst ... Wenn man ASM-Anweisungen sparen kann, soll mans machen :D |
Nja, nicht unbedingt. Wenn ich zwei "einfache" durch eine "exotische" Anweisung ersetze würde ich mich lieber nicht darauf verlassen, dass es danach schneller ist (Womit ich nicht sagen will dass LEA exotisch ist). :roll:
Zitat: | Hieße dann korrigiert: |
Kann es sein dass du einfach meine Version nochmal kopiert hast? :P |
uall@ogc - Mo 24.01.05 20:15
glaub das problem ist gelöst, da kann unser Benny ja auch mal den thread als bearbeitet/gelöst markieren
BenBE - Mo 24.01.05 22:10
Hab darauf gewartet, dass ein Programmierer mit viel zu viel Freizeit vielleicht noch ne kürzere findet ;-) Aber gut, hab's mal als gelöst markiert :D
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!