Ich versuche eine polynomische Implementierung von mir zu optimieren. Insbesondere befasse ich mich mit Polynomen mit den Koeffizienten modulo n (könnte >2^64 sein) und modulo mit einem Polynom in der Form x^r - 1 ( r ist < 2^64 ). Im Moment stelle ich den Koeffizienten als eine Liste von ganzen Zahlen (*) dar und ich habe alle grundlegenden Operationen auf die einfachste Weise implementiert.
Ich möchte, dass die Potenzierung und Multiplikation so schnell wie möglich ist, und um das zu erreichen, habe ich bereits verschiedene Ansätze ausprobiert. Mein derzeitiger Ansatz besteht darin, die Koeffizientenlisten in Ganzzahlen umzuwandeln, die ganzen Zahlen zu multiplizieren und die Koeffizienten zurück zu entpacken.
Das Problem ist, dass das Packen und Entpacken viel Zeit in Anspruch nimmt.
Gibt es also eine Möglichkeit, meine "Pack / Unpack" -Funktionen zu verbessern?
%Vor% Beachten Sie, dass ich nicht n wähle, es ist eine Eingabe vom Benutzer, und mein Programm möchte seine Primalität beweisen (mit dem AKS-Test), also kann ich es nicht faktorisieren .
(*) Ich habe mehrere Ansätze ausprobiert:
numpy -Array anstelle einer Liste und multiplizieren Sie mit numpy.convolve . Es ist schnell für n < 2^64 , aber schrecklich langsam für n > 2^64 [ich möchte auch vermeiden, externe Bibliotheken zu verwenden] scipy.fftconvolve . Funktioniert überhaupt nicht für n > 2^64 . mod x^r -1 auszuführen, ohne die ganze Zahl in eine Liste von Koeffizienten umzuwandeln (was den Grund der Verwendung dieser Repräsentation vereitelt). Ich habe einen Weg gefunden, die Conversions zu optimieren, obwohl ich immer noch hoffe, dass jemand mir helfen könnte, sie noch besser zu machen und hoffentlich eine andere clevere Idee zu finden.
Grundsätzlich stimmt es bei diesen Funktionen nicht, dass sie ein quadratisches Speicherzuweisungsverhalten haben, wenn sie die ganze Zahl packen oder wenn sie entpackt werden. (Siehe dieses Post von Guido van Rossum für ein anderes Beispiel für diese Art von Verhalten).
> Nachdem ich das erkannt habe, habe ich beschlossen, es mit dem Divide et Impera-Prinzip zu versuchen, und ich habe einige Ergebnisse erzielt. Ich teile das Array einfach in zwei Teile, konvertiere sie separat und schließe mich schließlich den Ergebnissen an (später werde ich versuchen, eine iterative Version ähnlich der f5 in Rossums Beitrag zu verwenden [edit: es scheint nicht viel schneller zu sein] ).
Die modifizierten Funktionen:
%Vor%Und die Ergebnisse:
%Vor% Wie Sie sehen, gibt diese Version eine ziemlich hohe Geschwindigkeit bis zur Konvertierung, von 4 bis 8 mal schneller (und größer die Eingabe, größer ist die Geschwindigkeit).
Ein ähnliches Ergebnis wird mit der zweiten Funktion erhalten:
Ich habe versucht, in der ersten Funktion, die die Start- und Endindizes umgeht, mehr Speicherreallokationen zu vermeiden und Slicing zu vermeiden, aber es stellt sich heraus, dass dies die Funktion für kleine Eingaben ziemlich verlangsamt und für sie ein wenig langsamer ist Real-Case-Eingaben. Vielleicht könnte ich versuchen, sie zu mischen, obwohl ich nicht glaube, dass ich viel bessere Ergebnisse erzielen werde.
Ich habe meine Frage in der letzten Periode bearbeitet, daher haben mir einige Leute einen Rat mit einem anderen Ziel gegeben als das, was ich kürzlich gefordert habe. Ich denke, es ist wichtig, die Ergebnisse, die von verschiedenen Quellen in den Kommentaren und den Antworten aufgezeigt werden, ein wenig aufzuklären, damit sie für andere Leute nützlich sein können, die schnelle Polynome und / oder AKS-Tests implementieren wollen.
n (gelesen: Wortgrößenzahl) interessieren und externe Abhängigkeiten nicht stören, dann gehen Sie für numpy und verwenden Sie numpy.convolve oder scipy.fftconvolve für die Multiplikation . Es wird viel schneller als alles, was Sie schreiben können. Leider, wenn n keine Wortgröße ist, können Sie scipy.fftconvolve überhaupt nicht verwenden, und auch numpy.convolve wird langsam langsam. numpy -Arrays kombinieren, um effizient zu arbeiten. n wollen, dann scheint meine Lösung die schnellste zu sein. Obwohl ich nicht versucht habe, die fft-Multiplikation zwischen Arrays von Koeffizienten in Python zu implementieren (was kann schneller sein). Wenn Sie das nicht lernen, warum erfinden Sie das Rad neu? Ein anderer Ansatz wäre, einen Python-Wrapper in eine andere Polynombibliothek oder ein anderes Programm zu schreiben, wenn ein solcher Wrapper nicht bereits existiert.
Versuchen Sie PARI / GP. Es ist überraschend schnell. Ich habe vor kurzem einen benutzerdefinierten C-Code geschrieben, der zwei Tage dauerte, um zu schreiben, und stellte sich heraus, dass er nur dreimal schneller war als ein zweizeiliges PARI / GP-Skript. Ich würde wetten, dass ein Python-Code, der PARI aufruft, schneller sein würde als alles, was Sie in Python implementieren. Es gibt sogar ein Modul zum Aufruf von PARI aus Python: Ссылка
Sie könnten Residual Number Systeme verwenden, um die Koeffizienten Ihres Polynoms darzustellen. Sie würden Ihre Koeffizienten auch in kleinere Ganzzahlen aufteilen, wie Sie es jetzt tun, aber Sie müssen sie nicht wieder in eine große Ganzzahl konvertieren, um Multiplikationen oder andere Operationen auszuführen. Dies sollte nicht viel Reprogrammierungsaufwand erfordern.
Das Grundprinzip von Residualzahlsystemen ist die eindeutige Darstellung von Zahlen mittels Modulararithmetik. Die ganze Theorie, die RNS umgibt, erlaubt Ihnen, Ihre Operationen auf den kleinen Koeffizienten zu tun.
bearbeiten: ein kurzes Beispiel:
Angenommen, Sie repräsentieren Ihre großen Koeffizienten in einem RNS mit den Modulen 11 und 13. Ihre Koeffizienten würden alle aus 2 kleinen ganzen Zahlen (& lt; 11 und & lt; 13) bestehen, die zu der ursprünglichen (großen) ganzen Zahl kombiniert werden können. p>
Angenommen, Ihr Polynom ist ursprünglich 33x² + 18x + 44. In RNS wären die Koeffizienten jeweils (33 mod 11, 33 mod 13), (18 mod 11,18 mod 13) und (44 mod 11, 44 mod 13) = & gt; (0,7), (7,5 ) und (0,5).
Das Multiplizieren Ihres Polynoms mit einer Konstanten kann dann erfolgen, indem Sie jeden kleinen Koeffizienten mit dieser Konstante multiplizieren und dann modulo machen.
Sagen Sie, Sie multiplizieren mit 3, Ihre Koeffizienten werden (0,21 mod 13) = (0,8), (21 mod 11,15 mod 13) = (10,2) und (0 mod 11,15 mod 13) = (0,2). Es gab keine Notwendigkeit, die Koeffizienten zurück in ihre große Ganzzahl zu konvertieren.
Um zu überprüfen, ob unsere Multiplikation funktioniert hat, können wir die neuen Koeffizienten wieder in ihre große Darstellung umwandeln. Dies erfordert das "Lösen" jedes Satzes von Koeffizienten als ein modulares System. Für die ersten Koeffizienten (0,8) müssten wir x mod 11 = 0 und x mod 13 = 8 lösen. Dies sollte nicht zu schwer zu implementieren sein. In diesem Beispiel sehen Sie, dass x = 99 eine gültige Lösung ist (modulo 13 * 11)
Wir erhalten dann 99x² + 54x + 132, das korrekte multiplizierte Polynom. Das Multiplizieren mit anderen Polynomen ist ähnlich (aber Sie müssen die Koeffizienten paarweise miteinander multiplizieren). Das Gleiche gilt für die Addition.
Für Ihren Anwendungsfall können Sie Ihr n basierend auf der Anzahl der gewünschten Koeffizienten oder ihrer Größe auswählen.
Wie wäre es mit der direkten Implementierung von Polynomen mit beliebiger Genauigkeit als eine Liste von numpigen Arrays?
Lassen Sie mich erklären: Sagen Sie, Ihr Polynom sei Σ P p
. Wenn die große ganze Zahl A p dargestellt werden kann als A p = p k k2 p> 64 k
dann wird das k th numpy-Array den 64-bit int A p, k an Position p enthalten.Sie können je nach Struktur Ihres Problems dichte oder spärliche Arrays auswählen.
Die Implementierung von Additions- und Skalaroperationen ist nur eine Frage der Vektorisierung der bignum-Implementierung derselben Operationen.
Die Multiplikation könnte wie folgt gehandhabt werden: AB = & Sgr; p, k, p ', k' A p, k B p, k '
2 64 (k + k ') X p + p . Eine naive Implementierung mit dichten Arrays könnte daher zu log 64 (n) 2 Aufrufen nachnumpy.convole oder scipy.fftconvolve führen.
Die Modulo-Operation sollte leicht zu implementieren sein, da sie eine lineare Funktion des linken Terms ist und der rechte Ausdruck kleine Koeffizienten hat.
BEARBEITEN Hier sind einige weitere Erklärungen
Anstatt das Polynom als eine Liste von willkürlichen Präzisionszahlen darzustellen (die selbst als Listen von 64-Bit- "Ziffern" dargestellt werden), transponiere die Darstellung so, dass:
Wenn nur ein paar Ihrer Koeffizienten sehr groß sind, dann haben die Arrays meistens Nullen, daher kann es sich lohnen, dünn besetzte Arrays zu verwenden.
Rufen Sie A p, k die k th Ziffer des p th Koeffizienten auf.
Beachten Sie die Analogie zu großen Ganzzahldarstellungen: Eine große Ganzzahl würde als
dargestelltx = Σ k k x k k
Ihr Polynom A wird auf die gleiche Weise wie
dargestelltA = Σ k k <64 k A k = k k p p k x p p
Um die Hinzufügung zu implementieren, geben Sie einfach vor, dass Ihre Liste von Arrays eine Liste einfacher Zahlen ist und implementieren Sie Addition wie üblich für große ganze Zahlen (achten Sie darauf, if then conditionals durch numpy.where zu ersetzen).
Um die Multiplikation zu implementieren, müssen Sie log 64 (n) 2 Polynom-Multiplikationen machen.
Um die Modulo-Operation für die Koeffizienten zu implementieren, ist es wieder ein einfacher Fall, die Modulo-Operation in eine große ganze Zahl zu übersetzen.
Um den Modulo durch ein Polynom mit kleinen Koeffizienten zu erhalten, verwenden Sie die Linearität dieser Operation:
A mod (X r - 1) = (Σ k k <2> <64 k ) mod (X r - 1)
= Σ k2 64 k (A k
r - 1))
Tags und Links python optimization polynomial-math