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

[Christian]

mal ne dumme Frage, warum richtet ihr euch nicht bei Sourceforge ein projekt ein dann könnt ihr über svn beide daran arbeiten ohne den code fehlerträchtig jeder für sich neu zu implementieren ?!

[mschnell]

Ich verstehe nicht, warum mir Showmessage "5705032704=100000*100000" ausgibt.

Anscheinend macht (für zweistellige GNZs) GNZTypToStr(x) nicht dasselbe was inttostr(GNZToIn64(x)) tut.

GNZToIn64 ist so simpel und leicht nachvollziehbar, dass da kaum was falsch sein kann (kann natürlich stark optimiert werden, dass steht aber momentan nicht an, weil es dann besser getestet werden müsste). Inttostr wird doch wohl richtig funktionieren...

Langasm fürchte ich, Du benutzt eine völlig andere Zahlendartellung als ich. Bei mir ist die Darstellung einer Langzahl die einzig mögliche logisch sinnvolle Erweiterung von Byte, Word, DWord, Uint64 auf einer X68 CPU: eine Folge von Bytes mit dem Wert

Langzahl-Wert = Summe (b(i) * 256^i) mit i := 0 ... n-1 mit b(i) = Byte n der Adresse (Langzahl-Start + i)

(Das ergibt bei n=1 Byte, bei n=2 Word, bei n=4 DWord, bei n=8 UInt64, bei n=4*m Langzahl mit Basitsyp DWord, bei n=8*m Langzahl mit Basitsyp UInt64.)

-Michael

[af0815]

mal ne dumme Frage, warum richtet ihr euch nicht bei Sourceforge ein projekt ein dann könnt ihr über svn beide daran arbeiten ohne den code fehlerträchtig jeder für sich neu zu implementieren ?!

Ist an und für sich eingerichtet - nutzen muß man es

Siehe auch hier

[Euklid]

Langasm fürchte ich, Du benutzt eine völlig andere Zahlendartellung als ich.

Völlig anders ist sie nicht. Aber hier könnte das Problem in der Tat liegen:

Bei mir ist die Darstellung einer Langzahl die einzig mögliche logisch sinnvolle Erweiterung von Byte, Word, DWord, Uint64 auf einer X68 CPU: eine Folge von Bytes mit dem Wert

Langzahl-Wert = Summe (b(i) * 256^i) mit i := 0 ... n-1 mit b(i) = Byte n der Adresse (Langzahl-Start + i)

Ist bei mir ähnlich. Genauer:

Code: Alles auswählen

GNZBasisTyp = dword;
  GNZTyp = array of GNZBasisTyp;

D.h. eher:
Langzahl-Wert = Summe (b(i) * (2^32)^i) mit i := 0 ... n-1 mit b(i) = dword n der Adresse (Langzahl-Start + i)

Bei mir ist jede Komponente im Array mit einem dword (=4 byte) besetzt. Ich wählte diese Größe, da bei einer 32bit-CPU ein dword genau in einen Register passt. Ich dachte bisher, deine ASM-Multiplikation sei dafür ausgelegt, da du hier den Pointer stets um 4 erhöhst.

So verschieden sind unsere beiden Darstellungen nicht und ich vermute, es sind nur geringe Anpassungen nötig. Wundert mich, dass die Addition so gut funktioniert.

Wie gehen wir weiter vor?

[mschnell]

Langzahl-Wert = Summe (b(i) * 256^i) mit i := 0 ... n-1 mit b(i) = Byte an der Byte-Adresse (Langzahl-Start + i)

Ist bei mir ähnlich.
Langzahl-Wert = Summe (b(i) * (2^32)^i) mit i := 0 ... n-1 mit b(i) = dword an der DWord Adresse (Langzahl-Start + i)

Das ist genau dasselbe - eben die native Zahldarstellung jeder X86-CPU, da ein DWord eben genau so dargestellt ist:
DWord-Wert = b0 * 256^0 + b1 * 256^1 + b2 * 256^2 + b3 * 256^3 mit bi = Byte an der Byte-Adresse (DWord-Start + i)
und DWord-Adresse = 4*Byte-Adresse ist, und (2^32)^i) = 256^(4*i) ist.

Bei mir ist jede Komponente im Array mit einem dword (=4 byte) besetzt. Ich wählte diese Größe, da bei einer 32bit-CPU ein dword genau in einen Register passt. Ich dachte bisher, deine ASM-Multiplikation sei dafür ausgelegt, da du hier den Pointer stets um 4 erhöhst.

Exakt ! Also müsste es eigentlich passen !

Wie gehen wir weiter vor?

Ich vermute, Deine GNZToIn64 Funktion hat ein Problem. Bitte teste sie, so dass sie bei einer zweistelligen Langzahl dasselbe ausgibt wie IntToStr mit dem UInt64 Wert, der aus den beiden DWords der Langzahl besteht. (Zahl < 2^63, da InttoStr sonst was negatives ausgibt.)

-Michael

[mschnell]

Hier die optimierten Versionen von GNZToIn64 und In64ToGNZ. Wegen der Kompatibilität der Zahldarstellungen von GNZ und UInt64 geht das so einfach.
Aber Vorsicht: zumindest Delphi schneidet die oberen 32 Bit ab, wenn man IntToHex(u) oder IntToStr(u) mit u=UInt64 macht. Mit Int64 ist es OK. (Anscheinend wird bei UInt64 fälschlicherweise die overloaded Variante mit Integer statt der mit Int64 verwendet.) FPC habe ich noch nicht darauf getestet.
-Michael

Code: Alles auswählen

function GNZToIn64(g:GNZType; var i64: UInt64): Integer;
type
  PUInt64 = ^UInt64;
var
  pu: PUInt64;
  i: Integer;
begin
  for i := 2 to Length(g) - 1 do begin
    if g[i] <> 0 then begin
      Result := -1;
      exit;
    end;
  end;
  pu := PUInt64(@g[0]);
  i64 := pu^;
  Result := 0;
end;
 
function In64ToGNZ(i64: UInt64): GNZType;
type
  PUInt64 = ^UInt64;
var
  pu: PUInt64;
begin
  SetLength(Result, 2);
  pu := PUInt64(@Result[0]);
  pu^ := i64;
end;

[Euklid]

Hallo Michael,

hast recht: Meine Umwandlungsroutinen setzen nicht das um, das sie umsetzen sollten. Der Fehler tritt mit meinen alten Funktionen nicht auf, weil diese recht allgemein gehalten sind und auch damit zurecht kommen. Nur die optimierten Assembler-Routinen kommen offenbar nicht damit zurecht. Damit ist das Problem immerhin gefunden und es muss nur noch behoben werden.

Die verwendeten Umwandlungsroutinen sind etwas komplexer als Int64ToGNZ, da sie sich auf den String-Typ beziehen und beliebig lange Zahlen umgewandelt werden können. Aber ich werde mich drum kümmern.

Gruß, Euklid

[mschnell]

Die verwendeten Umwandlungsroutinen sind etwas komplexer als Int64ToGNZ, da sie sich auf den String-Typ beziehen und beliebig lange Zahlen umgewandelt werden können.

Das hatte ich mir gedacht und habe deshalb für meine Tests das simple GNZToInt64 verwendet und mich nicht an einer Umwandlung -> Dezimalziffern versucht.

-Michael

[Euklid]

Habe meine Routine nun angepasst. Bei den ganzen Tests bin ich aber auf die folgende Merkwürdigkeit gestoßen:

Folgende Typendefinitionen:

Code: Alles auswählen

type
 
  GNZBasisType=dword;
  GNZTyp=array of GNZBasisType;

Folgende Testfunktion - verwendet wird die GNZaddinternal mit 4-fach enrolling:

Code: Alles auswählen

procedure TForm1.Button1Click(Sender: TObject);
var s,s1,s2:GNZTyp;
begin
  setlength(s,2);
  setlength(s1,1);
  setlength(s2,1);
  s1[0]:=4294967290;
  s2[0]:=6;
  GNZaddinternal(s[0],s1[0],s2[0],1);
  showmessage(IntToStr(s[1])+'|'+IntToStr(s[0]));
end;

Habe versucht durch diese Funktion alle möglichen Fehlerquellen zu beseitigen, indem ich mich auf das Nötigste beschränke.
Als Ergebnis sollte eigentlich "1|0" aufpoppen, es kommt aber "0|0". Mache ich etwas falsch oder vergisst die Assembler-Routine ein Carry-bit?

Viele Grüße, Alexander

[mschnell]

GNZaddinternal(s[0],s1[0],s2[0],1);

Du gibst Länge 1 an, also Langzahl-Arithmetik mit nur einem DWord. s[1] bleibt deshalb in der Funktion unbearbeitet.

Dein Missverständnis: die ASM "Internal" Funktionen Add, Sub, AddAdd und AddSub gehen von gleichlangen Zahlen in allen Parametern aus. (ASM kennt keine dynamischen Arrays sondern nur einen Pointer auf eine Folge von DWords. Und es ist nur eine Lange angegeben, die für ALLE Paramter gilt. Die ASM-Funktion kann nicht wissen, dass da ein weiteres DWord für einen eventuellen Übertrag oberhalb der letzten Stelle von s angelegt ist.)

-Michael

[Euklid]

GNZaddinternal(s[0],s1[0],s2[0],1);

Du gibst Länge 1 an, also Langzahl-Arithmetik mit nur einem DWord.

Richtig, so hattest du es denke ich vorgesehen, denn length(s1)=1:

Code: Alles auswählen

 
function GNZAdd(s1, s2: GNZType): GNZType;
begin
  setlength(Result, length(s1));
  GNZAddInternal(Result[0], s1[0], s2[0], length(s1));
end;

Würde ich der Internal-Funktion die Länge 2 übergeben, würde sie auf Speicherbereiche zugreifen, die es nicht gibt (hinsichtlich s1,s2).

Dein Missverständnis: die ASM "Internal" Funktionen Add, Sub, AddAdd und AddSub gehen von gleichlangen Zahlen in allen Parametern aus.

Es macht überhaupt keinen Umstand, dass die Internal-Funktionen von gleich langen Parametern in s1 und s2 ausgeht. Zu fordern, dass s die selbe Länge haben soll wie s1 oder s2 halte ich aber für problematisch, da dies nur für Additionen ohne Übertrag gilt und die ASM-Internal-Funktionen für die anderen Fälle unbrauchbar werden.
Das Problem ließe sich dann nämlich nur sehr umständlich lösen - nämlich, indem man vor Verwendung der Internal-Funktionen s1 und s2 um 1 dword erweitert und si[1]=0 setzt und diesen Schritt nach der internal-Addition wieder rückgängig macht, was Zeit kostet.

Vorschlag: Man könnte es bei der bisherigen Regelung belassen, wenn man durch einen zusätzlichen Parameter (z.B. var carry:boolean) das Carry-Flag übergibt. Dann kann weiter length(s)=length(s1)=length(s2) sein, und die Routine, die die Internal-Funktion bedient, kann genau abschätzen, wenn sie nachträglich s um die Länge 1 erweitern und s[1]=1 setzen muss.
Was meinst du?


Viele Grüße, Euklid

[mschnell]

Ich erweitere gleich 'mal die "Add" und "Sub" ASM-Prozeduren zu Funktionen, die den Carry vom obersten Wort der Langzahl als Funktionswert zurückgeben. Dann kann Der Pascal-Teil damit entsprechend verfahren.

Es ist aber nicht unbedingt eine gute Idee bei einer längeren Rechnung mit Langzahlen variabler Länge zu arbeiten. Darüber hatten wir schon gesprochen.
In jedem Fall sollte es eine Variante der (Pascal) "Add" und "Sub"-Funktionen geben, die nicht das Ergebnis zwingend ein Wort größer als die Summenden macht, oder dynamisch (also mit Umkopieren) das Ergebnis je nach Wert verlängert oder verkürzt.

-Michael

[mschnell]

Bitteschön !
-Michael

Code: Alles auswählen

function GNZAddInternal(var s, s1, s2: GNZBaseType; length: Integer): GNZBaseType; 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       (
  jz   @loop
  inc  ebx
  dec  edi
  jz   @l1
  dec  edi
  jz   @l2
  jmp  @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
  mov eax, 0
  adc eax, eax       // carry from highest word
  pop edi
  pop esi
  pop ebx
end;
 
 
 
function GNZSubInternal(var s, s1, s2: GNZBaseType; length: Integer): GNZBaseType; 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
  mov eax, 0
  sbb eax, eax       // carry from highest word
  pop edi
  pop esi
  pop ebx
end;
 
function GNZAdd1(s1, s2: GNZType): GNZType;
var
  c: GNZBaseType;
begin
  setlength(Result, length(s1));
  c := GNZAddInternal(Result[0], s1[0], s2[0], length(s1));
  if c<>0 then begin
    setlength(Result, length(Result)+1);
    Result[High(Result)] := c
  end;
end;
 
function GNZSub1(s1, s2: GNZType): GNZType;
var
  c: GNZBaseType;
begin
  setlength(Result, length(s1));
  c := GNZSubInternal(Result[0], s1[0], s2[0], length(s1));
  if c<>0 then begin
    setlength(Result, length(Result)+1);
    Result[High(Result)] := c
  end;
end;

[mschnell]

Umwandlungsroutinen setzen nicht das um, das sie umsetzen sollten. Der Fehler tritt mit meinen alten Funktionen nicht auf, weil diese recht allgemein gehalten sind und auch damit zurecht kommen. Nur die optimierten Assembler-Routinen kommen offenbar nicht damit zurecht. Damit ist das Problem immerhin gefunden und es muss nur noch behoben werden.

Benutzt Deine Langzahlen zu Dezimal-String Funktion die GNZ-Arithmetik-Funktionen ? Das ist garnicht nötig. Ich habe spaßeshalber 'mal eine Umwandlungsroutine gemacht, die das nicht tut. Sie ist recht simpel, u.U. ist sie aber langsamer.

-Michael

Code: Alles auswählen

function GNZToStr(g: GNZType): String;
var
  w: GNZBaseType;
  i, j, k: Integer;
  b, c: Byte;
begin
  Result := '';
  for k := length(g)-1 downto 0 do begin
    w := g[k];
    for j := 0 to 31 do begin
      c := w shr 31;
      w := w shl 1;
      for i := length(Result) downto 1 do begin
        b := Byte(Result[i]);
        b := 2*b+c;
        if b <= $69 then begin
          b := b-$30;
          c := 0;
         end else begin
          b := b-$3A;
          c := 1;
        end;
        Result[i] := char(b);
      end;
      if c <> 0 then begin
        Result := '1' + Result;
      end;
    end;
  end;
  if Result = '' then begin
    Result := '0';
  end;
end;

[mschnell]

Ich habe übrigens noch 'mal im Internet und in meinem Archiv gewühlt und folgende Implementierungen von Langzahlen-Arithmetik gefunden:



NX - Numerics
=============

NX - Numerics 0.11.0 (alpha)
Copyright (c) 2007, Marcel Martin.
All rights reserved.


Identification
--------------
Name : NX - Numerics
Version : 0.11.0 alpha
Category : Pascal Library
Status : Freeware
Update : September 12, 2007


Description
-----------
NX is a Pascal multiprecision number library.


Web site
--------
http://www.ellipsa.net/index.html







FGInt
=====

This implementation is made by me, Walied Othman, to contact me
mail to rainwolf@submanifold.be or triade@submanifold.be ,
always mention wether it 's about the FGInt or about the 6xs,
preferably in the subject line.
This source code is free, but only to other free software,
it's a two-way street, if you use this code in an application from which
you won't make any money of (e.g. software for the good of mankind)
then go right ahead, I won't stop you, I do demand acknowledgement for
my work. However, if you're using this code in a commercial application,
an application from which you'll make money, then yes, I charge a
license-fee, as described in the license agreement for commercial use, see
the textfile in this zip-file.
If you 're going to use these implementations, let me know, so I ca, put a link
on my page if desired, I 'm always curious as to see where the spawn of my
mind ends up in. If any algorithm is patented in your country, you should
acquire a license before using this software. Modified versions of this
software must contain an acknowledgement of the original author (=me).

This implementation is available at
http://www.submanifold.be

copyright 2000, Walied Othman
This header may not be removed.}