Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Suche Interpolation per Pseudozufallsgenerator
Autor
Universität/Hochschule Suche Interpolation per Pseudozufallsgenerator
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1596
  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: hier per Iterationsrechner https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Pseudozufallsgenerator2stellig.png 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).


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2090
Wohnort: Thüringen
  Beitrag No.1, eingetragen 2020-05-18

Ich weiß nicht, was da passiert, aber bzgl MODULO hatte ich einen Algorithmus mal entwickelt. Darauf bassieren die Programme für die k-Tupelsuche. Sowas wie : X*79812749181+1998912381=99927181 MOD 173891274981 (Die Berechnung wäre in <100 Schritten erledigt) Dieses X ist dann auch verknüpfbar mit beliebig anderen Bedingungen. Das Verfahren konnte ich selbst nicht nocheinmal finden, ist also offen, ob ich der Urheber bin. Zu Deinem Beispiel (ist hier einfach): (x*1000) mod 111=13 Verfahren: 1000x-13=111y Normierung zu: 1000x+1=111y /1000 MOD 111=1 x+1=111y y=1,x=110 110*1000+1=111y, y=991 1000*110+1=111*991 Nun für -13 ! (-13*110) MOD 111=13 also 13*1000 MOD 111 = 13


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1596
  Beitrag No.2, vom Themenstarter, eingetragen 2020-05-18

Konkret gegeben Zahlenfolge 36, 30, 6, 108, 33 Iteration: aB[i+1]:= (aB[i] * 630360016) modulo 2147483647 GESUCHT: Startwert aB[0] der Iteration 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 https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_FolgePerZufallsgenerator.png 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)


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2090
Wohnort: 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 zurück aufdröseln... 4Y+1=25, Y=6,Z=5 14*6+1=5*17,Z=17 14*Y+1=19*17,Y=23 33*23+1=19Z,Z=40 33Y+1=52*40,Y=63 85*63+1=52Z,Z=103 85Y + 1 = 137*103,Y=166 222*166 + 1 = 137 Z,Z=269 222 Y + 1 = 803*269,Y=973 3434*973 + 1 = 803 Z,Z=4161 3434 Y + 1 = 7671 * 4161,Y=9295 26447*9295 + 1 = 7671 Z,Z=32046 26447 Y + 1 = 34118*32046,Y=41341 231155*41341 + 1 = 34118 Z,Z=280092 231155 Y + 1 = 43722413 * 280092,Y=52978729 87675981*52978729 + 1 = 43722413 Z,Z=106237550 87675981 Y + 1 = 394426337*106237550,Y=477928929 876528655*477928929 + 1 = 394426337 Z,Z=1062095408 876528655 Y + 1 = 2147483647*1062095408,Y=2602119745 67448521712*2602119745 + 1 = 2147483647 Z,Z=81727807503,Y=2602119745 Normierung rückgängig 67448521712*2602119745 + 1 = 2147483647*81727807503, hier X=1 Für X=18910800480: Y=(18910800480*2602119745) MOD 2147483647 = Y = 521818456 18910800480 + 67448521712*521818456 = Z * 2147483647 ist zu lösen ! Z=16389360416 Somit wäre schnell gezeigt, dass (16389360416 * 630360016) modulo 2147483647 = 1620212934 ist und ...da haut was noch nicht hin 🤔 Ah, ich habs ! ((30+107Y) * 630360016) modulo 2147483647 = 0 18910800480 + 67448521712*521818456=((30+107Y) * 630360016) Y=55834574822 Y MOD 107+6=36...eine Lösung 🙂


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1596
  Beitrag No.4, vom Themenstarter, eingetragen 2020-05-18

Eigentlich suche ich ja den Startwert so, dass nach der 33 nicht 24,70,... sondern 18, 111,... kommen soll :-) Ich habe schon zig "Tricks" eingebaut, damit die Suche 1000 mal schneller wird, aber nach 2 Tagen noch immer nix...


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2090
Wohnort: Thüringen
  Beitrag No.5, eingetragen 2020-05-18

Das war jetzt sehr mühselig, aber ich habe gezeigt, das durchaus 2 Bedingungen erfüllt werden können ...und somit beliebig viele. Hier eben für Y=55834574822 55834574822 % 107 +6 =36 und (55834574822 * 630360016) % 2147483647 =0 Sollte es mir gelingen , mehrere zu Verknüpfen....naja, a[0] wird aber extrem groß, wenn immer mehr passen sollen. Wieso eigentlich dies ?


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1596
  Beitrag No.6, vom Themenstarter, eingetragen 2020-05-19

Hallo pzktupel, zwar hast Du 1 einziges Glied kompliziert berechnet, ABER die wichtigste Randbedingung vergessen: \sourceon JavaScript aB[i] > 0 \sourceoff Das bringt die Iteration in einen Zustand, der nur noch 0 erzeugt: Iterationsrechner Kontrolle https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_It_Norman000.png Ich habe mein Suchprogramm nochmals optimiert und stelle die Lösung im nächsten Beitrag vor.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1596
  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: b=aB[0]=468606286018 Iterationsrechner rechnet alles online vor https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_It_Pseudozufall_Loesung.png Und noch zum Hintergrund: Dieser Generator kann im Gegensatz zu anderen Interpolations-Algorithmen über 1 Mrd. Folgeglieder blitzschnell erzeugen, ohne eine PERIODE aufzuzeigen: \sourceon nameDerSprache 36,30,6,108,33,18,111,53,22,110,167,197,138,44,160,169,110,178,48,142,129,69,198,182,119,109,123,27,43,162,130,87,180,195,102,23,149,66,23,26,9,106,8,140,180,64,61,124,20,85,80,174,37,127,49,115,148,125,124,164,34,90,49,132,112,120,159,128,168,43,73,78,14,21,7,199,62,43,118,100,205,30,130,42,154,159,110,78,16,179,86,169,12,75,90,122,181,66,18, \sourceoff - 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!


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1596
  Beitrag No.8, vom Themenstarter, eingetragen 2020-05-19

2 weitere Lösungen hier.


   Profil
hyperG hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]