Kongruenzmethode < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:49 So 26.04.2009 | | Autor: | alex84hh |
| Aufgabe | Mit Z0=15 (Anfangswert), a=5 (Multiplikator), M=16 (Divisor) ernthält man folgende Zahlenfolge:
Z1=5*15(mod 16)=75:16=4 Rest 11
Z2=5*11(mod 16)=55:16=3 Rest 7
usw.. |
So, nun meine Frage..
Könnte mir bitte jemand vereinfacht erklären, wie man auf Rest 11 und Rest 7 kommt??
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Lg Alex
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:55 So 26.04.2009 | | Autor: | konvex |
hi,
Z1=5*15(mod 16)=75:16=4 Rest 11
75:16= 4,68, dh. die 16 passt 4 mal in die 75 rein, aber 16*4=64 also hast du den rest 11 damit du auf 75 kommst.
dh. 16*4+11=75
Z2=5*11(mod 16)=55:16=3 Rest 7
hier das gleiche:
55:16=3,43 dh. die 16 passt 3 mal in die 55 rein, aber 16*3=48 also hast du den rest 7 damit du auf 55 kommst.
dh. 16*3+7=55
hoffe das hilft dir weiter 
mfg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:25 So 26.04.2009 | | Autor: | alex84hh |
Super.. Dankeschön
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:20 Mo 27.04.2009 | | Autor: | alex84hh |
Soo.. Versuche nun anhand der gewonnenen Zufallszahlen, die ich mit der linearen Kongruenzmethode erstellt habe, [mm] \pi [/mm] via excel zu berechen..
Meine Frage nun.. Mein Anfangswert ist 1, Miltiplikator 24298 , +99991 und Divisor 199017.. damit bekomme ich auch "einige" Zufallszahlen (wenn ich richtig verstanden habe sind sie gleichverteilt).. Mein Problem ist nun, das ich aber Zahlen zw. 0 und 1 brauche.. Ist diese Methode überhaupt geeignet dazu??
Lg Alex
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:33 Di 28.04.2009 | | Autor: | felixf |
Hallo Alex
> Soo.. Versuche nun anhand der gewonnenen Zufallszahlen, die
> ich mit der linearen Kongruenzmethode erstellt habe, [mm]\pi[/mm]
> via excel zu berechen..
> Meine Frage nun.. Mein Anfangswert ist 1, Miltiplikator
> 24298 , +99991 und Divisor 199017.. damit bekomme ich auch
> "einige" Zufallszahlen (wenn ich richtig verstanden habe
> sind sie gleichverteilt).. Mein Problem ist nun, das ich
> aber Zahlen zw. 0 und 1 brauche.. Ist diese Methode
> überhaupt geeignet dazu??
Wenn du Zahlen zwischen $0$ und $n$ hast und Zahlen zwischen $0$ und $1$ brauchst, teile die Zahlen doch einfach alle durch $n$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:06 Di 28.04.2009 | | Autor: | konvex |
wenn du einfach 0,.... davor setzt bekommst du auch zahlen zw. 0 und 1
so haben wir das oft gemacht.
mfg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:12 Di 28.04.2009 | | Autor: | felixf |
Hallo
> wenn du einfach 0,.... davor setzt bekommst du auch
> zahlen zw. 0 und 1
> so haben wir das oft gemacht.
Da muss man aber aufpassen, dass sich die Verteilung nicht aendert. Weil so werden z.B. niemals die Zahlen 0.01, 0.02, 0.03, ..., 0.09 vorkommen, aber 0.10, 0.11, 0.12, ...,0.99.
Besser ist es schon die Zahlen durch die maximal vorkommende Zahl zu teilen; dann ist das Ergebnis wenigstens genauso gut (oder schlecht) in etwa gleichverteilt wie die Zahlen vorher auch.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:50 Di 28.04.2009 | | Autor: | alex84hh |
Um [mm] \pi [/mm] zu berechnen, brauche ich ja X und Y.. Kann man (darf man) Y mit einer anderen Auwahl der Größen a,m,Z0 berechnen, statt die Größen wie ich das für X gewählt habe? Und um eine gute Näherung zu [mm] \pi [/mm] zu bekommen, dachte ich an ca 10000 erzeugten Zufallszahlen (jeweils für X und Y).. Bin ich auf dem richtigen Weg???
Weiß jmd. welcher Algorithmus in Excel in der Funktion Zufallszahl() verwendet wird?
Lg Alex
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:06 Di 28.04.2009 | | Autor: | felixf |
Hallo!
> Um [mm]\pi[/mm] zu berechnen, brauche ich ja X und Y.. Kann man
> (darf man) Y mit einer anderen Auwahl der Größen a,m,Z0
> berechnen, statt die Größen wie ich das für X gewählt habe?
Kannst/darfst du machen. Es reicht auch einen anderen Startwert zu waehlen.
> Und um eine gute Näherung zu [mm]\pi[/mm] zu bekommen, dachte ich an
> ca 10000 erzeugten Zufallszahlen (jeweils für X und Y)..
> Bin ich auf dem richtigen Weg???
Ja.
> Weiß jmd. welcher Algorithmus in Excel in der Funktion
> Zufallszahl() verwendet wird?
Vermutlich etwas aehnliches. Oder auch etwas ausgekluegelter. Es gibt eine Menge von verschiedenen Zufallsgeneratoren, ein recht guter ist der ![[]](/images/popup.gif) Mersenne-Twister.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:22 Di 28.04.2009 | | Autor: | alex84hh |
Hallo Felix..
Danke, das du mir behilflich bist..
Der von dir vorgeschlagene Generator ist nach der Beschreibung wirklich gut. Mein Problem ist aber, dass ich eine Hausarbeit in Operations Research schreibe und das Thema Simulation habe.
Dazu gehört es auch einen Zufallsgenerator zu beschreiben/ erklären sowie die Monte-Carlo Methode.
Der Mersenne-Twister Algorithmus ist aber nach dem ersten Eindruck eine Nummer zu hoch für mich:) ..
Meine Idee war es, dass ich einen Zufallsgenerator aussuche und mit den daraus gewonnenen Zufallszahlen die Näherung zu [mm] \pi [/mm] anhand der Monte-Carlo Methode (Hit-Or-Miss) erläutere..
Nach einigen Recherchen im Internet habe ich mich für die Kongruenz Methode aufgrund der "einfachheit" ertschieden. Doch im nachhinein bekomme ich Zweifel ob es sinnvoll ist so einen Generator vorzustellen da er nicht so "gut" ist.
Zurück zu deinem vorgeschlagenen Generator. Im Artikel habe ich gelesen das es noch einen sogenannten kleinen Bruder gibts, den TT800.. Vielleicht kann mir jemand (falls es geht) den Algorithmus dazu veständlich erklären, sodass ich selbstständig Zufallszahlen erzeugen kann und ich bei der Presentation meiner Hausarbeit auch meinen Komilitonen erklären kann.
Könnte man den Algorithmus auch in Excel VBA imlementieren?
LG Alex
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:35 Mi 29.04.2009 | | Autor: | felixf |
Hallo Alex
> Danke, das du mir behilflich bist..
> Der von dir vorgeschlagene Generator ist nach der
> Beschreibung wirklich gut. Mein Problem ist aber, dass ich
> eine Hausarbeit in Operations Research schreibe und das
> Thema Simulation habe.
> Dazu gehört es auch einen Zufallsgenerator zu beschreiben/
> erklären sowie die Monte-Carlo Methode.
> Der Mersenne-Twister Algorithmus ist aber nach dem ersten
> Eindruck eine Nummer zu hoch für mich:) ..
Er ist auch nicht grad einfach :)
> Meine Idee war es, dass ich einen Zufallsgenerator
> aussuche und mit den daraus gewonnenen Zufallszahlen die
> Näherung zu [mm]\pi[/mm] anhand der Monte-Carlo Methode
> (Hit-Or-Miss) erläutere..
Hoert sich gut an.
> Nach einigen Recherchen im Internet habe ich mich für die
> Kongruenz Methode aufgrund der "einfachheit" ertschieden.
> Doch im nachhinein bekomme ich Zweifel ob es sinnvoll ist
> so einen Generator vorzustellen da er nicht so "gut" ist.
Es geht Fast alle in den verschiedensten Programmiersprachen standardmaessig angebotenen Zufallsgeneratoren sind von dieser Form. Die genauen Parameter sind eventuell verschieden ebenso wie die verwendete Wortbreite, aber das Prinzip ist fast immer das des Kongruenzgenerators.
> Zurück zu deinem vorgeschlagenen Generator. Im Artikel habe
> ich gelesen das es noch einen sogenannten kleinen Bruder
> gibts, den TT800.. Vielleicht kann mir jemand (falls es
> geht) den Algorithmus dazu veständlich erklären, sodass ich
> selbstständig Zufallszahlen erzeugen kann und ich bei der
> Presentation meiner Hausarbeit auch meinen Komilitonen
> erklären kann.
Ich wuerde zumindest im Vortrag den Kongruenzgenerator erklaeren, da er mit Abstand das einfachste ist was man so hat und halt auch der am haeufigsten verwendete ist.
Und zum Thema erklaeren: die Algorithmen fuehren auf einem Zustandsarray eine gewisse Aktion aus um daraus einen neuen Zustandswert zu bekommen (aus diesem Zustandswert wird dann die Zufallszahl gebildet). Dazu werden jeweils ''wild'' aussehende Operationen durchgefuehrt. Wirklich erklaeren kann man da nicht viel, eventuell kann man nachschauen (etwa in den Originalpapern) wie die Autoren auf solche Algorithmen gekommen sind, aber das war's eigentlich auch schon.
Was du eventuell machen koenntest ist manche Operationen vorstellen, die zu einem Zufallsgenerator kombiniert werden koennen, wie etwa
1) Multiplikation und Additionen modulo $n$;
2) Bitweise Operationen (XOR, AND, ...);
3) Bit-Shifts und Rotationen;
4) Verwendung von Tabelllen mit ''obskuren'' Zahlen (wo teilweise niemand ausser den Autoren weiss wo die herkommen) als Parameter fuer obige Operationen;
etc.
Gerade das Mischen der verschiedenen Operationen macht das ganze noch komplizierter und (wenn geschickt gewaehlt) besser.
> Könnte man den Algorithmus auch in Excel VBA
> imlementieren?
Ja. Excel VBA ist Turing-vollstaendig und somit kannst du da alles implementieren, was du auch in anderen Programmiersprachen implementieren kannst
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:09 Sa 06.06.2009 | | Autor: | alex84hh |
Hallo Felix,
Was genau könnte man zu den einzelnen Operationen schreiben..
1) Multiplikation und Additionen modulo m.
2) Bitweise Operationen (XOR, AND, ...).
3) Bit-Shifts und Rotationen.
4) Verwendung von Tabellen mit ''obskuren'' Zahlen (wo teilweise niemand außer den Autoren weiss wo die herkommen) als Parameter für obige Operationen.
5) Etc.
Hatte mir den Algorithmus von Wikipedia (http://de.wikipedia.org/wiki/Mersenne-Twister) angeschaut und folgende Gedanken dazu gemacht.
Als erstes wollte ich den Begriff Operationen klären.. Kann man auch Wirkung oder Aktion sagen??
Zu Punkt 1) h:=Yi-N-Yi-N mod 2^31+Yi-N+1 mod 2^31. Meint man das mit Addition modulo m, da man sieht das die beiden Moduli addiert werden?? Und mit Multiplikation die Formel drunter??
Zu Punkt 2) Ist verständlich.. XOR, AND sind im Algorithmus enthalten.
Zu Punkt 3 und 4) Konnte dazu leider nichts finden.. Wäre nett wenn mir das jemand erläutert.
Punkt 5) Was gibt es da noch unter etc.???
liebe Grüße
Alexander
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:40 Mo 08.06.2009 | | Autor: | felixf |
Hallo Alexander!
> Was genau könnte man zu den einzelnen Operationen
> schreiben..
>
> 1) Multiplikation und Additionen modulo m.
> 2) Bitweise Operationen (XOR, AND, ...).
> 3) Bit-Shifts und Rotationen.
> 4) Verwendung von Tabellen mit ''obskuren'' Zahlen (wo
> teilweise niemand außer den Autoren weiss wo die herkommen)
> als Parameter für obige Operationen.
> 5) Etc.
>
> Hatte mir den Algorithmus von Wikipedia
> (http://de.wikipedia.org/wiki/Mersenne-Twister) angeschaut
> und folgende Gedanken dazu gemacht.
> Als erstes wollte ich den Begriff Operationen klären..
> Kann man auch Wirkung oder Aktion sagen??
> Zu Punkt 1) h:=Yi-N-Yi-N mod 2^31+Yi-N+1 mod 2^31. Meint
> man das mit Addition modulo m, da man sieht das die beiden
> Moduli addiert werden?? Und mit Multiplikation die Formel
> drunter??
Siehe hier. Du fuehrst normale Addition/Multiplikation durch und nimmst das Ergebnis nachher modulo einer Zahl (oft: [mm] $2^{32}$ [/mm] o.ä.).
> Zu Punkt 2) Ist verständlich.. XOR, AND sind im
> Algorithmus enthalten.
> Zu Punkt 3 und 4) Konnte dazu leider nichts finden.. Wäre
> nett wenn mir das jemand erläutert.
Zu 4): hier oder hier.
Zu 3): hier und hier.
> Punkt 5) Was gibt es da noch unter etc.???
Nunja, verschiedene Moeglichkeiten die Zahlen $0, ..., [mm] 2^{32}-1$ [/mm] aufzufassen. Moeglich ist als [mm] $\IZ/2^{32}\IZ$ [/mm] (das ist dann Addition/Multiplikation modulo [mm] $2^{32}$), [/mm] oder als endlichen Koerper mit [mm] $2^{32}$ [/mm] Elementen (Addition ist dann XOR, Multiplikation was komplizierteres), oder als [mm] $\IF_2^6$ [/mm] (das ist dann XOR bzw AND bei Addition bzw. Multiplikation).
Ansonsten sind der Fantasie natuerlich keine Grenzen gesetzt ;)
LG Felix
|
|
|
|
