i mod 3 = 0 ; gehts auch schneller?

[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