Matroids Matheplanet Forum Index
Forumbereich moderiert von: matroid
Informatik » Algorithmen / Datenstrukturen » Suche Interpolation per Pseudozufallsgenerator
Druckversion
Druckversion
Antworten
Antworten
Universität/Hochschule Suche Interpolation per Pseudozufallsgenerator
hyperG Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 03.02.2017, Mitteilungen: 1245
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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



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).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 02.09.2017, Mitteilungen: 1697, aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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




-----------------
zum Primzahl k-Tupel Thread
PDFs on "Mathematik alpha"
Hinweis: MP-Notizbuch



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 03.02.2017, Mitteilungen: 1245
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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


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)




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 02.09.2017, Mitteilungen: 1697, aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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 🙂




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 03.02.2017, Mitteilungen: 1245
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 02.09.2017, Mitteilungen: 1697, aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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 ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 03.02.2017, Mitteilungen: 1245
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.6, vom Themenstarter, eingetragen 2020-05-19

Hallo pzktupel,

zwar hast Du 1 einziges Glied kompliziert berechnet, ABER die wichtigste Randbedingung vergessen:
JavaScript
aB[i] > 0

Das bringt die Iteration in einen Zustand, der nur noch 0 erzeugt:
Iterationsrechner Kontrolle



Ich habe mein Suchprogramm nochmals optimiert und stelle die Lösung im nächsten Beitrag vor.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 03.02.2017, Mitteilungen: 1245
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
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



Und noch zum Hintergrund:
Dieser Generator kann im Gegensatz zu anderen Interpolations-Algorithmen über 1 Mrd. Folgeglieder blitzschnell erzeugen, ohne eine PERIODE aufzuzeigen:
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,

- 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!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG Senior Letzter Besuch: in der letzten Woche
Mitglied seit: 03.02.2017, Mitteilungen: 1245
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.8, vom Themenstarter, eingetragen 2020-05-19

2 weitere Lösungen hier.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2020 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]