[python] Wie lange wird diese Exponentiation dauern?

Neue Frage »

12.11.2023, 17:43

Malcang

Auf diesen Beitrag antworten »

[python] Wie lange wird diese Exponentiation dauern?

Hallo mal wieder smile

Ich lasse gerade einige Berechnungen laufen (Proth'sche Zahlen, wie immer Big Laugh

).
Jedenfalls geht es dabei um sehr große modulare Exponentiationen.
Im vorliegenden Fall will ich folgendes Berechnen:
$\begin{eqnarray*} 5^{\frac{m-1}{2}} \mod m \end{eqnarray*}$ mit $\begin{eqnarray*} m = 631383\cdot 2^{2525534}+1 \end{eqnarray*}$ (das ist die derzeit größte bekannte Cullen-Primzahl).
Nun wollte ich gerne abschätzen, wie lange das dauert. Dazu habe ich folgendes gemacht:
Ich habe diese Berechnungen für alle $\begin{eqnarray*} m \end{eqnarray*}$ der Form $\begin{eqnarray*} m = 631383\cdot 2^k \end{eqnarray*}$ mit $\begin{eqnarray*} 26 \leq k \leq 10^4 \end{eqnarray*}$ und $\begin{eqnarray*} k \equiv 2 \pmod{12} \end{eqnarray*}$ durchgeführt. (Ich hatte das erst mit allen Zahlen $\begin{eqnarray*} 26 \leq k 10^4 \end{eqnarray*}$ probiert, aber festgestellt, dass es bei verschiedenen Restklassen sehr unterschiedliche Ergebnisse gab. Daher hier auf $\begin{eqnarray*} \equiv 2 \pmod{12} \end{eqnarray*}$ gegangen).
Diese Zeiten habe ich gemessen und mit einem Polynom 2. Grades angenähert. Außerdem habe ich das Rauschen untersucht. Das ganze sieht so aus (die Beschriftung an der x-Achse ist falsch. Das ist nur die Anzahl der untersuchten Exponenten, nicht der jeweilige Exponent selbst)
[attach]57349[/attach]
Das quadratische Polynom lautet $\begin{eqnarray*} f: x\mapsto 0.08 - 9.65\cdot 10^{-5}x + 2.57\cdot10^{-8}x^2 \end{eqnarray*}$
Nun habe ich mir also $\begin{eqnarray*} f(2525534) \approx 163679 \end{eqnarray*}$ angeschaut. Das ergbit eine Berechnungszeit von 45 Stunden.

Mir ist schon klar, dass dies nicht die genaue Zeit ist, und es sicher eher länger dauern wird. Aber ist dies eine "annehmbare" Approximation? Kann ich eine bessere Abschätzung erlangen?

12.11.2023, 18:26

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Im vorliegenden Fall will ich folgendes Berechnen:
$\begin{eqnarray*} 5^{\frac{m-1}{2}} \mod m \end{eqnarray*}$ mit $\begin{eqnarray*} m = 631383\cdot 2^{2525534}+1 \end{eqnarray*}$ (das ist die derzeit größte bekannte Cullen-Primzahl).

Du willst also $\begin{eqnarray*} 5^{\frac{m-1}{2}}\equiv -1\bmod m \end{eqnarray*}$ auf andere Weise als über das Quadratische Reziprozitätsgesetz berechnen? verwirrt

12.11.2023, 18:30

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Du willst also $\begin{eqnarray*} 5^{\frac{m-1}{2}}\equiv -1\bmod m \end{eqnarray*}$ auf andere Weise als über das Quadratische Reziprozitätsgesetz berechnen? verwirrt

Hallo HAL. Ich habe das nun über die in python eingebaute Funktion

Zitat:

pow(a,b,m)

gemacht, das mir $\begin{eqnarray*} a^b\pmod m \end{eqnarray*}$ liefert.

Du sagst, eine andere Weise als das QRP? Ah, du willst darauf hinaus dass ich die größte Cullen-Primzahl erwähnt hab, oder?
Im Allgemeinen nutze ich meinen Algorithmus aus dem anderen Thread. In diesem Falle hier weiß ich halt einfach, dass $\begin{eqnarray*} -1 \end{eqnarray*}$ rauskommen sollte. Ich wollte das für meine Ausarbeitung einfach mal "live" machen smile

Oder habe ich dich falsch verstanden.

12.11.2023, 18:32

HAL 9000

Auf diesen Beitrag antworten »

Ja, wenn man natürlich nicht weiß, dass dieses $\begin{eqnarray*} m \end{eqnarray*}$ eine Primzahl ist, dann funktioniert der Weg über das Quadratische Reziprozitätsgesetz selbstredend nicht. Augenzwinkern

12.11.2023, 18:34

Malcang

Auf diesen Beitrag antworten »

Danke HAL und sorry, da war ich zu betriebsblind und hab es deshalb nicht erwähnt smile

Aber wenn ich das mal rein auf die Berechnungszeit betrachte, ist mein Ansatz mit der Messung dann korrekt?

12.11.2023, 18:48

HAL 9000

Auf diesen Beitrag antworten »

Ich versuche das mal aufgrund der angenommenen Berechnungsweise zu verstehen:

Eine Multiplikation zweier ganzer Zahlen mit ungefähr $\begin{eqnarray*} x \end{eqnarray*}$ Binärstellen hat Komplexität $\begin{eqnarray*} O\left(x\ln(x)\right) \end{eqnarray*}$ , das schaffen zumindest moderne Multiplikationsalgorithmen basierend auf FFT (gegenüber dem herkömmlichen, schlechteren $\begin{eqnarray*} O\left(x^2\right) \end{eqnarray*}$ der "schriftlichen" Multiplikation). Nun sind bei dieser Potenzberechnung auch in etwa $\begin{eqnarray*} O(x) \end{eqnarray*}$ solche Multiplikationen nötig, daher wäre meine Vermutung für die Komplexität eher $\begin{eqnarray*} O\left(x^2\ln(x)\right) \end{eqnarray*}$ als dein $\begin{eqnarray*} O\left(x^2\right) \end{eqnarray*}$ . verwirrt

12.11.2023, 18:55

Malcang

Auf diesen Beitrag antworten »

Danke sehr, das gibt mir schon eine andere Sicht. Ich war einfach von quadratischem Wachstum ausgegangen und konnte mir "np.polyfit" auch noch eine Phyton-Funktion finden, die mir das so annähert. Aber sieht der der empirischen Daten denn nicht auch stark quadratisch aus?
Ich bin beim Thema Komplexität leider völlig raus.
Aber mit dem Hintergrundwissen von dir, HAL, wie könnte ich denn hier eine besser passende Funktion finden? Also wie könnte ich meine empirischen Daten durch eine Funktion der Form $\begin{eqnarray*} f: x\mapsto a\cdot x^2\cdot \ln(bx) \end{eqnarray*}$ (richtig?) annähern?

12.11.2023, 19:05

HAL 9000

Auf diesen Beitrag antworten »

Naja, wenn du es mit dem Ansatz probieren willst, der entspricht ja

$\begin{eqnarray*} f(x) = ax^2\ln(x) + cx^2 \end{eqnarray*}$ mit $\begin{eqnarray*} c=a\ln(b) \end{eqnarray*}$

Diese Koeffizienten $\begin{eqnarray*} a,c \end{eqnarray*}$ kann man aus deinem empirischen Material mit multipler linearer Regression fitten.

Allzu kleine $\begin{eqnarray*} x \end{eqnarray*}$ würde ich noch nicht in diese Statistik einbeziehen, da dort der Einfluss des "krummen" 631383 im Exponent noch zu groß ist. Also über den Daumen gepeilt anhand deines Graphes vielleicht nur die von 400..800 einbeziehen. Verlang aber bloß keine genauere Erklärung für dieses eher heuristische Argument. Augenzwinkern

12.11.2023, 19:16

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Naja, wenn du es mit dem Ansatz probieren willst, ...

Das war nur mein erster Gedanke. Was würdest du denn machen?

Zitat:

Original von HAL 9000
Verlang aber bloß keine genauere Erklärung für dieses eher heuristische Argument. Augenzwinkern

12.11.2023, 21:40

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Das war nur mein erster Gedanke. Was würdest du denn machen?

Musst ja nicht jedes Wort eine Goldwaage legen. Probier es einfach aus, und wenn ein gutes Bestimmtheitsmaß herauskommt, umso besser. Wenn nicht, dann kannst du dir ja dann nochmal Gedanken machen, ob weitere/andere Glieder im Modell evtl. sinnvoll sein könnten.

13.11.2023, 19:57

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Malcang
Das war nur mein erster Gedanke. Was würdest du denn machen?

So war das nicht gemeint. Ich hatte nur aus deinem

Zitat:

Naja, wenn du es mit dem Ansatz probieren willst...

reausgelesen, dass du es vielleicht mit einem anderen Ansatz machen würdest. Und der wäre mit deinem Wissen dann natürlich sinniger smile

14.11.2023, 08:33

HAL 9000

Auf diesen Beitrag antworten »

Das ist ja alles sehr schön, aber hast du nun diese Regression durchgeführt oder nicht?

14.11.2023, 09:26

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Das ist ja alles sehr schön, aber hast du nun diese Regression durchgeführt oder nicht?

Nein, ich hatte das weil die Berechnung nach ~60 Stunden fertig war dann wieder ad acta gelegt.
Interessieren würde es mich aber trotzdem. Dazu würde ich aber ohnehin wieder einen Thread aufmachen, weil ich das Thema gar nicht kenne Big Laugh

Können wir das hier vielleicht fortführen? Womit muss ich beginnen?

Ich habe ja die Wertepaare $\begin{eqnarray*} (x, f(x)) \end{eqnarray*}$ , wobei $\begin{eqnarray*} f \end{eqnarray*}$ hier nur meine angenäherte Funktion ist.

14.11.2023, 09:46

HAL 9000

Auf diesen Beitrag antworten »

Ok, das werde ich jetzt nicht im einzelnen erläutern, verweise auf die in https://de.wikipedia.org/wiki/Multiple_lineare_Regression dargestellten Grundlagen.

Die Kurzfassung bezogen auf dein Modell $\begin{eqnarray*} f(x)= ax^2\ln(x) + cx^2 \end{eqnarray*}$ :

Du hast Datenpaare $\begin{eqnarray*} (x_i,y_i) \end{eqnarray*}$ für $\begin{eqnarray*} i=1,\ldots,n \end{eqnarray*}$ vorliegen, für die du $\begin{eqnarray*} a,c \end{eqnarray*}$ so anpassen willst, dass Näherung $\begin{eqnarray*} y_i\approx f(x_i) \end{eqnarray*}$ möglichst gut funktioniert. Dazu konstruiere Matrizen bzw. Vektoren

$\begin{eqnarray*} X = \begin{pmatrix} x_1^2\ln(x_1) & x_1^2\\ x_2^2\ln(x_2) & x_2^2\\ \vdots & \vdots\\ x_n^2\ln(x_n) & x_n^2\end{pmatrix} \end{eqnarray*}$ und $\begin{eqnarray*} y = \begin{pmatrix} y_1\\ \vdots\\ y_n\end{pmatrix} \end{eqnarray*}$ ,

dann sind $\begin{eqnarray*} \begin{pmatrix} a\\ c\end{pmatrix} = \left(X^T X\right)^{-1} \left(X^T y\right) \end{eqnarray*}$ optimal im Sinne einer minimalen Summe der quadratischen Abweichung

$\begin{eqnarray*} \left\| X\begin{pmatrix} a\\ c\end{pmatrix} - y\right\|_2^2 = \sum_{i=1}^n \left(ax_i^2\ln(x_i)+cx_i^2-y_i\right)^2 \to \min! \end{eqnarray*}$ bzgl. $\begin{eqnarray*} a,c \end{eqnarray*}$ .

Alternativ kannst du gemäß $\begin{eqnarray*} \frac{f(x)}{x^2} = a\ln(x) + c \end{eqnarray*}$ auch einfach lineare Regression angewandt auf die Datenpaare $\begin{eqnarray*} \left( \ln(x_i), \frac{y_i}{x_i^2}\right) \end{eqnarray*}$ durchführen, was aber zu leicht anderen Koeffizienten $\begin{eqnarray*} a,c \end{eqnarray*}$ führt, weil das Optimalitätskriterium hier ein anderes ist, nämlich

$\begin{eqnarray*} \sum_{i=1}^n \left(a\ln(x_i)+c-\frac{y_i}{x_i^2}\right)^2 \to \min! \end{eqnarray*}$ bzgl. $\begin{eqnarray*} a,c \end{eqnarray*}$ .

Bedeutet eine stärkere Gewichtung der kleineren $\begin{eqnarray*} x_i \end{eqnarray*}$ , was wir hier eigentlich nicht wollen (Ziel ist ja die Extrapolation der Rechenzeiten für große $\begin{eqnarray*} x \end{eqnarray*}$ ). Daher würde ich die "echte" erstgenannte Regresssion hier vorziehen.

14.11.2023, 09:58

Malcang

Auf diesen Beitrag antworten »

Cool, danke sehr HAL! Freude

Später am Laptop werde ich das sofort mal umsetzen!

14.11.2023, 19:33

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

dann sind $\begin{eqnarray*} \begin{pmatrix} a\\ c\end{pmatrix} = \left(X^T X\right)^{-1} \left(X^T y\right) \end{eqnarray*}$ optimal im Sinne einer minimalen Summe der quadratischen Abweichung

HAL, $\begin{eqnarray*} X \end{eqnarray*}$ ist eine $\begin{eqnarray*} n\times 2 \end{eqnarray*}$ -Matrix, oder?
Denn dann ist doch $\begin{eqnarray*} X^ty \end{eqnarray*}$ nicht defniert?

14.11.2023, 19:46

HAL 9000

Auf diesen Beitrag antworten »

Brauchen wir wirklich eine Wiederholung Grundlagen Matrix-Multiplikation??? Nun gut:

Matrix mit Dimension $\begin{eqnarray*} u\times v \end{eqnarray*}$ multipliziert mit Matrix der Dimension $\begin{eqnarray*} v\times w \end{eqnarray*}$ ergibt Matrix der Dimension $\begin{eqnarray*} u\times w \end{eqnarray*}$ .

Und nund die Anwendung hier:

$\begin{eqnarray*} X \end{eqnarray*}$ ist eine $\begin{eqnarray*} n\times 2 \end{eqnarray*}$ -Matrix, und $\begin{eqnarray*} y \end{eqnarray*}$ ein $\begin{eqnarray*} n \end{eqnarray*}$ -Vektor bzw. gleichbedeutend eine $\begin{eqnarray*} n\times 1 \end{eqnarray*}$ -Matrix. Dann besitzen die folgenden Größen diese Dimensionen:

$\begin{eqnarray*} X^T \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times n \end{eqnarray*}$
$\begin{eqnarray*} X^TX \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times 2 \end{eqnarray*}$
$\begin{eqnarray*} \left(X^TX\right)^{-1} \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times 2 \end{eqnarray*}$
$\begin{eqnarray*} X^Ty \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times 1 \end{eqnarray*}$
$\begin{eqnarray*} \left(X^TX\right)^{-1}\left(X^Ty\right) \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times 1 \end{eqnarray*}$

Wo siehst du da Probleme???

14.11.2023, 19:57

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Brauchen wir wirklich eine Wiederholung Grundlagen Matrix-Multiplikation??? Nun gut:

Matrix mit Dimension $\begin{eqnarray*} u\times v \end{eqnarray*}$ multipliziert mit Matrix der Dimension $\begin{eqnarray*} v\times w \end{eqnarray*}$ ergibt Matrix der Dimension $\begin{eqnarray*} u\times w \end{eqnarray*}$ .

Und nund die Anwendung hier:

$\begin{eqnarray*} X \end{eqnarray*}$ ist eine $\begin{eqnarray*} n\times 2 \end{eqnarray*}$ -Matrix, und $\begin{eqnarray*} y \end{eqnarray*}$ ein $\begin{eqnarray*} n \end{eqnarray*}$ -Vektor bzw. gleichbedeutend eine $\begin{eqnarray*} n\times 1 \end{eqnarray*}$ -Matrix. Dann besitzen die folgenden Größen diese Dimensionen:

$\begin{eqnarray*} X^T \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times n \end{eqnarray*}$
$\begin{eqnarray*} X^TX \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times 2 \end{eqnarray*}$
$\begin{eqnarray*} \left(X^TX\right)^{-1} \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times 2 \end{eqnarray*}$
$\begin{eqnarray*} X^Ty \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times 1 \end{eqnarray*}$
$\begin{eqnarray*} \left(X^TX\right)^{-1}\left(X^Ty\right) \end{eqnarray*}$ Dimension $\begin{eqnarray*} 2\times 1 \end{eqnarray*}$

Wo siehst du da Probleme???

Nirgendwo... ach man, warum passieren mir immernoch diese Flüchtigkeitsfehler... Sorry und Danke!

16.11.2023, 08:53

HAL 9000

Auf diesen Beitrag antworten »

Wenn's so ein Riesenproblem ist, dann reich den Datensatz mit den gemessenen Zeiten für die jeweiligen $x$ einfach mal rüber und ich berechne dir $\begin{eqnarray*} a,c \end{eqnarray*}$ bzw. dann in der Folge $\begin{eqnarray*} b \end{eqnarray*}$ , inklusive Bestimmtheitsmaß (Gütefaktor der Anpassung).

16.11.2023, 08:59

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Wenn's so ein Riesenproblem ist, dann reich den Datensatz mit den gemessenen Zeiten für die jeweiligen $x$ einfach mal rüber und ich berechne dir $\begin{eqnarray*} a,c \end{eqnarray*}$ bzw. dann in der Folge $\begin{eqnarray*} b \end{eqnarray*}$ , inklusive Bestimmtheitsmaß (Gütefaktor der Anpassung).

Das ist ein tolles Angebot, vielen Dank HAL!
Ich wollte aber ohnehin gerade einen neuen Thread aufmachen, in dem es um Komplexitätsbestimmung geht (auch für diesen Algorithmus).

Ich hoffe das ist ok wenn ich dazu einen neuen Thread starte. Ansonsten kann ein Moderator das vielleicht einfach löschen und den Post hierher verschieben?
Danke nochmal für das Angebot und die Hilfe!! Freude

Zitat:

Original von HAL 9000
$x$

Schade dass das Board diesen Math-mode nicht unterstützt. Mir passiert es auch ständig Big Laugh

Neue Frage »

Antworten »

[python] Wie lange wird diese Exponentiation dauern?

Verwandte Themen