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

Zur Vorstellung von Komponenten und Units für Lazarus

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

Beitragvon mschnell » 30. Nov 2008, 10:07 Re: GNURZ - Arithmetik-Unit für große Zahlen

Euklid hat geschrieben:Die GNURZ-Routinen sind so flexibel, dass sie mit beliebiger Zahlenbasis (Zehnersystem=10, Hexadezimalsystem=16, u.s.w.) rechnen können.

Ist das wirklich sinnvoll ?

Wenn in den Berechnungen immer wieder auf die Zahlenbasis Rücksicht genommen werden muss, kann das die Ausführung ganz erheblich verlangsamen.

Euklid hat geschrieben:Scheint er zu machen. Das würde demnach die lästige Arbeit mit Pointern ersparen :)

Sieht gut aus.

Übrigens ist die Addition ein sehr guter und einfach zu machender Kandidat für AS-Optimierung, (Wenn man von der Zahlenbasis-Geschichte absieht. Es muss ja jedesmal beim nächsten Wort der Übertrag vom vorigen einbezogen werden. Das macht ein entsprechender ASM Befehl hardwaremäßig. man braucht nur eine einzige Addition pro Wort.

(Ob das wirklich viel bringt ist allerdings eine andere Frage, weil es viel länger dauert, die Werte aus dem und ins RAM zu transportieren als die Berechnung. Hier hilft natürlich der Cache, das ist aber wiederum vom ganzen Programm abhängig.)

64 Bit Arithmetik wäre sehr wahrscheinlich deutlich schneller.

-Michael
mschnell
 
Beiträge: 3215
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon Euklid » 30. Nov 2008, 11:24 Re: GNURZ - Arithmetik-Unit für große Zahlen

Auf die "Zahlenbasis-Geschichte" kann ich verzichten, die benötige ich jetzt nicht mehr. Sie erfüllte ihren Zweck, als ich mir noch nicht sicher war, welchen Datentyp ich für das Array des GNZTyp verwende. Durch die Einführung der GlobBasis konnte ich den GNZTyp variieren und der Rest des Programms wurde durch einen einfachen Wechsel der GlobZahlenbasis daran angepasst.

mschnell hat geschrieben:Übrigens ist die Addition ein sehr guter und einfach zu machender Kandidat für AS-Optimierung, (Wenn man von der Zahlenbasis-Geschichte absieht. Es muss ja jedesmal beim nächsten Wort der Übertrag vom vorigen einbezogen werden. Das macht ein entsprechender ASM Befehl hardwaremäßig. man braucht nur eine einzige Addition pro Wort.


Gute Idee - nehme an, das funktioniert, indem eine Overflow-Flag gesetzt wird, die in Assembler abgefragt werden könnte. Gibt es Möglichkeiten, diese Flagge auch mit einem Pascal-Befehl abzufragen? Wäre natürich besonders praktisch.

Die Überlauf-Geschichte wird bisher recht aufwendig geregelt:

Code: Alles auswählen
for n:=0 to aAnz-1 do
    begin
      ZwSp:= ZwSp + a[n] + b[n];
      If ZwSp>=GNZ_GlobZahlenbasis then
      begin
        Erg[n]:= ZwSp-GNZ_GlobZahlenbasis;
        ZwSp:=1;
      end else
      begin
        Erg[n]:=ZwSp;
        ZwSp:=0;
      end;
    end; //for n:=0 to aAnz-1;


Durch Benutzung von Assembler würde nach deiner Ausführung die komplette if-Schleife wegfallen. Wäre also ein beträchtliche Optimierung, die mit kleinem Aufwand möglich wäre. Bei den CPU-Cache-Größen sowie den aktuellen Prefetching-Einheiten dürfte nach meiner Einschätzung der Speicherzugriff nicht bremsen.

64 Bit Arithmetik wäre sehr wahrscheinlich deutlich schneller.


Ja, ganz sicher. Der Code sollte dennoch auch für 32-bit-CPUs kompilierbar sein - die sind einfach noch zu stark verbreitet, um auf eine Unterstützung zu verzichten.
Euklid
 
Beiträge: 2758
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

Beitragvon mschnell » 30. Nov 2008, 12:34 Re: GNURZ - Arithmetik-Unit für große Zahlen

Euklid hat geschrieben:Auf die "Zahlenbasis-Geschichte" kann ich verzichten, die benötige ich jetzt nicht mehr. Sie erfüllte ihren Zweck, als ich mir noch nicht sicher war, welchen Datentyp ich für das Array des GNZTyp verwende. Durch die Einführung der GlobBasis konnte ich den GNZTyp variieren und der Rest des Programms wurde durch einen einfachen Wechsel der GlobZahlenbasis daran angepasst.

Ich meine, es wäre sinnvoll als Zahlenbasis 32 Bit und 64 Bit vorzusehen. Allerdings nicht dynamisch wählbar, sondern als Compiler-Option (z.B. mit könnte mit einer {$if Abfrage "Type GNZBaseType=Integer;" bzw "Type GNZBaseType=Int64;" sowie einige notwendige Konstanten ausgewählt werden, die dann später verwendet werden und an entsprechenden Stellen nörigenfalls wieder wieder {$if Abfragen. Das sollte deutlich optimierten Code erzeugen

Euklid hat geschrieben:Gute Idee - nehme an, das funktioniert, indem eine Overflow-Flag gesetzt wird, die in Assembler abgefragt werden könnte. Gibt es Möglichkeiten, diese Flagge auch mit einem Pascal-Befehl abzufragen? Wäre natürich besonders praktisch.
Nein, in Pascal kann man das nicht anfragen. In ASM braucht man es nicht abfragen weil es einen "Addiere mit Carry"-Befehl gibt, der das automatisch ohne zusätzlichen Instruktionen tut. Übrigens "Abfragen" sollte man zur Geschwindigkeits-Optimierung möglichst vermeiden ! (Bedingte) Sprünge sind die langsamsten Prozessor-Befehle überhaupt.

Euklid hat geschrieben:Die Überlauf-Geschichte wird bisher recht aufwendig geregelt...

Das ist natürlich eine ziemliche Katastrophe für die Laufzeit :) Also sollten wir zunächst 'mal die Addition angehen :). Ich versuche das 'mal, wenn Du eine Version mit statisch definierter Zahlenbasis (32 Bit und 64 Bit) hast.

Euklid hat geschrieben:
64 Bit Arithmetik wäre sehr wahrscheinlich deutlich schneller.
Ja, ganz sicher. Der Code sollte dennoch auch für 32-bit-CPUs kompilierbar sein - die sind einfach noch zu stark verbreitet, um auf eine Unterstützung zu verzichten.


Dazu wird eine {$if - Compiler-Anweisung nötig sein. Vermutlich gibt es eine automatisch gesetzte option, wenn für 64 Bit übersetzt wird.

-Michael
Zuletzt geändert von mschnell am 1. Dez 2008, 11:18, insgesamt 1-mal geändert.
mschnell
 
Beiträge: 3215
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon af0815 » 30. Nov 2008, 12:34 Re: GNURZ - Arithmetik-Unit für große Zahlen

Euklid hat geschrieben:
64 Bit Arithmetik wäre sehr wahrscheinlich deutlich schneller.


Ja, ganz sicher. Der Code sollte dennoch auch für 32-bit-CPUs kompilierbar sein - die sind einfach noch zu stark verbreitet, um auf eine Unterstützung zu verzichten.


mit bedingter Kompilerung sollte es sinnvoll sein, für die Plattformen wo es möglich ist, zu optimieren bzw. die Routinen allgemein zu halten. Dort wo es erst mal möglich ist, das Maximum herauszuholen.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).
af0815
 
Beiträge: 3388
Registriert: 7. Jan 2007, 10:20
Wohnort: Niederösterreich
OS, Lazarus, FPC: Win7/Linux (L stable FPC stable) per fpcup | 
CPU-Target: 32Bit (64Bit)
Nach oben

Beitragvon mschnell » 1. Dez 2008, 11:19 Re: GNURZ - Arithmetik-Unit für große Zahlen

Euklid hat geschrieben:Die Multiplikation ist ein ganz schöner brocken, da sie diverse Fallunterscheidungen macht.

Das hört sich ganz schlecht an ! Wie bereits früher angedeutet: Abweichungen vom linearen Fluss des Codes sind bei modernen Prozessoren fürchrterlich langsame Operationen. Für ein "if" kann dar Prozessor bestimmt zehn Multiplikationen und Addition ausführen. Zusätzlich wird die (Instruction-) Cache-Ausnutzung mit größer werdendem Code schlechter. Hast Du getestet, ob eine "Pennäler"-mäßige Multiplikationsroutine (eine Dezimalstelle entspricht 32 oder 64-Bit Wert) nicht vielleicht doch schneller ist ?

Das könnte vor allem sein wenn die Addition zweier Langzahlen und die Multiplikation einer Langzahl mit einem 32 (oder 64-Bit) Wert mit ASM optimiert ist, um die Behandlung des Übertrags "hardwaremäßig" zu realisieren.

-Michael
mschnell
 
Beiträge: 3215
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon indianer-frank » 1. Dez 2008, 11:42 Re: GNURZ - Arithmetik-Unit für große Zahlen

mschnell hat geschrieben:Das hört sich ganz schlecht an ! Wie bereits früher angedeutet: Abweichungen vom linearen Fluss des Codes sind bei modernen Prozessoren fürchrterlich langsame Operationen. Für ein "if" kann dar Prozessor bestimmt zehn Multiplikationen und Addition ausführen. Zusätzlich wird die (Instruction-) Cache-Ausnutzung mit größer werdendem Code schlechter.

Das ist ein ziemlich naiver Einwand: Eine Karatsuba-Multiplikation ist viele Größenordungen komplizierter als if-Abfragen, außerdem sind die vielen Setlength viel schlechter.
mschnell hat geschrieben:Hast Du getestet, ob eine "Pennäler"-mäßige Multiplikationsroutine (eine Dezimalstelle entspricht 32 oder 64-Bit Wert) nicht vielleicht doch schneller ist ?
Das könnte vor allem sein wenn die Addition zweier Langzahlen und die Multiplikation einer Langzahl mit einem 32 (oder 64-Bit) Wert mit ASM optimiert ist, um die Behandlung des Übertrags "hardwaremäßig" zu realisieren.

Da gibt's nichts zu testen, es sei denn, Du zweifelst an der Realität. "Pennäler"-Multiplikation skaliert mit Länge^2, Karatsuba mit Länge^log2(3) = Länge^1.585. Es kann nur darum gehen, ob GNZ_Karazubagrenze ein wenig größer gemacht wird.

Frank
indianer-frank
 
Beiträge: 130
Registriert: 30. Nov 2008, 21:53

Beitragvon Euklid » 1. Dez 2008, 12:05 Re: GNURZ - Arithmetik-Unit für große Zahlen

mschnell hat geschrieben:Das hört sich ganz schlecht an !


Hinsichtlich der Addition ist es klar, dass der Übertrag in Hardware schneller geregelt werden kann als in Software, dies gilt gewiss auch für die Multiplikation - an dieser Stelle besteht, wie wir schon feststellten, Optimierungsbedarf.

In diesem Fall dienen die if-Abzweigungen der Optimierung des Codes, sie sind also durchaus sinnvoll. In sehr vielen Fällen ist die Geschwindigkeit einer Routine stärker von dem verwendeten Algorithmus abhängig denn von den Hardware-Optimierungen. Hinsichlich der Multiplikation ist z.B. die Schulmethode der schriftlichen Multiplikation für kleine Zahlen unschlagbar schnell. Da hier aber der Rechanaufwand quadratisch mit der Stellenanzahl zunimmt, wird sie für große Zahlen zu langsam. Daher verwendet die GNURZ-Artihmetik ab einer Stellenanzahl von 44 den sogenannten Karazuba-Algorithmus, der mit n^1,6 im Aufwand zunimmt. Dieser wiederum ist besonders für Zahlen mit ähnlicher Stellenanzahl effektiv, d.h. hier muss erneut eine Fallunterscheidung eingeführt werden.
Hier habe ich Messungen durchgeführt, die die Vorteile zeigten. Die Multiplikation zweier hunderttausendstelliger Zahlen wäre nicht im Hundertstelsekundenbereich möglich ohne Karazuba. Ohne Zweifel können weitere Optimierungen auf Hardware-Seite die Berechnung in den ein- bis zweistelligen Millisekundenbereich drücken.
Theoretisch gibt es für sehr große Zahlen eine Methode, die die schnelle Fourier-Transformation benutzt und welche schneller ist als der Karazuba-Algorithmus. Diese wurde noch nicht implementiert.

Wie bereits früher angedeutet: Abweichungen vom linearen Fluss des Codes sind bei modernen Prozessoren fürchrterlich langsame Operationen. Für ein "if" kann dar Prozessor bestimmt zehn Multiplikationen und Addition ausführen.

Naja, bedingte Sprünge brauchen bei heutigen Prozessoren nicht mehr sonderlich viele Zyklen. Aber ich stimme dir zu, dass es dem Prozessor erschwert wird, parallel Befehle abzuarbeiten (was moderne Prozessoren tun), wenn der Code viele Sprünge enthält.

Zusätzlich wird die (Instruction-) Cache-Ausnutzung mit größer werdendem Code schlechter.

Das ist wahr. Bei allen im Laden befindlichen Prozessoren und bei den meisten der aktuell verwendeten Prozessoren dürfte der Instructions-Cache die 64 KB überschreiten. Hier dürften die aktiven Teile des Multiplikationsalgorithmus reinpassen. Man muss bedenken, dass sich die Multiplikation z.B. _nach_ der Entscheidung, per Schulmethode zu multiplizieren, auf einen relativ kleinen iterativen Bereich beschränkt.

Probleme macht der Karazuba-Algorithmus insofern, da mir nur ein rekursiver Algorithmus bekannt ist. Ein iterativer Algorithmus wäre hier effektiver, ich konnte jedoch weder einen finden noch einen herleiten.

Hast Du getestet, ob eine "Pennäler"-mäßige Multiplikationsroutine (eine Dezimalstelle entspricht 32 oder 64-Bit Wert) nicht vielleicht doch schneller ist ?

Ich bin mir nicht sicher, ob ich hier verstanden habe, was du meinst: Aber durch die Setzung der GlobZahlenbasis im Constructor Create wird mit 32bit-Werten pro Stelle gerechnet. Das gilt für alle Routinen.

Das könnte vor allem sein wenn die Addition zweier Langzahlen und die Multiplikation einer Langzahl mit einem 32 (oder 64-Bit) Wert mit ASM optimiert ist, um die Behandlung des Übertrags "hardwaremäßig" zu realisieren.


Zustimmung: Das wären ganz sicher lohnenswerte Optimierungen.



Viele Grüße, Euklid
Euklid
 
Beiträge: 2758
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

Beitragvon Euklid » 1. Dez 2008, 12:29 Re: GNURZ - Arithmetik-Unit für große Zahlen

Hallo Frank,

indianer-frank hat geschrieben:außerdem sind die vielen Setlength viel schlechter.


Der verwendete Karazuba-Algorithmus ist in der Tat mit Setlength-Anweisungen durchsetzt. Das ist sehr ungünstig. Nur weiß ich nicht, wie ich ihn auf der Grundlage eines GNZTyps, der auf dynamische Arrays beruht, in dieser Hinsicht besser schreiben könnte. Zur Zeit ist jedes Setlength unabdingbar. Ein Ausweg würden statische Arrays ergeben, aber sind diese hier wirklich sinnvoll?
Denn: Der L1-Cache teilt sich, wie mschnell schon andeutete, hälftig in einen Cache für Prozessoranweisungen und hälfig in einen Daten-Cache auf. Bei der Verwendung statischer Arrays, die groß sein müssen um die Rechnung mit großen Zahlen zu ermöglichen, bezweifel ich, dass die da alle reinpassen. Die oben zitierte MPUnit verwendet statische Arrays [0..30000] vom Typ Cardinal. Wenn ich mich nicht verrechne, ist der Cache dadurch mit einer einzigen Zahl schon gefüllt, was möglicherweise stärker auf die Laufzeit auswirkt als die setlength, die für einen minimalen Speicherverbrauch sorgen.

Ev. gibt es einen Mittelweg?

indianer-frank hat geschrieben:"Pennäler"-Multiplikation skaliert mit Länge^2, Karatsuba mit Länge^log2(3) = Länge^1.585. Es kann nur darum gehen, ob GNZ_Karazubagrenze ein wenig größer gemacht wird.


Die Überlegung ist zwar gut, aber an der Karazubagrenze lässt sich leider nicht mehr viel schrauben. Der Wert GNZ_Karazubagrenze=44 stellte sich nach einen automatisierten Laufzeittest als optimal heraus.

Optimierungsmöglichkeiten in der Multiplikationsroutine sehe ich vor allem in einer Überprüfung der dortigen Funktionsaufrufe (ev. lässt sich durch Verwendung von inline ein Vorteil erzielen, aber die Routine ist generell schon sehr groß) sowie in einer von mschnell angeregten Regelung der Übertragsrechnung durch Verwendung von Assembler. Wenn Euch ein Weg einfällt, einige der setlength-Anweisungen rauszuschmeißen, wäre das natürlich auch gut.

Ich danke Euch für Eure Kommentare, die sich positiv auf die Arithmetik-Unit auswirken.


Viele Grüße, Euklid
Euklid
 
Beiträge: 2758
Registriert: 22. Sep 2006, 09:38
Wohnort: Hessen

Beitragvon mschnell » 1. Dez 2008, 12:46 Re: GNURZ - Arithmetik-Unit für große Zahlen

indianer-frank hat geschrieben:Karatsuba skaliert mit Länge^log2(3) = Länge^1.585.

Wenn das wirklich so ist, dass der Gesamt-Aufwand anders skaliert ist natürlich jede low-level-Optimierung erst auf dieser Basis sinnvoll.

Laut Wikipedia geht der der Algorithmus aber von "teuren" Multiplikationen aus. Das ist bei modernen Prozessoren nicht so. Abfragen und Sprünge dauern viel länger als Multiplikationen. Wenn nur die Multiplikationen, nicht aber die Gesamt-Anzahl der Durchläufe der innersten Schleifen entsprechend kleiner skaliert, wird es nichts nützen.

Wenn wir die Addition mit ASM-Übertrags-Optimierung haben, ist es kein Aufwand mehr eine Primitiv-Multiplikation zu schreiben, um einen Test zu machen.

-Michael
mschnell
 
Beiträge: 3215
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon mschnell » 1. Dez 2008, 13:23 Re: GNURZ - Arithmetik-Unit für große Zahlen

Euklid hat geschrieben: In sehr vielen Fällen ist die Geschwindigkeit einer Routine stärker von dem verwendeten Algorithmus abhängig denn von den Hardware-Optimierungen.
Da hast Du absolut recht. Erst wenn man den optimalen High-Level Algorithmus verwendet, lohnt sich eine low-level-Optimierung. Ich vermute, der Karazuba benutzt intern wiederholt eine normale Multiplikation mit kürzeren Langzahlen, die wiederum durch low-Level Optimierung verbessert werden könnte.

Der primitiv-Algorithmus braucht für die n^2 Multiplikationen n^2 Schleifendurchläufe. Wenn Karazuba weniger Schleifendurchläufe benötigt, sollte man ihn natürlich verwenden.

Euklid hat geschrieben:Theoretisch gibt es für sehr große Zahlen eine Methode, die die schnelle Fourier-Transformation benutzt und welche schneller ist als der Karazuba-Algorithmus. Diese wurde noch nicht implementiert.


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

Euklid hat geschrieben:Naja, bedingte Sprünge brauchen bei heutigen Prozessoren nicht mehr sonderlich viele Zyklen. Aber ich stimme dir zu, dass es dem Prozessor erschwert wird, parallel Befehle abzuarbeiten (was moderne Prozessoren tun), wenn der Code viele Sprünge enthält.
Multiplikationen und Additionen brauchen meist (bis zu einer gewissen Sättigung) überhaupt keine Zyklen, weil sie im Hintergrund ausgeführt werden, während der Programm-Fluss weiterläuft.

Euklid hat geschrieben:Probleme macht der Karazuba-Algorithmus insofern, da mir nur ein rekursiver Algorithmus bekannt ist. Ein iterativer Algorithmus wäre hier effektiver, ich konnte jedoch weder einen finden noch einen herleiten.
Ich glaube nicht, dass ein nicht-rekursiver Algorithmus wesentlich effektiver sein muss, wenn der Rekursive gut geschrieben ist.

Euklid hat geschrieben:
Hast Du getestet, ob eine "Pennäler"-mäßige Multiplikationsroutine (eine Dezimalstelle entspricht 32 oder 64-Bit Wert) nicht vielleicht doch schneller ist ?
Ich bin mir nicht sicher, ob ich hier verstanden habe, was du meinst: Aber durch die Setzung der GlobZahlenbasis im Constructor Create wird mit 32bit-Werten pro Stelle gerechnet. Das gilt für alle Routinen.
Klar, für eine Assembler-Optimierung muss die Zahlenbasis der Register-Größe entsprechen: für ein 32-Bit Programm also 32 Bit, für ein 64-Bit-Programm 64 Bit. Variabel (vom Create zu setzen) darf sie auf keinen Fall sein.

Euklid hat geschrieben:
Das könnte vor allem sein wenn die Addition zweier Langzahlen und die Multiplikation einer Langzahl mit einem 32 (oder 64-Bit) Wert mit ASM optimiert ist, um die Behandlung des Übertrags "hardwaremäßig" zu realisieren.
Zustimmung: Das wären ganz sicher lohnenswerte Optimierungen.


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

-Michael
Zuletzt geändert von mschnell am 1. Dez 2008, 13:36, insgesamt 1-mal geändert.
mschnell
 
Beiträge: 3215
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon mschnell » 1. Dez 2008, 13:31 Re: GNURZ - Arithmetik-Unit für große Zahlen

Euklid hat geschrieben:Nur weiß ich nicht, wie ich ihn auf der Grundlage eines GNZTyps, der auf dynamische Arrays beruht, in dieser Hinsicht besser schreiben könnte.
Anscheinend braucht der Algorithmus Zahlen unterschiedlicher "Länge".
Wenn Deine Lang-Zahlen Klasse wären, könnten sie ein dynamisches Array für die Daten-Wörter enthalten, dessen Größe beim Create gesetzt wird und eine Property "AktSize", die nach bedarf gesetzt werden kann und bestimmt, mit wie vielen Stellen gerechnet wird. Wenn Du keine Klasse machen willst, tut's natürlich auch ein Record. C-mäßig wäre es, im ersten Array-Element die effektive Länge zu halten, dann kann ein "normaler" Pointer Cardinal^ verwendet werden, um eine Langzahl anzusprechen.

Euklid hat geschrieben:Der Wert GNZ_Karazubagrenze=44 stellte sich nach einen automatisierten Laufzeittest als optimal heraus.
Wenn die primitive Multiplikation deutlich schneller wird, tritt bei Karazuba der Overhead durch die Code-Komplexität deutlicher zutage und die grenze wird sich nach oben verschieben.

Heißt GNZ_Karazubagrenze=44 bei GlobZahlenbasis=32 44+32 = 1408 Bit ?

-Michael
Zuletzt geändert von mschnell am 1. Dez 2008, 13:35, insgesamt 1-mal geändert.
mschnell
 
Beiträge: 3215
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon indianer-frank » 1. Dez 2008, 13:34 Re: GNURZ - Arithmetik-Unit für große Zahlen

mschnell hat geschrieben:
indianer-frank hat geschrieben:Karatsuba skaliert mit Länge^log2(3) = Länge^1.585.

Wenn das wirklich so ist, dass der Gesamt-Aufwand anders skaliert ist natürlich jede low-level-Optimierung erst auf dieser Basis sinnvoll.

Ich denke, daß große Mißverständsnisse zu den Multiplikation da sind: Karatsuba beruht im wesentlichen darauf, daß eine Langzahlmultiplikationen von zwei Zahlen der Länge L auf drei Langzahlmultiplikationen der Länge L/2 zurückgeführt wird, das ganze rekursiv bis die Länge L/2^k unterhalb der Karatasubagrenze (GNZ_Karazubagrenze) ist. Darunter setzt "Pennäler"-Muliplikation ein, darunter die Prozessor-Multiplikation.

Wenn man die Karatasubaschleife optimiert, kann man GNZ_Karazubagrenze verkleinern, wenn man die "Pennäler"-Muliplikation optimiert (Stichwort Comba), wird man GNZ_Karazubagrenze vergößern.

mschnell hat geschrieben:Laut Wikipedia geht der der Algorithmus aber von "teuren" Multiplikationen aus. Das ist bei modernen Prozessoren nicht so. Abfragen und Sprünge dauern viel länger als Multiplikationen. Wenn nur die Multiplikationen, nicht aber die Gesamt-Anzahl der Durchläufe der innersten Schleifen entsprechend kleiner skaliert, wird es nichts nützen.


Da mißversteht Du schon wieder Multiplikationen. Multiplikationenen=Langzahl-Multiplikationen sind teuer im Vergleich zu Langzahl-Additionen und Langzahl-Verschiebeoperationen. Und Langzahl-Additionen sind viel teurer als Prozesso-Multipliation (wenn man nicht gerade sehr kleine Längen hat).

Frank
indianer-frank
 
Beiträge: 130
Registriert: 30. Nov 2008, 21:53

Beitragvon mschnell » 1. Dez 2008, 13:42 Re: GNURZ - Arithmetik-Unit für große Zahlen

indianer-frank hat geschrieben:Multiplikationenen=Langzahl-Multiplikationen sind teuer im Vergleich zu Langzahl-Additionen und Langzahl-Verschiebeoperationen. Und Langzahl-Additionen sind viel teurer als Prozesso-Multipliation (wenn man nicht gerade sehr kleine Längen hat).

Das ist nicht logisch, Der Algorithmus soll eine Langzahlen-Multiplikation bewerkstelligen, also kann man seine Effektivität nicht in Größenordnungen von Langzahlen-Multiplikation messen.

-Michael
mschnell
 
Beiträge: 3215
Registriert: 11. Sep 2006, 09:24
Wohnort: Krefeld
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ) | 
CPU-Target: X32 / X64 / ARMv5
Nach oben

Beitragvon indianer-frank » 1. Dez 2008, 13:42 Re: GNURZ - Arithmetik-Unit für große Zahlen

mschnell hat geschrieben:Wenn Deine Lang-Zahlen Klasse wären, könnten sie ein dynamisches Array für die Daten-Wörter enthalten, dessen Größe beim Create gesetzt wird und eine Property "AktSize", die nach bedarf gesetzt werden kann und bestimmt, mit wie vielen Stellen gerechnet wird. Wenn Du keine Klasse machen willst, tut's natürlich auch ein Record. C-mäßig wäre es, im ersten Array-Element die effektive Länge zu halten, dann kann ein "normaler" Pointer Cardinal^ verwendet werden, um eine Langzahl anzusprechen.

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.

Frank
indianer-frank
 
Beiträge: 130
Registriert: 30. Nov 2008, 21:53

Beitragvon indianer-frank » 1. Dez 2008, 13:44 Re: GNURZ - Arithmetik-Unit für große Zahlen

mschnell hat geschrieben:
indianer-frank hat geschrieben:Multiplikationenen=Langzahl-Multiplikationen sind teuer im Vergleich zu Langzahl-Additionen und Langzahl-Verschiebeoperationen. Und Langzahl-Additionen sind viel teurer als Prozesso-Multipliation (wenn man nicht gerade sehr kleine Längen hat).

Das ist nicht logisch, Der Algorithmus soll eine Langzahlen-Multiplikation bewerkstelligen, also kann man seine Effektivität nicht in Größenordnungen von Langzahlen-Multiplikation messen.

Will ja auch keiner, der Vergleich ist zu Langzahl-Additionen und Langzahl-Verschiebeoperationen.

Frank
indianer-frank
 
Beiträge: 130
Registriert: 30. Nov 2008, 21:53

» Weitere Beiträge siehe nächste Seite »
VorherigeNächste

Zurück zu Units/Komponenten



Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

porpoises-institution
accuracy-worried