GNURZ - Arithmetik-Unit für große Zahlen

[indianer-frank]

Normalerweise wird beim Mehrwort-Subtrahieren immer SBB (= subtract with borrow) verwendet. Bist Du sicher, daß zB
sub esi, [ecx+edi]
adc eax, 0
richtig ist? Auf jeden Fall wäre
sbb esi, [ecx+edi]
wohl etwas schneller.

Frank

[mschnell]

Da bin ich allerdings ziemlich sicher. Beim Doppel-Subtrahieren musste ich das Carry-Wort (nicht Bit, hier muss ja ein Übertrag zur nächsten "Stelle" von bis zu 2 gehalten werden, der passt nicht in ein Bit !) positiv halten und dann subtrahieren. (Negativ halten geht nicht, dann muss man bei der nächsten Stelle "add" machen und das gibt den falschen Carry.)

"sbb esi, [ecx+edi]" wäre falsch. Der Carry muss in der nächsten "Stelle" verwendet werden nicht in derselben. Deshalb ist der Code ja so lang.

Porbier's bitte aus !

Ich habe eine Idee, dass man ein Carry bit im Carry-Flag und nur das andere in einem Register halten kann. Das könnte einige Befehle sparen.

-Michael

[Euklid]

Hier die Variante mit vierfachem Loop-Enrolling.

Die Bilanz der Assembler-Optimierungen ist beeindruckend:

Code: Alles auswählen

Laufzeitmessung von: 10.000 Additionen, 50.000-stellige Zahlen
 
Bisherige Routine: 2,196 sec
Assembler-Routine: 0,973 sec (alt)
Assembler-Routine: 0,858 sec (4-fach enrolling)

Danke für die tolle Arbeit! Nehme an, dass sich 4-fach-enrolling insbesondere für sehr große Zahlen lohnt.

Die folgenden Tage werde ich meine Zeit u.a. den folgenden Dingen widmen:
1. Feste Integration der Assembler-Routinen AddInternal in alle Bereichen der GNURZ.
2. High-Level-Optimierung des bisherigen Multiplikations-Algorithmus. (dauert ggf auch länger)
3. Prüfung der mit dem GGZTyp verbundenen Routinen für negative Zahlen.
4. Testen der SubInternal-Routinen sowie deren Integration

Wir haben dann voraussichtlich Mitte kommender Woche eine neue GNURZ-Unit, die nicht unerhebliche Geschwindigkeitsvorteile mit sich bringt und zudem negative Zahlen unterstützt.

Viele Grüße, Euklid

[mschnell]

Die Subtraktion ist ja klar. Ich kann den Code dafür morgen 'mal reinstellen (mit 4-ach enrolling)

Die SubSub-Routine ist hier noch in der Diskussion.

Ich bastele gerade an der primitiv-Multiplikation: in ASM mache ich nur Langzahl * Basistyp, der Überbau wird Pascal)

Freue mich schon auf 64 Bit

-Michael

[mschnell]

Hier die Subtraktion (tivial )

Code: Alles auswählen

procedure GNZSubInternal(var s, s1, s2: GNZBaseType; length: Integer); assembler;
asm
  push ebx           // s, s1 and s2 already are eax, edx and ecx
  push esi
  push edi
  mov  ebx, length
  mov  edi, ebx
  shr  ebx, 2
  and  edi, 3         // clear carry       (finally edi=0).
  jz   @loop
  inc  ebx
  dec  edi
  jz   @l1
  dec  edi
  jz   @l2
  dec  edi
  jz   @l3
@loop:
  mov esi, [edx+edi]
  sbb esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //ebp = ebp + 4 without affecting carry
@l3:
  mov esi, [edx+edi]
  sbb esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //ebp = ebp + 4 without affecting carry
@l2:
  mov esi, [edx+edi]
  sbb esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //ebp = ebp + 4 without affecting carry
@l1:
  mov esi, [edx+edi]
  sbb esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //ebp = ebp + 4 without affecting carry
  dec ebx
  jnz @loop
  pop edi
  pop esi
  pop ebx
end;
 
function GNZSub(s1, s2: GNZType): GNZType;
begin
  setlength(Result, length(s1));
  GNZSubInternal(Result[0], s1[0], s2[0], length(s1));
end;

-Michael

[mschnell]

Hier noch eine Variante der ausgerollten Addition, die sich nur in der Reihenfolge der Befehle von einem vorigen Versuch mit ein-Register-Adressierung unterscheidet.

Hintergrund: Ein beliebtes C-Konstrukt is die autoincrement-Adressierung "*x++". Hierfür haben viele Prozessoren spezielle Befehle mit eingebauter inkrementierung der Adresse. Der X86 hat das nicht (außer bei den unflexiblen und auf neuen Prozessoren vermutlich nicht sehr schnellen "String"-Befehlen). Da die Befehle aber intern in RISC übersetzt werden, könnte es sein dass der Übersetzer in der Lage ist den Speicherzugriff mit anschließendem Increment in einen einzigen RISC befehl übersetzen kann.

Es könnte sich lohnen, die Geschwindigkeit dieser Variante zu testen.

-Michael

Code: Alles auswählen

procedure GNZAddInternal(var s, s1, s2: GNZBaseType; length: Integer); assembler;
asm
  push ebx           // s, s1 and s2 already are eax, edx and ecx
  push esi
  push edi
  mov  ebx, length
  mov  edi, ebx
  shr  ebx, 2
  and  edi, 3         // clear carry       (finally edi=0).
  jz   @loop
  inc  ebx
  dec  edi
  jz   @l1
  dec  edi
  jz   @l2
  dec  edi
  jz   @l3
@loop:
  mov esi, [edx]
  lea edx, [edx+4]   //edx = edx + 4 without affecting carry
  adc esi, [ecx]
  lea ecx, [ecx+4]   //ecx = ecx + 4 without affecting carry
  mov [eax], esi
  lea eax, [eax+4]   //eax = eax + 4 without affecting carry
@l3:
  mov esi, [edx]
  lea edx, [edx+4]   //edx = edx + 4 without affecting carry
  adc esi, [ecx]
  lea ecx, [ecx+4]   //ecx = ecx + 4 without affecting carry
  mov [eax], esi
  lea eax, [eax+4]   //eax = eax + 4 without affecting carry
@l2:
  mov esi, [edx]
  lea edx, [edx+4]   //edx = edx + 4 without affecting carry
  adc esi, [ecx]
  lea ecx, [ecx+4]   //ecx = ecx + 4 without affecting carry
  mov [eax], esi
  lea eax, [eax+4]   //eax = eax + 4 without affecting carry
@l1:
  mov esi, [edx]
  lea edx, [edx+4]   //edx = edx + 4 without affecting carry
  adc esi, [ecx]
  lea ecx, [ecx+4]   //ecx = ecx + 4 without affecting carry
  mov [eax], esi
  lea eax, [eax+4]   //eax = eax + 4 without affecting carry
  dec ebx
  jnz @loop
  pop edi
  pop esi
  pop ebx
end;

[mschnell]

Hier die ASM-Versionen der AddAdd und SubSub Funktionen, die für die Karazuba-Multiplikation sinnvoll sein können.
Euklid könnte testen, ob die schneller sind als zweimal hintereinander Add bzw Sub aufzurufen.

Bei 64 Bit wird das interessanter, da wir keine temporären Speicherzellen brauchen, sondern genügend Register für die Pointer haben. Da kann man auch wieder die ein-Register Adressierung probieren und möglicherweise bringt Loop-Enrolling noch was.

-Michael

Code: Alles auswählen

 
procedure GNZAddAddInternal(var s, s1, s2, s3: GNZBaseType; length: Integer); assembler;
var
  stemp, s1temp: Pointer;
asm                   // s, s1 and s2 are eax, edx and ecx.
  push ebx
  push esi
  push edi
  mov  stemp, eax     // s  -> stemp.
  mov  s1temp, edx    // s1 -> s1temp.
  mov  ebx, length
  xor  edi, edi       // rdi = 0 .
  xor  eax, eax       // carry eax = 0.
 
@loop:                // eax = 0 or 1 or 2 or 3.
  mov  edx, s1temp
  mov  esi, [edx+edi] // s1.
  adc  esi, eax       // add in all carries.
  mov  eax, 0
  adc  eax, eax       // save first carry.
  add  esi, [ecx+edi] // s2.
  adc  eax, 0         // save first and second carry.
  mov  edx, s3
  add  esi, [edx+edi] // 3nd carry !.
  mov  edx, stemp
  mov  [edx+edi], esi
  lea  edi, [edi+4]   //ebp = ebp + 4 without affecting carry
  dec  ebx
  jnz  @loop
  pop  edi
  pop  esi
  pop  ebx
end;
 
 
procedure GNZSubSubInternal(var s, s1, s2, s3: GNZBaseType; length: Integer); assembler;
var
  stemp, s1temp: Pointer;
asm                   // s, s1 and s2 are eax, edx and ecx.
  push ebx
  push esi
  push edi
  mov  stemp, eax     // s  -> stemp.
  mov  s1temp, edx    // s1 -> s1temp.
  mov  ebx, length
  xor  edi, edi       // rdi = 0 .
  xor  eax, eax       // carry eax = 0.
 
@loop:                // eax = 0 or 1 or 2 or 3.
  mov  edx, s1temp
  mov  esi, [edx+edi] // s1.
  sbb  esi, eax       // sub in all carries.
  mov  eax, 0
  adc  eax, eax       // save first carry.
  sub  esi, [ecx+edi] // s2.
  adc  eax, 0         // save first and second carry.
  mov  edx, s3
  sub  esi, [edx+edi] // 3nd carry !.
  mov  edx, stemp
  mov  [edx+edi], esi
  lea  edi, [edi+4]   //ebp = ebp + 4 without affecting carry
  dec  ebx
  jnz  @loop
  pop  edi
  pop  esi
  pop  ebx
end;
 
function GNZAddAdd(s1, s2, s3: GNZType): GNZType;
begin
  setlength(Result, length(s1));
  GNZAddAddInternal(Result[0], s1[0], s2[0], s3[0], length(s1));
end;
 
function GNZSubSub(s1, s2, s3: GNZType): GNZType;
begin
  setlength(Result, length(s1));
  GNZSubSubInternal(Result[0], s1[0], s2[0], s3[0], length(s1));
end;

[EugenE]

Habe mich mal bissel ans testen des GGZTyps gesetzt, nach nen paar einfachen rechnungen +-/* glaube auch mod, verlief es richtig, sobald ich mehr zeit habe mache ich noch nen paar andere tests

Btw: soviel Assembler in diesem Thread und ich verstehe null davon^^

[Euklid]

Hier die ASM-Versionen der AddAdd und SubSub Funktionen, die für die Karazuba-Multiplikation sinnvoll sein können.
Euklid könnte testen, ob die schneller sind als zweimal hintereinander Add bzw Sub aufzurufen.

Werde ich machen! Eine Antibiotika-Allergie hatte mich die vergangenen Tage ein wenig außer Gefecht gesetzt und meine Zeiteinteilung etwas durcheinander geworfen. Dennoch sollte ich den Zeitplan einhalten können und Mitte der kommenden Woche eine erste assembleroptimierte GNURZ-Arithmetikunit supported by michael rausgeben.

Habe mich mal bissel ans testen des GGZTyps gesetzt, nach nen paar einfachen rechnungen +-/* glaube auch mod, verlief es richtig, sobald ich mehr zeit habe mache ich noch nen paar andere tests

Schön, danke. Werde auch ein paar Tests durchführen. Wenn wir bis Mitte kommender Woche keine Unregelmäßigkeiten feststellen, wird die Unterstützung negativer Zahlen Teil der nächsten Version sein. Geht ja ordentlich voran mit der Gnurz.

Viele Grüße, Euklid

[af0815]

Schön, danke. Werde auch ein paar Tests durchführen. Wenn wir bis Mitte kommender Woche keine Unregelmäßigkeiten feststellen, ....

Lohnt sich nicht die Errichtung einer Testumgebung, damit Änderungen immer gegengeprüft werden können. Sprich das man Probleme = falsche Resulate sofort erkennen kann ?

Vorschlag: Einlesen von definierten Zahlen, verarbeiten in der Testumgebung (GNURZ) , Ausgabe in Files und anschliessend mittels diff nachsehen ob die Ergebenisse das sind was man erwartet hat.
Ist zwar einmal ein grösserer Aufwand lohnt sich aber sicherlich. Vor allen können dann schneller alle Änderungen auf den verschiedenen Plattformen auch geprüft werden.

[mschnell]

Das finde ich eine sehr gute idee !

Zudem wäre es natürlich sehr schön, auch auf anderen Plattformen als X86 PC zu testen. (Hierzu müssten dann Compiler-Optionen für die Endian-Behandling eingebaut werden.)

Die Pascal-Versionen der Unterprogramme sollten natürlich immer im Quellcode bleiben und die ASM-arianten nur mit Compiler-Optionen (und natürlich Plattform-spezifisch eingeschaltet werden.

-Michael

[af0815]

Für die Tests ein Einsprung Test your Lazarus/FPC code with FPCUnit. Werde mir das mal ansehen.

[Euklid]

Für die Unit in Version 0.99.3 hatte ich einen Testzyklus geschrieben, der die Grundoperationen (Add, Sub, Mul, Div) an jeweils 10000 Zufallszahlen überprüfte. (Daher bin ich mir bei der 0.99.3 auch so sicher, dass die Grundoperationen weitgehend fehlerfrei sind).

Diesen Test auf sämtliche Funktionen der GNURZ auszuweiten ist keine schlechte Idee; sie wird umgesetzt. Werde mich daran begeben, wenn kommende Woche die neue Version der Gnurz veröffentlicht ist.
Wenn die GNURZ anschließend einen umfangreichen Testzyklus, welcher sämtliche Fälle behandelt, besteht, kann man sie dann aus dem Betastadium rausnehmen und als stabile Version bezeichnen.

Viele Grüße, Euklid

[mschnell]

Hier ein Vorschlag für die Primitiv-Multiplikation. Bitte testen !
-Michael

Code: Alles auswählen

procedure GNZMulInternal(var p, p1: GNZBaseType; p2: GNZBaseType; length: Integer); assembler;
var
  ptemp, p1temp: Pointer;
  p2temp: Cardinal;
 
asm                   // p, p1 and p2 are eax, edx and ecx.
  push ebx
  push esi
  push edi
  mov  ptemp, eax     // p  -> ptemp.
  mov  p1temp, edx    // p1 -> p1temp.
  mov  p2temp, ecx    // p2 -> p2temp.
  mov  ebx, length
  xor  edi, edi       // edi = 0 .
  xor  esi, esi       // carry esi = 0.
 
@loop:
  mov  ecx, p1temp
  mov  eax, [ecx+edi] // p1.
  mul  [p2temp]       // EAX *  [p2temp] -> EDX:EAX.
                      //                     EDX <= $FFFFFFFE.
  mov  ecx, ptemp
  add  eax, [ecx+edi] // p = p + low(p1*p2).
 
                      // This digit          | next digit                    | second next digit.
  adc  edx, 0         //                     | high(p1*p2) + new carry bit   | Carry not possible.
  add  eax, esi       // + old carry word.   | Carry bit possible
  mov  ecx, ptemp
  mov  [ecx+edi], eax // -> p.
  mov  esi, edx       //                     | next carry word.
  adc  esi, 0         //                     | + carry                       | Carry not possble
  lea  edi, [edi+4]   //ebp = ebp + 4 without affecting carry.
  dec  ebx
  jnz  @loop
  mov  ecx, ptemp
//  add  esi, [ecx+edi] // digit n+1 is still = 0 !!! .
  mov  [ecx+edi], esi
 
 
  pop  edi
  pop  esi
  pop  ebx
end;
 
function GNZPrimitivMul(p1, p2: GNZType): GNZType;
var
  l, i:  Integer;
begin
  l := length(p1);
  setlength(Result, l*2);
  for i := 0 to l*2 - 1 do begin
    Result[i] := 0;
  end;
  for i := 0 to l - 1 do begin
    GNZMulInternal(Result[i], p1[0], p2[i], l);
  end;
end;

[EugenE]

Wie wäre es wenn man die größte Länge von beiden: p1, p2 nimmt und nicht nur von p1

Dann hätte ich noch ne frage kommt mir das nurso vor oder wird es da falsch gerechnet?

(den Assembler code nicht mit berücksichtigt)

aber da wird dann ja die zahl : p1[0] = 4; p2[0] = 5; nach Result[0] geschrieben, also ist ja dann Result[0] = 0 und die 2( 20 ) wo kommt die hin?