heruasfinden ob zahl Gerade oder ungerade ist

[ferby]

Hallo,

gibt es einen befehl oder eine einfache möglichkeit herauszufinden ob eine zahl eine ganze gerade oder ungerade zahl ist?

[FAlter]

Wenn der Rest der Division durch 2 gleich 0 ist, ist die Zahl gerade, ist er 1 (//Edit: oder -1 bei negativen Zahlen), ist sie ungerade.

PS: Darauf könnte man mit NACHDENKEN selber kommen.

[ferby]

Hallo,

wie prüfe ich ob der Rest 0 ist?
Ich weiß das es dazu einen Befehl gibt hab ihn aber vergessen :wall:

[Duffy]

Hallo ferby,
mit

Delphi-Quellcode:

mod

bye
Claus

[Robert_G]

mod ;)

[Nikolas]

Mit Mod

[Tja: wenigstens hab ich noch Bronze geholt :P ]

[Treffnix]

Delphi-Quellcode:

Zahl mod 2

*edit* hoppla! :shock: Aber jedenfalls ist das Ergebnis einstimmig ausgefallen :mrgreen: *edit*

[ferby]

ach ja der wars,


danke

[Chewie]

Oder direkt Odd benutzen.

[Schneider-Huetter]

Die schnellste Methode hierzu ist wahrscheinlich :

Delphi-Quellcode:

if GanzeZahl and 1 = 1 then //ungerade
 else; //gerade

[Stefan Hueg]

Kann ich bestätigen,

Code:

if GanzeZahl and 1 = 1 then //ungerade
else; //gerade

ist wesentlich schneller (doppelt so schnell) wie die Mod-Methode.

[Luckie]

Kann jemand mal in den Sourcen gucken, wie es Odd macht?

[negaH]

Delphi-Quellcode:

if Zahl and 1 <> 0 then ;

entspricht dem Odd, und ist auch das schnellste.

Delphi-Quellcode:

if Zahl and 1 = 1 then ;

beinhaltet in Assembler einen Vergleich eines Registers mit einer Zahl die im Speicher steht, somit wesentlich ineffizienter.

Nutze ODD() dafür ist es da, und auch optimiert.

Delphi-Quellcode:

if Zahl mod 2 <> 0 then ;

ist in fakt identisch wie Odd(), kann also niemals langsammer sein.

Gruß Hagen

PS: Halbwissen ist schlechter als Unwissen.

[himitsu]

@Luckie
das geht wohl nicht ... wenn ich die Deklaration davon suchen laß, dann lande ich in der System.pasund da ist natürlich nicht's zufinden -.-

Aber es wird wohl so aussehn ^^

Delphi-Quellcode:

function Odd(X: Longint): Boolean;
  begin
    Result := Boolean(X and $01);
  end;

[ADD]
@negaH
meines ist schneller ;) (der Vergleich mit 1 ist entfallen)

[EDIT]
sch*** Schreibfehler

[Luckie]

Wieso? Wenn ich die Sourcen habe (Prof oder höher), dann sollte mnan es auch in der System.pas finden.

[Nothine]

Zitat:

Zitat von Luckie

Wieso? Wenn ich die Sourcen habe (Prof oder höher), dann sollte mnan es auch in der System.pas finden.

außer es ist compiler-magic, was in diesem falle wohl zutreffen dürfte...

[negaH]

nein wird es nicht, Odd() ist ein Compiler-Magic und muß direkt im Source anaylsiert werden. In den meisten Fällen wie eben

Delphi-Quellcode:

if Odd(Zahl) then ;

ensteht ein Branch, ein bedingter Sprung in Assembler.

Delphi-Quellcode:

asm
  AND    EAX,1
  JZ     @NichtOdd


@NichtOdd:
end;

Delphi-Quellcode:

if Zahl and 1 = 1 then ;

würde dagegen so aussehen

Delphi-Quellcode:

asm
   AND EAX,1
   CMP EAX,1
   JNE @NichtOdd

@NichtOdd:
end;

Odd() selber wird aber als Magic unterschiedlich nach Assembler umgesetzt, zB.

Delphi-Quellcode:

Result := Odd(Zahl);

würde im besten Falle so aussehen

Delphi-Quellcode:

AND  EAX,1

könnte aber auch so ausehen

Delphi-Quellcode:

AND    EDX, 1
SETNZ  AL

je nach Optimierung des Compiliers und den Vorrausetzung der benutzen Register.

Gruß hagen

[Luckie]

Ui. Schon wieder was gelernt. Danke Hagen.

[negaH]

Zitat:

@negaH
meines ist schneller (der Vergleich mit 1 ist entfallen)

nein ist es nicht,
1.) sagte ich schon das ich niemals bei solchen Boolschen Auswertungen es so schreiben würde

Delphi-Quellcode:

if Flag and 1 = 1 then;
if Flag and $80 = $80 then ;

sondern immer

Delphi-Quellcode:

if Flag and 1 <> 0 then ;
if Flag and $80 <> 0 then ;

weil ich eben weis das das Assemblertechnisch ein großer Unterschied ist, und

2.) vergisst du das du eine externe Funktion nutzt die einen CALL + RET usw. benötigt, Odd() selber benutzt ist ein Compiler-Magic den der Compiler abhängig von den Randbedinungen immer anders in Asssembler umsetzt.Der Compiler wählt dann in jedem Falle den optimlasten und effizientesten Assembler, ganz im Gegensatz zu deiner Funktion. Sie beschränkt in diesem Falle die Wahlfreiheit des Optimierers.

Gruß Hagen

[Stefan Hueg]

Zitat:

Zitat von negaH

Zitat:

@negaH
meines ist schneller (der Vergleich mit 1 ist entfallen)

Gruß Hagen

Doch ist es, habe es bei 100.000.000 Vergleichen getestet, die Variante mit "if Zahl and 1 = 1" ist um den Faktor 2 schneller als die Variante "if Zahl mod 2 = 1".

[negaH]

Wie übersetzt der Compiler

Delphi-Quellcode:

 Zahl mod 2

??

Er übersetzt es direkt in

Delphi-Quellcode:

  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:

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:

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

[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