hyperG
Senior Dabei seit: 03.02.2017 Mitteilungen: 1311
Themenstart: 2020-05-14
Es gibt ja bereits mehrere Interpolations-Algorithmen, um vorgegebene Zahlenfolgen zu generieren (Polynom- I., trigonometrische I. , Nachkommastellen irrationaler Zahlen...).
Im Gegensatz zu den Nachkommastellen von irrationalen Zahlen
(wo man nur nach "Mustern suchen" kann),
sollte es doch bei Pseudozufallsgeneratoren (Modulo-Iteration )
möglich sein, bei gegebener Zahlenfolge den STARTPUNKT der Iteration zu bestimmen.
Damit die Periode aber extrem groß bleibt und die vorgegebenen Glieder der Folge auch klein sein können, muss ja eine 2. Modulofunktion nachgeschaltet werden. Hier ein Beispiel:
Natürlich kann man durch "Probieren" den Startpunkt von bis zu 4 Gliedern relativ leicht finden, ABER gibt es nicht eine Möglichkeit durch Umstellen die Iteration "rückwärts" ablaufen zu lassen?
Beispiel:
Die Gleichung, die das Glied 13 ergibt: (x*1000) mod 111=13
hat ja folgende Geradengleichung als Lösung: x=111*n+13
Wenn das Glied davor 12 sein soll, könnte man doch
(x1*1000) mod 111=12
x1=111*n+12
beide Geradengleichungen miteinander verbinden.
Diese kleinen Faktoren (hier 1000 und 111) erzeugen jedoch keine große Periode -> und so bleibt nur die Verschachtelung von 2 Modulofunktionen, die ich aber momentan nicht umstellen kann...
a) gibt es da schon Algorithmen oder Begriffe, nach denen man suchen könnte? (Interpolation per Pseudozufallsgenerator brachte kein Erfolg)
b) kann man so etwas ohne Herumprobieren umstellen oder ein Gleichungssystem aufstellen?
So um die 9 Glieder als Vorgabe sollten schon möglich sein
(egal ob 1, 2 oder 3stellig).
Algorithmus 1: Probieren, bis es funktioniert (dauert sehr lange)
Algorithmus 2: elegant die Modulo-Iteration "rückwärts" bis zum Startwert berechnen (den suche ich)
Hinweis: nur sehr wenige Modulo-Werte erzeugen gute Pseudo-Zufallswerte mit einer sehr großen Periodendauer von über 1 Mrd.
Lösung: aB[0]=1905323518
Mit der 2. Modulo-Funktion werden die "großen Pseudo-Zufallswerte" zu kleineren Zahlenfolge konvertiert:
aC[i] = aB[i] % 107+6
Problem: will man statt 5 nun 7 Elemente der Folge vorgeben, vergrößert sich die Suchzeit um etwa das 10000 FACHE!
@pzktupel:
"Die Berechnung wäre in <100 Schritten erledigt" verstehe ich nicht.
Kannst Du mir zeigen, wie "Dein" Algorithmus die Folge
36, 30, 6, 108, 33 (und noch 2 weitere)
erzeugen kann und dabei noch eine Periode größer 1 Mio. hat?
(d.h. noch 1 Mio. weitere Glieder, ohne dass sich eine Periode erkennen lässt)
Verboten sind also auch Algorithmen, die einfach nur aus einer gegebenen Zahl je 3 Ziffern extrahiert wie:
036030006108033 mod 1000 -> 33
durch 1000 ohne Rest
036030006108 mod 1000 -> 108
... usw. -> da sich damit nur begrenzte Zahlenfolgen erzeugen lassen
(außerdem ginge das auch mit String-Funktionen)
pzktupel
Aktiv Dabei seit: 02.09.2017 Mitteilungen: 1746
Herkunft: Thüringen
Beitrag No.3, eingetragen 2020-05-18
Ui, ich verstehe !
Ich sage vorsichtig erstmal, das könnte mit einem Fingerschnipp berechenbar sein.
Ich muss das erstmal sortieren...die Zahlen sind zu groß im Bsp um das hier aufzudröseln. (Kann mich aber auch irren)
Hm, ich versuche mal was:
Du hast aC[i] = aB[i] % 107+6, also
X MOD 107+6=36 -> 30 = X MOD 107 , X=30+107Y
Also das X ist Teil von aB[i]
aB[i+1]:= (aB[i] * 630360016) modulo 2147483647
:
((30+107Y) * 630360016) modulo 2147483647 = 0
18910800480 + 67448521712 Y modulo 2147483647
also 18910800480 + 67448521712 Y muss durch 2147483647 teilbar sein
Gleichung normiert 67448521712 Y + 1 = 2147483647 Z
67448521712 Y + 1 = 2147483647 Z
876528655 Y + 1 = 2147483647 Z
876528655 Y + 1 = 394426337 Z
87675981 Y + 1 = 394426337 Z
87675981 Y + 1 = 43722413 Z
231155 Y + 1 = 43722413 Z
231155 Y + 1 = 34118 Z
26447 Y + 1 = 34118 Z
26447 Y + 1 = 7671 Z
3434 Y + 1 = 7671 Z
3434 Y + 1 = 803 Z
222 Y + 1 = 803 Z
222 Y + 1 = 137 Z
85 Y + 1 = 137 Z
85 Y + 1 = 52 Z
33 Y + 1 = 52 Z
33 Y + 1 = 19 Z
14 Y + 1 = 19 Z
14 Y + 1 = 5 Z
4 Y + 1 = 5 Z
4 Y + 1 = Z
Y=1, Z=5
hyperG
Senior Dabei seit: 03.02.2017 Mitteilungen: 1311
Beitrag No.7, vom Themenstarter, eingetragen 2020-05-19
Nachdem ich mein Suchprogramm nochmals optimiert habe
(150 Modulos parallel während eines Haupt-Iterationsschrittes, Negation; usw.) ...
hier die Lösung:
Und noch zum Hintergrund:
Dieser Generator kann im Gegensatz zu anderen Interpolations-Algorithmen über 1 Mrd. Folgeglieder blitzschnell erzeugen, ohne eine PERIODE aufzuzeigen:
- trigonometrische Interpolation hat sehr kurze Periode
- Nachkommastellen irrationaler Zahlen lassen sich ab 1 Mrd. Nachkommastellen nur sehr langsam berechnen
- Polynome driften sehr schnell ab oder lassen sich schnell durchschauen...
Diese Erkenntnisse kann ich nun hier gleich praktisch anwenden!
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Themenstart: 2020-05-14
Für hyperG bei den Matheplanet-Awards stimmen
Notiz
Profil
Quote
Link
