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

[Euklid]

Womit wir dann bei der von EugenE beschriebenen MPArith-Unit sind, die entgegen der Angaben keine statischen Arrays verwenden, sondern genau das, was Du hier vorschlägst.

Die Angaben stammen ohne Zweifel von mir.
Möglicherweise interpretiere ich diese Zeilen aus mp_types.pas hier falsch(?):

Code: Alles auswählen

 
const
  MAXDigits = 32000;              {max number of mp_int digits   }
type
  TDigitArray = packed array[0..MaxDigits+63] of mp_digit;

Aber egal ob statisch oder nicht, der Autor fragt die Werte generell über Pointer ab, was die Sache wieder effektiv macht - denn vermutlich muss so nicht das komplette Array in den Cache geladen werden, sondern nur das gerade benötigte Digit. Die verwendeten Typen erlauben wahrscheinlich eine effektivere Arithmetik, da setlength durch eine Wertzuweisung ersetzt werden kann.

[Euklid]

Verstehe ich nicht. Fourier-Transformation ist eine Sache von kontinuierlichen Größen (real- oder Komplex). Du willst diskrete (integer) Größen berechnen.

Ähnliches dachte ich auch, als ich davon gelesen habe. Aber es scheint zu gehen:

http://de.wikipedia.org/wiki/Sch%C3%B6n ... lgorithmus" onclick="window.open(this.href);return false;

Habe mir noch nicht die Mühe gemacht, den Algorithmus nachzuvollziehen.

Multiplikationen und Additionen brauchen meist (bis zu einer gewissen Sättigung) überhaupt keine Zyklen, weil sie im Hintergrund ausgeführt werden

Ah ok, interessant.

Ich glaube nicht, dass ein nicht-rekursiver Algorithmus wesentlich effektiver sein muss, wenn der Rekursive gut geschrieben ist.

Ich dachte daran, dass bei Funktionsaufruf die Register gerettet werden müssen, u.s.w. und rekursive Programmierung deshalb langsamer sein könnte, weil sie eine Unmenge an Aufrufen auslöst.

Wenn Du eine Variante der Komponente mit konstantem GlobZahlenbasis (=32, optional =64) hast, könnten wir das 'mal versuchen.

Gerne. Danke für die angebotene Unterstützung bzgl. ASM. Am Besten werde ich hier mal eine Liste an Optimierungen veröffentlichen und die dann nach und nach abarbeiten. Ich kann zur Zeit noch nicht sagen, wann genau ich die umsetzen kann. Insbesondere wenn der GNZTyp neu definiert und umstrukturiert werden sollte, ist es wahrscheinlich besser, die Umsetzung noch abzuwarten, bevor wir die ASM-Optimierungen durchführen.

Viele Grüße, Euklid

[indianer-frank]

Womit wir dann bei der von EugenE beschriebenen MPArith-Unit sind, die entgegen der Angaben keine statischen Arrays verwenden, sondern genau das, was Du hier vorschlägst.

Die Angaben stammen ohne Zweifel von mir.
Möglicherweise interpretiere ich diese Zeilen aus mp_types.pas hier falsch(?):

const
MAXDigits = 32000; {max number of mp_int digits }
type
TDigitArray = packed array[0..MaxDigits+63] of mp_digit;[/code]

Mit Sicherheit, denn es geht wie folgt weiter:

Code: Alles auswählen

type
  mp_int    = record                   {MP integer number           }
                pdigits : PDigitArray; {pointer to digit array      }
                alloc   : word;        {allocated digits in pdigits }
                used    : word;        {used digits in pdigits      }
                sign    : word;        {sign: MP_ZPOS or MP_NEG     }
                magic   : word;        {set to MP_MAGIC by mp_init  }
              end;

Aber egal ob statisch oder nicht, der Autor fragt die Werte generell über Pointer ab, was die Sache wieder effektiv macht - denn vermutlich muss so nicht das komplette Array in den Cache geladen werden, sondern nur das gerade benötigte Digit. Die verwendeten Typen erlauben wahrscheinlich eine effektivere Arithmetik, da setlength durch eine Wertzuweisung ersetzt werden kann.

Nein, da der Speicher nicht statisch ist, wird er via mp_grow und letztendlich ReallocMem auf die benötigte Größe erweitert; allerdings mit einer Granularität, die über mp_set_allocprec optimierbar ist.

Frank

[Euklid]

Ok, danke für die Richtigstellung.

[mschnell]

http://de.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen-Algorithmus

Icvh denke, das hat wenig mit dem zu tun, was man im Allgemeinen unter Fourier-Transformation versteht. Es werden nur zur Überführung des primitiven Multiplikations-Algorithmus (im Prinzip einer Summe von Produkten) in den Schönhage-Strassen-Algorithmus ähnliche Methoden verwand wie bei der Überführung des einfachen DFT-Algorithmus (Summe von Produkten) in den FFT-Algorithmus.

-Michael

[mschnell]

Überlegungen zur "FFT-Multiplikation".
Ich vermute es hängt so zusammen:
Die mathematische Operation eines Signal-Filters ist eine "Faltung" zweier Funktionen. Das ist ein Integral über ein Produkt bestimmter Funktionen. Die digitale Berechnung einer Faltung ist somit eine Summe von Produkten. Bei n Sampels entstehen dabei n Ergebnisse, die jeweils eine Summe von n Produkten sind. Also O(n²) Operationen: Für jedes Ergebnis-Sampel werden alle Sampels der Ur-Funktionen mit einander in Beziehung gesetzt.
Eine Faltung kann man auch durch die Fourier-Transformation des Produktes der Fourier-Transformierten der Funktionen berechnen. Die Digitale Fourier-Transformation (DFT) benötigt ebenfalls O(n²) Operationen (die Formel zur Berechnung der Fourier-Transformierten ist der zur Faltung sehr ähnlich), die Komplexität bleibt also gleich wie bei der direkten Berechnung.
Wenn n aber eine Zweierpotenz ist, kann statt der "primitiven" DFT auch der FFT-Algorithmus verwendet werden, der exakt dasselbe Ergebnis liefert, aber nur eine Komplexität von O( n * log(n) ) aufweist. Hierdurch wird auch die Komplexität der digitalen Faltung zu O( n * log(n) ).

Auch bei der Multiplikation von Langzahlen muss - wie bei der digitalen Faltung - für jede Ergebnis-Stelle eine Summe des Produktes aller Stellen der Faktoren berechnet werden: Komplexität O(n²). Das ist dieselbe Operation wie eine digitale Faltung. Entspechend lassen sich wohl dieselben Umwandlungen durchführen um die Komplexität auf O( n * log(n) ) zu bringen.

Der DFT/FFT Algorithmus verwendet permanent sinus und cosinus (DFT wird zu FFT durch Ausnutzung der Beziehung sin²+cos²=1, wodurch jede Menge der Summanden sich auslöschen). Wie man bei Ganzen Zahlen sinnvoll mit Sinus arbeitet ist mir allerdings schleierhaft .

-Michael

[mschnell]

Euklid:
Dein Haupt-Augenmerk liegt anscheinend auf der Multiplikation von Langzahlen. Dazu folgende Überlegungen:

- Zur Optimierung des internen Handlings sollte die Größe des Basis-Elements zur Compile-Zeit festliegen und je nach Prozessor 32 oder 64 Bit betragen. Entsprechen ist der Type des Basis-Elements entweder ein vorzeichenloser 32 Bit Integer oder ein vorzeichenloser 64 Bit Integer. Dann tritt die Größe des Basis-Elements bei den Berechnungen vermutlich überhaupt nicht mehr auf.

- Ich glaube, dass es nicht verkehrt ist als Langzahlen-Typ bei dynamischen Arrays von Basistyp-Elementen zu bleiben. Das Interface der Langzahlen-Unit nach außen wird sonst recht unübersichtlich.

- Das Interface der Langzahlen-Unit nach außen sollte also die Grundfunktionen wie LongAdd und LongMult mit dynamischen Arrays zur Verfügung stellen. Da die Karatsuba-Multiplikation aber Funktionen auf Teil-Arrays ausführt, sollte intern mit Zeigern (Var-Parametern) gearbeitet werden. Hier würde ein Funktions-Aufruf rein mit dynamischen Arrays ein Kopieren das Arrays erfordern.
Ein zusätzlicher Funktions-Aufruf bei externen Lang-Operationen macht nichts an der Performance aus. Die Funktion LongAdd sieht dann z.B. so aus

Code: Alles auswählen

procedure LongAddInternal(var Summe, Summand1, Summand2: LongNumberBaseType; Length: Integer);
begin
  ...
end;
 
procedure LongAdd(Summe, Summand1, Summand2: LongNumber); // dynamic arrays are passed by reference anyway
begin;  
  LongAddInternal(Summe[0], Summand1[0], Summand2[0], length(Summand1)); 
end;

die Karatsuba-Multiplikation ist dann:

Code: Alles auswählen

procedure LongMultInternal(var Produkt, Faktor1, Faktor2: LongNumberBaseType; Length: Integer);

und die primitive Multiplikation ist

Code: Alles auswählen

procedure LongMultInternalPrimitive(var Produkt, Faktor1, Faktor2: LongNumberBaseType; Length: Integer);

- Ich glaube nicht dass es schadet Karatsuba als rekursiv zu belassen

- Karatsuba kann nun alternativ (aber mit gleichen Parametern) sich selbst oder LongMultInternalPrimitive aufrufen.

- Karatsuba benötigt neben der Multiplikation noch die Addition und (wenn ich das richtig sehe) die Operation z := a - b - c; und z := a + b + c;. Addition ist als LongAddInternal ohnehin vorhanden, die anderen Operationen wären dann

Code: Alles auswählen

procedure LongSubSubInternal(var Summe, s1, s2, s3: LongNumberBaseType; Length: Integer);
procedure LongAddAddInternal(var Summe, s1, s2, s3: LongNumberBaseType; Length: Integer);

- Wenn das läuft kann man sich daranmachen LongAddImnternal, LongSubSubInternal, LongAddAddInternal und schließlich LongMultInternalPrimitive zunächst in der 32 Bit Variante in ASM umzuschreiben und bei entsprechend gesetzter Compiler-Option statt der Pascal-Version zu verwenden. Danach können auch die 64 Bit Assembler Teile in Angriff genommen werden.

Hört sich das sinnvoll an ?

-Michael

[Euklid]

Hallo Michael,

Überlegungen zur "FFT-Multiplikation".

Wir hatten in unserem Studium zwar die Fourier-Transformation, die FFT oder DFT hatten wir jedoch nicht durchgenommen. Wichtiger erscheinen mir zur Zeit die Low-Level-Optimierungen, die du in den vorhergehenden Beiträgen angesprochen hast. Aber trotzdem danke für die Infos. Hört sich an, als hättest du Mathematik studiert? Oder zumindest eine Wissenschaft, in der Mathematik zur Anwendung kommt

Zur Optimierung des internen Handlings sollte die Größe des Basis-Elements zur Compile-Zeit festliegen und je nach Prozessor 32 oder 64 Bit betragen. Entsprechen ist der Type des Basis-Elements entweder ein vorzeichenloser 32 Bit Integer oder ein vorzeichenloser 64 Bit Integer. Dann tritt die Größe des Basis-Elements bei den Berechnungen vermutlich überhaupt nicht mehr auf.

Ja, das ließe sich umsetzen denke ich. Zur Zeit ist das Basiselement bereits ein vorzeichenloses 32Bit-Integer (dword). Nur wird der Überschlag umständlich ausgeführt, hier kommt die Assembler-Optimierung.

Ich glaube, dass es nicht verkehrt ist als Langzahlen-Typ bei dynamischen Arrays von Basistyp-Elementen zu bleiben. Das Interface der Langzahlen-Unit nach außen wird sonst recht unübersichtlich.

Schon möglich. Hinsichtlich dynamischer Arrays gab es das setlength-Problem, welches besonders beim Karazuba-Algorithmus auftritt. Wie könnte eine Lösunge diesbezüglich aussehen?

Das Interface der Langzahlen-Unit nach außen sollte also die Grundfunktionen wie LongAdd und LongMult mit dynamischen Arrays zur Verfügung stellen. Da die Karatsuba-Multiplikation aber Funktionen auf Teil-Arrays ausführt, sollte intern mit Zeigern (Var-Parametern) gearbeitet werden. Hier würde ein Funktions-Aufruf rein mit dynamischen Arrays ein Kopieren das Arrays erfordern.

Zur Zeit sieht die verwendete Karazuba-Funktion ähnlich aus, wie du sie beschreibst:

Code: Alles auswählen

function GNZKarazuba(a,b:GNZTyp;aAnz,bAnz,Laenge:dword):GNZTyp;

Nur wird zusätzlich die Stellenanzahl von a und b, aAnz und bAnz, übertragen. Das erspart ein paar length-Aufrufe.

Die Karazuba-Multiplikation funktioniert also ähnlich, wie du es vorschlägst. Die "normale" Multiplikation sowie die Addition dagegen noch nicht, hier wäre es sinnvoll, folgende, immer wieder auftretende Schleife so wie du es vorschlägst in eine AddInternal auszulagern und in Assembler zu schreiben (siehe unten nochmal detailierter):

Code: Alles auswählen

ZwSp:= a[n] + b[n];   //Addition des LongNumberBaseType (in diesem Fall dword)
      If ZwSp>=GNZ_GlobZahlenbasis then       // GlobZahlenbasis ist 2^32, also gleich der Größe des dword. Hier beginnt also die Berechnung des Überschlags.
      begin
        Erg[n]:= ZwSp-GNZ_GlobZahlenbasis;
        ZwSp:=1;
      end else
      begin
        Erg[n]:=ZwSp;
        ZwSp:=0;
      end;

Die GlobZahlenbasis ist 2^32. Damit könnte man diese Variable durch Verwendung von Assembler einsparen, denn die GlobZahlenbasis erfüllt keinen anderen Sinn als den Überschlag zu berechnen, welcher jedoch über Assembler direkt berechnet werden kann.

Karatsuba benötigt neben der Multiplikation noch die Addition und (wenn ich das richtig sehe) die Operation z := a - b - c; und z := a + b + c;. Addition ist als LongAddInternal ohnehin vorhanden

Ja genau.

die anderen Operationen wären dann

Code: Alles auswählen

procedure LongSubSubInternal(var Summe, s1, s2, s3: LongNumberBaseType; Length: Integer);

Stimme zu.

Wenn das läuft kann man sich daranmachen LongAddImnternal, LongSubSubInternal, LongAddAddInternal und schließlich LongMultInternalPrimitive zunächst in der 32 Bit Variante in ASM umzuschreiben und bei entsprechend gesetzter Compiler-Option statt der Pascal-Version zu verwenden. Danach können auch die 64 Bit Assembler Teile in Angriff genommen werden.

Hört sich das sinnvoll an ?

Auf jeden Fall. Möchtest du mal versuchen, die Prozedur LongAddInternal umzusetzen? Am Besten zunächst für 32bit, also für den Dateityp dword. Dazu müsste der folgende Pascal-Quelltext in Assembler übersetzt werden:

Code: Alles auswählen

procedure LongAddInternal32(var Summe, Ueberschlag, Summand1, Summand2: dword);
begin
  Summe:=Summand1+Summand2;   //(1)
  //Soweit sollte alles klar sein. Nun muss noch der Überschlag berechnet werden. Die Berechnung des Überschlags erfolgt nach deiner Aussage in Assembler gleichzeitig mit (1). In Pascal ist folgender (langsamer!) Quelltext dafür nötig:
  If Summe >2^32 then
  begin
    Ueberschlag:=1;
    Summe:=Summe-2^32;
  end else Ueberschlag:=0;
  //Die Variable Ueberschlag kann also die Werte 0 und 1 annehmen.
end;
 

Ich könnte eine solche Prozedur direkt in die Arithmetik-Unit einbauen. Dadurch würde die GNZ_GlobZahlenbasis hinsichtlich der Addition schonmal wegfallen. Zudem wäre viel Zeit gewonnen.
Anschließend könnten wir diesen Schritt auch für die primitive Multiplikation wagen, wodurch die GNZ_GlobZahlenbasis auch aus den Multiplikations-Routinen verschwinden würden, und so die Gnurz-Unit langsam GlobZahlenbasis-frei wird.


Viele Grüße, Euklid

[mschnell]

Hört sich an, als hättest du Mathematik studiert?

XStimmt ist aber knapp 100 Jahre her. Die FFT habe ich aber in der Mathematik-Vorlesung nicht verstanden. Zum Glück hatte ich Physik als Nebenfach und der Prof konnte es verständlicher darlegen. DFT und FFT habe ich mir damals aus Büchern angelesen.

Ich glaube, dass es nicht verkehrt ist als Langzahlen-Typ bei dynamischen Arrays von Basistyp-Elementen zu bleiben. Das Interface der Langzahlen-Unit nach außen wird sonst recht unübersichtlich.

Hinsichtlich dynamischer Arrays gab es das setlength-Problem, welches besonders beim Karazuba-Algorithmus auftritt. Wie könnte eine Lösunge diesbezüglich aussehen?

(Var-Parameter als Zeiger. Siehe weiter unten im Text. SetLength wird nur einmal für ein Array gemacht. Wenn es nicht mehr gebraucht wird macht man Setlength(x, 0) um den Speicher freizugeben. Bei "Normalen" Funktionen wird die Länge immer gleich sein: passend für die größte mögliche Zahl. Bei Karazuba muss man die Länge des Feldes, in das das Ergebnis kommt, vor dem Aufruf der Basis-Funktionen natürlich geschickt wählen.

Zur Zeit sieht die verwendete Karazuba-Funktion ähnlich aus, wie du sie beschreibst:

Code: Alles auswählen

function GNZKarazuba(a,b:GNZTyp;aAnz,bAnz,Laenge:dword):GNZTyp;

Das ist eben nicht so. Durch einen var-Parameter vom Basis-Element Typ wird ein Zeiger übergeben, der mitten in ein dynamisches Array zeigen kann. Hierdurch ist es im Karazuba-Code möglich, die obere Hälfte des Arrays als Faktor oder Summand an das Unterprogramm zu übergeben.

Code: Alles auswählen

ZwSp:= a[n] + b[n];   //Addition des LongNumberBaseType (in diesem Fall dword)
      If ZwSp>=GNZ_GlobZahlenbasis then       // GlobZahlenbasis ist 2^32, also gleich der Größe des dword. Hier beginnt also die Berechnung des Überschlags.
      begin
        Erg[n]:= ZwSp-GNZ_GlobZahlenbasis;
        ZwSp:=1;
      end else
      begin
        Erg[n]:=ZwSp;
        ZwSp:=0;
      end;

Ganz und gar nicht. (Oder ich verstehe Dich hier falsch.) Sinnvoll ist es, die gesamte Schleife zur Addition zweiter Langzahlen in einer Funktion zu vollziehen und diese dann in ASM zu konvertieren. Nur so kann der Hardawre-Übertrag verwendet werden. Hierzu wird (wie ich es ohnehin auch für eine Pascal-Implementierung für sinnvoll halte) ein Pointer auf das erste zu verwendende Array-Element (low 32 Bit der Langzahl) übergeben. Das geht in Pascal einfach als var-Parameter. In ASM ist das auch leicht handhabbar.

Auf jeden Fall. Möchtest du mal versuchen, die Prozedur LongAddInternal umzusetzen?

Nö, das macht momentan keinen Sinn bevor es nicht als Pacal-Code getestet ist. Zunächst sollte alles entsprechend der neuen Technik (wenn wir uns darauf einigen können) in Pascal laufen. Das ist vermutlich dann wegen der SetLength-Optimierung schon eine nett Beschleunigung. Der ASM-Kram kommt dann oben d'rauf.

-Michael

[Euklid]

XStimmt ist aber knapp 100 Jahre her. Die FFT habe ich aber in der Mathematik-Vorlesung nicht verstanden. Zum Glück hatte ich Physik als Nebenfach

Hattest also auch Physik... ... eine sinnvolle Kombination! Interessiert du dich auch für Astronomie? Bzw. Astrophysik.

SetLength wird nur einmal für ein Array gemacht. Wenn es nicht mehr gebraucht wird macht man Setlength(x, 0) um den Speicher freizugeben.

Letzteres wird soweit ich weiß bei FreePascal nicht gebraucht. Er gibt den Speicher automatisch frei, sobald er nicht mehr gebraucht wird.

Bei Karazuba muss man die Länge des Feldes, in das das Ergebnis kommt, vor dem Aufruf der Basis-Funktionen natürlich geschickt wählen.

Aber sie muss gewählt werden. D.h. pro Aufruf von Karazuba (und das ist bei Rekursion nicht wenig) steckt da mindestens ein setlength pro relevanter Variable.

Durch einen var-Parameter vom Basis-Element Typ wird ein Zeiger übergeben, der mitten in ein dynamisches Array zeigen kann. Hierdurch ist es im Karazuba-Code möglich, die obere Hälfte des Arrays als Faktor oder Summand an das Unterprogramm zu übergeben.

Ok, das könnte in der Tat schneller sein. Wie setzt man einen Pointer inmitten eines Arrays? Durch x:=@zahl[mitte] ? Habe mit Pointern noch nicht sonderlich häufig gearbeitet.

Sinnvoll ist es, die gesamte Schleife zur Addition zweiter Langzahlen in einer Funktion zu vollziehen und diese dann in ASM zu konvertieren. Nur so kann der Hardawre-Übertrag verwendet werden. Hierzu wird (wie ich es ohnehin auch für eine Pascal-Implementierung für sinnvoll halte) ein Pointer auf das erste zu verwendende Array-Element (low 32 Bit der Langzahl) übergeben. Das geht in Pascal einfach als var-Parameter. In ASM ist das auch leicht handhabbar.

Ok, du möchtest den Befehl ADC verwenden. Sag das doch gleich

Das ist vermutlich dann wegen der SetLength-Optimierung schon eine nett Beschleunigung. Der ASM-Kram kommt dann oben d'rauf.

Das kann ich mir vorstellen.

[mschnell]

Astronomie? Bzw. Astrophysik.

Nicht direkt, momentan ist mein größtes Physik-Interesse im Bereich der theoretischen Gefilde wie Relativitäts-Theorie, Machsches Prinzip, Quantentheorie, Stringtheorie und so, vor allem wenn es über das Standard-Modell hinaus-weist. Aber ernsthafte Ahnung habe ich davon nicht.
-Michael

[mschnell]

Letzteres wird soweit ich weiß bei FreePascal nicht gebraucht. Er gibt den Speicher automatisch frei, sobald er nicht mehr gebraucht wird.

Wo hast Du das her ? Dann müssten dynamische Arrays wie Strings Reference-Counting machen. Wäre sicherlich möglich, aber nicht Delphi-kompatibel. Außerdem sollte man die Software möglichst so schreiben, dass sie auch auf Delphi läuft.

Aber sie muss gewählt werden. D.h. pro Aufruf von Karazuba (und das ist bei Rekursion nicht wenig) steckt da mindestens ein setlength pro relevanter Variable.

Klar ! der Speicher für die Variable muss ja irgendwie allokiert werden. Das ist bei jeder Implementierung notwendig.

Wie setzt man einen Pointer inmitten eines Arrays? Durch x:=@zahl[mitte] ?

Vermutlich brauchen wir keinen expliziten Pointer, weil Pascal var-Parameter kann. An das Unterprogramm wird einfach für die untere Hälfte oder die komplette Langzahl an den var-Parameter x[0] übergeben (siehe den Beispiel-Code in der vorigen Mail) und x[mitte] für die obere Hälfte (mitte = length(x) div 2, natürlich nur bei gerader Länge).

Ok, du möchtest den Befehl ADC verwenden.

Na klar, so ist der Befehlscode gedacht. ADC in einer Schleife und Source und Destination Pointer incrementieren. [/quote] Das sind nur ca 8 Zeilen Code.

-Michael

[Euklid]

Nicht direkt, momentan ist mein größtes Physik-Interesse im Bereich der theoretischen Gefilde wie Relativitäts-Theorie, Machsches Prinzip, Quantentheorie, Stringtheorie und so, vor allem wenn es über das Standard-Modell hinaus-weist.

Viele der Dinge haben ja einen Bezug zur Astronomie. Moderne Kosmologie wäre ohne Rel.Theorie nicht denkbar; das Machsche Prinzip wurde ja erst kürzlich wieder kontrovers diskutiert - mithilfe der 3K-Hintergrundstrahlung lässt sich nämlich durchaus eine Relativbewegung unserer Erde über die Rotverschiebung messen. Hier mehr dazu: http://de.wikipedia.org/wiki/Hintergrundstrahlung" onclick="window.open(this.href);return false;

Wo hast Du das her ? Dann müssten dynamische Arrays wie Strings Reference-Counting machen.

Habe ich aus der Dokumentation im Abschnitt über dyn. Arrays. FreePascal zählt tatsächlich die Referenzen. Aber dadurch wird es ja nicht unkompatibel zu Delphi, denn setlength(v,0) funktioniert ja trotzdem.

Na klar, so ist der Befehlscode gedacht. ADC in einer Schleife und Source und Destination Pointer incrementieren. Das sind nur ca 8 Zeilen Code.

Ok, dann wird mir jetzt einiges klarer.


Gruß, Euklid

[mschnell]

OK, es geht in der PAscal-Version anscheinend nicht ohne explizite Pointer (man könnte mit "absolute" arbeiten, aber das ist auch nicht übersichtlicher.

Der Assembler Code ist auch 15 Zeilen geworden und nicht 8, aber immerhin.

Erstmal eine reine 32 Bit-Version:

Kannst Du 'mal testen, wenn Du magst.

-Michael

Code: Alles auswählen

unit asmtest1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, FileUtil, LResources, Forms, Controls, Graphics, Dialogs,
  StdCtrls;
 
type
 
  { TForm1 }
 
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { private declarations }
  public
    { public declarations }
  end; 
 
var
  Form1: TForm1; 
 
implementation
 
Type
  GNZBaseType  = Integer;
  GNZPBaseType = ^GNZBaseType;
  GNZType = array of GNZBaseType;
 
const
  ll = 5;
 
 
{$define asm}
 
{$ifdef asm}
 
{$ifdef fpc}
  {$asmmode intel}
{$endif}
 
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
  xor edi, edi       // edi = 0 and clear carry
@loop:
  mov esi, [edx+edi]
  adc esi, [ecx+edi]
  mov [eax+edi], esi
  lea edi, [edi+4]   //edi = edi + 4 without affecting carry
  dec ebx
  jnz @loop
  pop edi
  pop esi
  pop ebx
end;
 
  {$else}
procedure GNZAddInternal(var s, s1, s2: GNZBaseType; length: Integer);
var
  i:  Integer;
  sp, sp1, sp2: GNZPBaseType;
begin
  sp  := @s;
  sp1 := @s1;
  sp2 := @s2;
  for i := 0 to L - 1 do begin
    sp^ := sp1^ + sp2^;
    // carry handling missing !!!
    inc(sp);
    inc(sp1);
    inc(sp2);
  end;
end;
{$endif}
 
function GNZAdd(s1, s2: GNZType): GNZType;
begin
  setlength(Result, length(s1));
  GNZAddInternal(Result[0], s1[0], s2[0], length(s1));
end;
 
 
{ TForm1 }
 
procedure TForm1.Button1Click(Sender: TObject);
var
  s, s1, s2: GNZType;
  i : Integer;
begin
  SetLength(s1, ll);
  SetLength(s2, ll);
  for i := 0 to ll-1 do begin
    s1[i] := $100+i;
    s2[i] := $1000+$10*i;
  end;
  s1[3] := s1[3] or $FFFFF000;
  s := GNZAdd(s1, s2);
  for i := 0 to ll-1 do begin
    Memo1.Lines.Add(IntToHex(s[i], 8));
  end;
end;
 
initialization
  {$I asmtest1.lrs}
 
end.

[Euklid]

Hallo Michael,

vielen Dank für deine Einsatz!
Für einen ausgiebigen Test möchte ich mir Zeit nehmen und ihn daher erst morgen durchführen.

Viele Grüße, Euklid