Antworte auf:  Suche Interpolation per Pseudozufallsgenerator von hyperG
Forum:  Algorithmen / Datenstrukturen, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1243
Herkunft:
 Beitrag No.8, eingetragen 2020-05-19 18:45    [Diesen Beitrag zitieren]

2 weitere Lösungen hier.


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1243
Herkunft:
 Beitrag No.7, eingetragen 2020-05-19 17:30    [Diesen Beitrag zitieren]

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!


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1243
Herkunft:
 Beitrag No.6, eingetragen 2020-05-19 16:58    [Diesen Beitrag zitieren]

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.


pzktupel
Aktiv
Dabei seit: 02.09.2017
Mitteilungen: 1692
Herkunft: Thüringen
 Beitrag No.5, eingetragen 2020-05-18 23:24    [Diesen Beitrag zitieren]

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 ?


hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1243
Herkunft:
 Beitrag No.4, eingetragen 2020-05-18 22:14    [Diesen Beitrag zitieren]

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


pzktupel
Aktiv
Dabei seit: 02.09.2017
Mitteilungen: 1692
Herkunft: Thüringen
 Beitrag No.3, eingetragen 2020-05-18 21:51    [Diesen Beitrag zitieren]

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 🙂



hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1243
Herkunft:
 Beitrag No.2, eingetragen 2020-05-18 21:20    [Diesen Beitrag zitieren]

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)



pzktupel
Aktiv
Dabei seit: 02.09.2017
Mitteilungen: 1692
Herkunft: Thüringen
 Beitrag No.1, eingetragen 2020-05-18 16:37    [Diesen Beitrag zitieren]

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



hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1243
Herkunft:
 Themenstart: 2020-05-14 23:46    [Diesen Beitrag zitieren]

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


 
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]