i mod 3 = 0 ; gehts auch schneller?

[tn249]

hallo,

kann man i mod 3 = 0 , also eine zahl auf teilbarkeit durch 3 noch schneller berechnen, evtl mit assembler ?

Gruß
Thomas

[Dax]

Öhm.. ne. mod ist schon Assembler, gewissermaßen. Du könntest noch die Quersumme bilden, aber ob das so viel schneller ist, sei dahingestellt

[negaH]

Ja das kann man

p3 = 3^-1 mod 2^32

r == x mod 3


r' == x * 3^-1 mod 2^32 * 3 div 2^32


wenn r = 0 dann r' = 0.

Berechnet wird es so:

3^-1 mod 2^32 = $AAAAAAAB

ergo

r' = x * $AAAAAAAB mod 2^32 * 3 div 2^32

x * $AAAAAAAB mod 2^32 ist nichts anders als IMUL EAX, $AAAAAAAB

* 3 div 2^32 ist nichts anderes als nach dem vorherigen Schritt mit 3 zu multiplizieren und das Resulat aus EDX zu nehmen also die obersten 32 Bits einer 32*32Bit MUltiplikation.

Sähe dann so aus

Delphi-Quellcode:

function InvMulMod2k32(A,B,BInv2k: Cardinal): Cardinal;
asm
    IMUL  EAX,ECX
    MUL   EDX
    MOV   EAX, EDX
end;

if InvMulMod2k32(X, 3, InvMod2k32(3)) = 0 then ;

function InvMod2k32(A: Cardinal): Cardinal;
asm  // 32 Cycles PIV
       MOVZX EDX,AL
       MOV   ECX,EAX
       SHR   EDX,1
       NEG   ECX
       MOVZX EAX,Byte Ptr [@Tab + EDX]
       MOV   EDX,EAX
       IMUL  EAX,ECX
       ADD   EAX,2
       IMUL  EAX,EDX
       MOV   EDX,EAX
       IMUL  EAX,ECX
       ADD   EAX,2
       IMUL  EAX,EDX
       RET
       NOP
@Tab:  DB    001h, 0ABh, 0CDh, 0B7h, 039h, 0A3h, 0C5h, 0EFh
       DB    0F1h, 01Bh, 03Dh, 0A7h, 029h, 013h, 035h, 0DFh
       DB    0E1h, 08Bh, 0ADh, 097h, 019h, 083h, 0A5h, 0CFh
       DB    0D1h, 0FBh, 01Dh, 087h, 009h, 0F3h, 015h, 0BFh
       DB    0C1h, 06Bh, 08Dh, 077h, 0F9h, 063h, 085h, 0AFh
       DB    0B1h, 0DBh, 0FDh, 067h, 0E9h, 0D3h, 0F5h, 09Fh
       DB    0A1h, 04Bh, 06Dh, 057h, 0D9h, 043h, 065h, 08Fh
       DB    091h, 0BBh, 0DDh, 047h, 0C9h, 0B3h, 0D5h, 07Fh
       DB    081h, 02Bh, 04Dh, 037h, 0B9h, 023h, 045h, 06Fh
       DB    071h, 09Bh, 0BDh, 027h, 0A9h, 093h, 0B5h, 05Fh
       DB    061h, 00Bh, 02Dh, 017h, 099h, 003h, 025h, 04Fh
       DB    051h, 07Bh, 09Dh, 007h, 089h, 073h, 095h, 03Fh
       DB    041h, 0EBh, 00Dh, 0F7h, 079h, 0E3h, 005h, 02Fh
       DB    031h, 05Bh, 07Dh, 0E7h, 069h, 053h, 075h, 01Fh
       DB    021h, 0CBh, 0EDh, 0D7h, 059h, 0C3h, 0E5h, 00Fh
       DB    011h, 03Bh, 05Dh, 0C7h, 049h, 033h, 055h, 0FFh
end;

function InvMod2k32(A: Cardinal): Cardinal;
{ Result = A^-1 mod 2^32, A must be odd, 72 cycles PIV }
asm
       MOV   ECX,EAX
       MOV   EDX,EAX
       NEG   ECX
       IMUL  EAX,EDX
       SUB   EAX,2
       IMUL  EAX,ECX
       MOV   EDX,EAX
       IMUL  EAX,ECX
       ADD   EAX,2
       IMUL  EAX,EDX
       MOV   EDX,EAX
       IMUL  EAX,ECX
       ADD   EAX,2
       IMUL  EAX,EDX
       MOV   EDX,EAX
       IMUL  EAX,ECX
       ADD   EAX,2
       IMUL  EAX,EDX
end;

Zwei MULs sind wesentlich schneller als ein DIV. Allerdings sieht man das man das modulare Inverse, eg 3^-1 mod 2^32 nach Möglichkeit als Konstante vorrausberechnen muß.

@DAX: In meinem DECMath findest du ebenfalls diese Sourcen, du hast lange nichts mehr von dir hören lassen ?!

Gruß Hagen

[marabu]

Hallo Thomas,

MOD wird intern durch die sehr teure DIV Operation erledigt. Bei dem Versuch die Teilbarkeit durch 3 ohne Rest durch die deutlich günstigeren Operationen SHR und XOR zu bestimmen muss man sich trotzdem gewaltig anstrengen um einen minimalen Geschwindigkeitsvorteil heraus zu arbeiten. Ich habe zwar gerade keine CPU-Daten für den Pentium IV auf dem Tisch liegen und musste mit den Taktzyklen des 80386 rechnen, aber ich denke, überschlägig wirst du mit MOD nicht schlecht bedient.


Hallo Hagen,

habe beim Schreiben gerade deinen Beitrag entdeckt. Beim 80386 waren DIV und MUL/IMUL etwa gleich teuer. Hat sich das so gravierend geändert, dass zwei IMUL Operationen besser aussehen als eine DIV? Hast du Zahlen?

Freundliche Grüße vom marabu

[DerDan]

Mich würds mal interessieren, wie oft du

if (x mod 3) = 0 then ... rechnen musst damit men weis ob sich optimieren den rentiert.


evtl ist ja auch dein Zahlenumfang von X eingeschränkt.

Die meisten 'Hand' optimierungen funktionieren deshalb weil es Randbedingungen gibt, die man einem Compiler nicht beibringen kann ...


mfg

DerDan

[negaH]

@Marabu:

MUL,IMUL wird in der FPU ausgeführt, daher schneller.

@DerDan:

ich stimme dir zu. Wenn tn249 mal erklären könnte in welchem Kontext er das benötigt so wäre es durchaus möglich mehr "on top" den Algorithmus zu optimieren so das eventuell der mod 3 Test entfallen kann.

Gruß Hagen

[marabu]

Hallo Hagen,

danke für die Information. Erstaunlicher Fortschritt - zu meiner Studienzeit musste man noch floating point Instruktionen verwenden um die FPU zu aktivieren.

marabu

[tn249]

Na dann will ich mal ein paar Infos rausrücken;

Beim Bundesmathewettbewerb 2006 lautet die 1. Aufgabe ungefähr wie folgt:

Man wähle 2 natürliche Zahlen p, q, wobei p + 1 = q und die einfache Quersumme beider Zahlen durch 2006 teilbar sein muss.

Mein erster Ansatz war natürlich mal ein try & error versuch. dh alle zahlen durchprobieren

während das programm dann lief ist mir aufgefallen, dass die kleinste zahl, die die quersumme 2006 haben kann 223 stellen hat und damit weit ausserhalb meines verwendeten typs int64 (würde damit überhaupt die assembleroptimierung funktionieren?) liegt.

ausserdem ist mir aufgefallen, dass die berechnung ca 1 * 10^200 jahre dauern würde, abgabetermin is aber schon in ein paar monaten

dann hab ich mal nach quersummensätzen gesucht und gefunden, dass wenn eine zahl durch 3 teilbar ist auch die quersumme durch 3 teilbar ist -> 2006 ist nicht durch 3 teilbar, also fällt jede zahl raus, die mod 3 = 0 ist.

inzwischen bin ich total von dem versuch abgekommen, das mit nem programm durchlaufen zu lassen, zumindest nichtemhr auf diese art

papier und bleistift sind produktiver



Auch wenn ich den Ansatz vin dir Hagen nicht ganz verstanden hab;

Vielen Dank an eure Mühen, in ner ruhigen Minute werd ich mirs nochmal durchdenken, evtl kann ichs ja wann anders brauchen.

Gruß
Thomas

PS: die aufgabe hab ich gelöst, antwort verrat ich aber nicht =)

[BenjaminH]

Du musst dir nur überlegen, bei welchen Zahlen die Addition von 1 eine Änderung der Quersumme um 2006 hervorrufen kann.
Dann gehts ganz schnell!
Beispiel:
Zahl Quersumme
11 2
12 3
..
In der Mathematik solltest du gezielt probieren und nicht einfach drauflos schießen, du wirst nämlich recht oft daneben treffen...
Mein Lösung hat ca 450 Stellen, dafür hab ich außer der Lösung im Dezimalsystem noch ne Lösung im binär(4013 Stellen) und eine im 2008 er(3 Stellen) system, die beide recht witzig sind.

[GuenterS]

Zitat von tn249:

Na dann will ich mal ein paar Infos rausrücken;

Beim Bundesmathewettbewerb 2006 lautet die 1. Aufgabe ungefähr wie folgt:

Man wähle 2 natürliche Zahlen p, q, wobei p + 1 = q und die einfache Quersumme beider Zahlen durch 2006 teilbar sein muss.

Mein erster Ansatz war natürlich mal ein try & error versuch. dh alle zahlen durchprobieren

während das programm dann lief ist mir aufgefallen, dass die kleinste zahl, die die quersumme 2006 haben kann 223 stellen hat und damit weit ausserhalb meines verwendeten typs int64 (würde damit überhaupt die assembleroptimierung funktionieren?) liegt.

ausserdem ist mir aufgefallen, dass die berechnung ca 1 * 10^200 jahre dauern würde, abgabetermin is aber schon in ein paar monaten

dann hab ich mal nach quersummensätzen gesucht und gefunden, dass wenn eine zahl durch 3 teilbar ist auch die quersumme durch 3 teilbar ist -> 2006 ist nicht durch 3 teilbar, also fällt jede zahl raus, die mod 3 = 0 ist.

inzwischen bin ich total von dem versuch abgekommen, das mit nem programm durchlaufen zu lassen, zumindest nichtemhr auf diese art

papier und bleistift sind produktiver



Auch wenn ich den Ansatz vin dir Hagen nicht ganz verstanden hab;

Vielen Dank an eure Mühen, in ner ruhigen Minute werd ich mirs nochmal durchdenken, evtl kann ichs ja wann anders brauchen.

Gruß
Thomas

PS: die aufgabe hab ich gelöst, antwort verrat ich aber nicht =)

Hm, wie muss man die Aufgabenstellung denn genau verstehen?

Bei p + 1 = q muss da die Quersumme der Summe aus p+1 durch 2006 teilbar sein, oder nur jeweils p und q?