heruasfinden ob zahl Gerade oder ungerade ist

[negaH]

Wie übersetzt der Compiler

 Zahl mod 2 ??

Er übersetzt es direkt in

  Zahl and 1 so clever ist der Compiler um zu erkennen das 2 eine Potenz von 2 ist, und das auf einem Rechner der ein Binärrechner darstellt ! Allerdings besteht ein klitzekleiner Unterschied !

and ist Vorzeichenlos, mod dagegen nicht, WEIL DU den Boolschen Vergleich zu einem Aithmetischen Zahlenvergleich degradierst ! Du sagst dem Compuiler mit

Delphi-Quellcode:

if Zahl mod 2 = 1 then;
if Zahl and 1 = 1 then;

durch den Vergleich mit = 1, das er zwei Seiten einer Formel Zahlen technisch vergleichen soll, also arithmetisch und nicht boolean. Da mod Vorzeichenbehaftet arbeitet, schätze mal Zahl -> type Integer statt type Cardinal, wird es langsammer.

Aber mit

Code:

if Zahl mod 2 <> 0 then;
if Zahl and 1 <> 0 then;
if Odd(Zahl) then;

relativiert dies sich wieder alles.
1.) es sind die schnelleren Lösungen,schneller als deine
2.) es sind echte Boolsche Auswertungen,und keine Arithmetischen
3.) sie sind alle drei assemblertechnisch identisch

Gruß Hagen

[negaH]

Zitat:

2.) es sind echte Boolsche Auswertungen,und keine Arithmetischen

Warum ist das so ?

Weil es nur zwei Lösungen geben kann, eine TRUE und eine FALSE, wenn man fragt "ist Zahl nicht Null ?"
Jede IF THEN Abfrage die man so optimiert das der Compiler nur ZWEI Antworten liefern kann, bzw. abfragen muß, ist in Assembler am effizientesten zu codieren. Man sollte, wenn es möglich ist, also die IF THEN Bedingungen so umschreiben das daraus eine Boolsche Abfrage wird. In diesem Moment kann der Compiler Code erzeugen der die schon in den CPU Flags gesetzten Flags der vorherigen Vergleiche DIREKT mit bedingten Sprungbefehlen auswerten kann. Somit entfällt im Vergleich zu arithmetischen Abfragen immer ein zusätzlicher CPU Befehl.

Achso, warum aber "nicht Null?" ?
Weil jede Operation auf Intel CPUs, egal ob Addition, Multiplikation, AND, XO, Vergleiche die Flags der CPU so setzt das das Z = ZERO Flag automatisch gesetzt wird. D.h. nach jeder arithmetischen Operation der CPU steht in den Flags schon drinnen ob das Resultat NULL ist. Somit muß man im nächsten Schritt keinen zusätzlichen Vergleich merh durchführen, sondern kann dieses Z Flag direkt mit einem Bedingten Sprungbefehl auswerten.Zb. eben JZ -> Springe wenn Z = 1, oder eben JNZ -> Springe wenn Z = 0. Dies geht NUR mit der Null so.

Gruß Hagen

[Schneider-Huetter]

Mit diesem kleinen Programm kann festgestellt werden, mit welcher Methode man am schnellsten
feststellen kann, ob eine Zahl gerade oder ungerade ist ( mit 1.000.000.000 Schleifendurchläufen).
In der RAR-Datei befinden sich 2 Versionen, die 1. Version im Ordner Variable überprüft eine
Variable (hier mit festem Wert 3). Die 2. Version im Ordner Konstante überprüft den festen Wert 3.

Bei der ersten Version ist Odd() und And 1 <> 0 am schnellsten.
Die MOD Varianten sind hier relativ langsam.

Bei der zweiten Version ist sind alle Methoden gleich schnell, nur Odd() ist ca. um Faktor 1,5 langsamer.
Kann sich das jemand erklären?


wieso erkennt der Compiler nicht, dass alle Varianten eigentlich identisch sind?
Als Assembler-Code könnte er dann ja für alle Varianten sschreiben:

Code:

asm
 AND EAX,1
 JZ @gerade

[Nightshade]

Meine Zeiten :

"Odd" und "AND <>" sind gleich schnell

[Gruber_Hans_12345]

Zitat von negaH:

Aber mit

Code:

if Zahl mod 2 <> 0 then;
if Zahl and 1 <> 0 then;
if Odd(Zahl) then;

relativiert dies sich wieder alles.
3.) sie sind alle drei assemblertechnisch identisch

Gruß Hagen

Bist du sicher ?

Hasb gerade probiert und folgendes rausbekommen :

Code:

if Zahl mod 2 <> 0

wird zu 
and eax, $80000001
jns +$05
dec eax
or eax, -$02
inc eax
test eax, eax

die zwei anderen zu

Code:

test al,$01

entweder keine optimierung beim compiler eingestellt oder es wird anders Übersetzt !

Gruss
Hans

[edit]
Upss ... ganz so einfach ist es doch nicht, hatte die Test mit integer durchgeführt.
Mit cardinal sind wirklich alle drei gleich

[Chewie]

Klar, dass es bei Cardinal schneller geht. Denn der hat kein Vorzeichen, folglich ist die Zahl ungerade, wenn das kleinste Bit 1 ist. Bei vorzeichenbehafteten Zahlen muss man dagegen das Vorzeichen beachten.

[Gruber_Hans_12345]

Zitat von Chewie:

Klar, dass es bei Cardinal schneller geht. Denn der hat kein Vorzeichen, folglich ist die Zahl ungerade, wenn das kleinste Bit 1 ist. Bei vorzeichenbehafteten Zahlen muss man dagegen das Vorzeichen beachten.

Eigentlich nicht !

Da ja nur gefordert ist ob die Zahl gerade ist oder nicht.
und auch bei integer Zahlen die kleiner 0 sind ist das kleinste Bit 1 bei ungeraden Zahlen da spielt das Vorzeichen keine Rolle !

nur mod liefert ja nicht zurück ob gerage/ungerade sonder :

Zahl mod 2 [edit natürlich nur wenn die Zahl ungerade ist, ansonsten 0]
1 für Zahlen > 0
-1 für Zahlen < 0


Gruss
hans

[Chewie]

Ach mist, hab wohl schon zu lange Semesterferien....
Dämliches Zweierkomplement

[negaH]

Tja, da schnappt die MOD-Falle zu. Mathematisch gibt es zwei glasklare Definitionen

MOD -> +-x mod +y == +x mod +y, d.h. das Resultat nimmt immer das Vorzeichen des Dividenten an.
REM -> +-x rem +y == +-x rem +<, d.h. das Resultat nimmt das Vorzeichen des Divisors an.

Leider verhält sich der Delphi MOD Operator eben nicht so wie es in der Mathematik definiert wurde.

Sprich:

-8 mod +7 == -1 mod +7 == 7 -1 == 6 mod 7.
+8 mod -7 == +1 mod -7 == +1 -7 == -6 mod -7.

So wäre es richtig. Somit müsste das Delphi MOD eigentlich REM -> Remainder heissen. Ich kenne eigentlich nur Fortran, Smalltalk, Algol die das richtig handhaben, allerdings enthalten die auch ein REM Äquivalent.

Der Unterschied zwischen REM und MOD definiert sich durch deren Domain. Während REM = Remainder = Rest der Division sich auf arithmetische natürliche Zahlen beschränkt, definiert MOD eigentlich eine Kongruenzklasse, zB. in Modularen Ringen. In solchen Kongruenzklassen bestimmt aber immer der Modulus das Vorzeichen ! Wenn also beim MOD der Modulus positiv ist so muß das Resulat eben auch immer positiv sein. "if X mod 1 <> 0 then" wäre demnach mathematisch absolut korrekt und liefert, da +1 positiv ist, immer ein positives Resulat zurück.
Nun, leider ist es in Delphi nicht an dem, sei es das es an der Intel Architektur liegt, sprich der DIV Assembler Befehl eben eigentlich ein implizites REM durchführt (was ja auch korrekt ist) oder sei es das PASCAL den MOD Operator einfach falsch umsetzt (historisch gesehen).

Gruß Hagen