Hallo Hagen,
Beispielprogramm und innere Zitate wegen Doppelquote gelöscht
Zitat von
negaH:
Datentypen müssen ersetzt werden, wie schon erwähnt.
Eben nicht (wenn wir das gleiche meinen
). Der "diskrete Logarithmus", ich denke du meintest die "diskrete modulare Exponentation" was im Grunde ein falscher Name ist, wir reden von der "binären modularen Exponentation". Dieser Algo. kann eben nicht überlaufen denn die größte Zahl die entstehen kann in diesem Algo. ist exakt 2 mal an Bits größer als das Modulo -> also als das N. Wenn wir N also als Integer deklarieren dann müssen die Multiplikation und Quadrierungen in diesem Algo mit Int64 Datentypen arbeiten. Bedenkt man welche Datengrößen entstehen wenn man erst m^e ausrechnet, Ln2(m)*Ln2(e), dann sind das schon sehr kleine Zahlengrößen mit denen die "binäre Exponentation" auskommt.
Suche mal hier im Forum nach "modulare binäre Exponentation", ich hatte schon einen Source gepostet der mit Int64 arbeitet.
Die Bezeichnung Diskreter Logarithmus habe ich nur verwendet, weil Mb123 so seine Funktion bezeichnet hat
sonst wäre ich auch nicht auf den Namen gekommen.
Zitat von
negaH:
@MatWur:
Man alloziert zb. den Speicher für das Resultat gleich am Anfang der Funktion und arbeitet nun alle Teiloperationen nur in diesem Speicher ab. Meine Karatsuba Implementierung benötigt zb. ein Ln2(A) + Ln2(B) Bits großes Resultat und intern ein Temporary das 2 * (Ln2(A) + Ln2(B)) groß ist. Alle Operationen sprich Inputs für die rekursiven Karatsuba Aufrufe und deren Outputs arbeiten nun immer in diesem Speicherbereich. Wenn die äußerste Karatsuba zum Aufrufer zurückkehrt steht in diesem Speicher quasi das Resultat das durch die rekursiven Aufrufe der Karatsuba Funktion direkt berechnet wurden. Ich weis nicht ob's dir was bringt aber ich habe mal meinen Karatsuba rangehangen.
inplaced ist mir durch deine Antwort in meinem FFT-Fred schon klar geworden, die geringe Menge an Speicher will mir noch nicht so recht in den Kopf gehen. Aber ich werde deine Beispielroutinen durchgehen, dann wird mir hoffentlich einiges klarer. Aber ohne praktisches Beispiel ist sowas immer schwer nach zu vollziehen. Zumindestens mir geht es so
Zitat von
negaH:
Soviel wie ich weis ist das nicht der SSE2 Befehlssatz. SSE2 ist erstmal eine Intel Erfindung, AMD's Counterpart heist anders, denoch haben sich AMD und Intel geeinigt und neuere AMDs unterstützen SSE2. Das hat nichts mit dem Coprozessor zu tuen, der arbeitet mit Fließkommazahlen. Das intern in den CPUs weite Teile des Coprozessors und dieser SSE2 Befehle in den gleichen Recheneinheiten erledigt werden ist dabei nebensächlich. Sogesehen stimmt deine Aussage wiederum indirekt
Ja, alle meine Routinen arbeiten nur mit Ganzzahlen, sie nutzen also nirgends die Fließkommazahlen des Coprozessors, der ist viel zu langsam.
hmmm, auf meinem Computer ist der Coprozessor deutlich schneller als die Ganzzahlarithmetik, auch wenn er Gleitkommazahlen berechnet. Bei Berechnungen mit 4 oder 5 Operationen lohnt es sich sogar mit Runden und zurückspeichern in einen Ganzzahlwert. Vielleicht habe ich eine völlig falsche Vorstellung von SSE2... mit Hardwareinterna und Befehlssätzen habe ich mich schon lange nicht mehr befasst. Black Box Computer.
Zitat von
negaH:
Die Karatsuba-Sqr ist natürlich schneller als die Mul, ca. 1.5 mal. Auch diesen Source habe ich mal unten rangehangen. Das sieht ma auch am Source im Vergleich, die Sqr ist viel kompakter hat also weniger Sonderfälle zu berücksichtigen, ergo performanter und ruft natürlich im Innersten auch die Sqr-Schoolboy Methode auf die eben ihrerseits 1.5 mal schneller sein sollte als eine Schoolboy Multiplikation.
Über die Karatsuba-Methode haben wir gerade in meinem Matheforum diskutiert, ich wage mal folgende Behauptung aus Intuition heraus: die Zeitersparnis bei deiner Quadratur (und die ist im Testprogramm zu deiner Bibliothek ja klar ersichtlich) wird zu 99% durch die Zeitersparnis der Sqr-Schoolboy Methode 'erzeugt', nur sehr wenig der gesamten Zeitersparnis von der speziellen Methode(n) während der Karatsuba-Rekursion. Das könnte man in etwa so zeigen: Quadriere Zahlen, die gerade noch nur mit der Sqr-Schoolboy Methode abgearbeitet werden können und miss die Zeitersparnis gegenüber der Multiplikation. Bereits diese hohen 'nur Sqr-Schoolboy Methode'-Zahlen werden eine Zeitersparnis von ca 33% erbringen. Quadrierst du dann Zahlen bis zur Maximalgrösse für Karatsuba wird sich diese Zeitersparnis prozentual nur sehr wenig weiter erhöhen. Aber wie gesagt, ich schaue mir das Beispielprogramm genau an sobald ich dazu komme.
Zitat von
negaH:
Nein. Das sind Funktionen die quasi 1 Digit zu einem großen Speicherbereich addieren/subtrahieren. Wenn wei zb. bei Karatsuba inplaced unsere Zahlen zerlegt haben,rekursiv immer die Hälte von der Hälfte, dann müssen wir nach deren Multiplikation ja das Resultat wieder zusammenbauen. Bei dieser Operation entstehen Über/Unterläufe, Carry, die wir dann natürlich in die anderen Hälten des Resultates einrechnen müssen. Dazu benötigt man also Funktionen die zb. die Zahl +1 in eine große Zahle reinrechnen, ein Carry eben.
DIncD() wäre zb. so eine Funktion bei mir, "Digit-Speicher Increment with one Digit" -> 1 Digit = 32 Bit.
ah ja, das wird klar. Da ich solche Algorithmen immer sehr kompakt programmiere (bei weiten nicht so schön und modular wie bei dir
) ist das ein Problem, das direkt im Algorithmus gelöst wird, ich verwende dafür keine eigene Unterroutine.
Zitat von
negaH:
Das ist Karatsuba aber man splittet in 3 Teile statt nur 2 Hälften. Es gibt demzufolge auch eine Toom-Cook-5,-7,-11 und so weiter.
Gruß Hagen
Klingt eigentlich logisch. Dann wird auch klar warum diese Algorithmen gestaffelt immer noch ein bischen Zeitersparnis auf den letzten draufpacken. Muss ich auch mal genauer durchleuchten.
Deine Routinen werde ich genauer durchleuchten und dich dann evtl. noch mal mit ein paar Fragen quälen^^ Für weitere Diskussionen sollten wir dann besser meinen Fred mit den FFT's nehmen, sonst gerate ich noch in den Verdacht Mb123's Fred zu misbrauchen
Aber danke dir wieder herzlich für die Informationen, die nächsten Tage habe ich ein Haufen Input's zu verarbeiten
bis denne
Matthias