Laufzeit Zufallszahlen

05.11.2010, 13:12	minimammut	Auf diesen Beitrag antworten »
Laufzeit Zufallszahlen Meine Frage: Hey, ich habe ne Aufgabe aus nem Buch, zu der ich keine Lösung habe und mir nicht sicher bin, ob ich es richtig gelöst habe. Außerdem komme ich an einer bestimmten Stelle nicht weiter... Hier die Aufgabe: Schreibe eine Methode RANDOM(a, b), die eine Zufallszahl zwischen a und b (inklusive) ausgibt, und dabei nur RANDOM(0,1) benutzt. Wie ist die erwartete Laufzeit der Methode als Funktion von a und b? Jede der Zahlen zwischen a und b soll mit gleicher Wahrscheinlichkeit auftreten. Meine Ideen: Also meine Methode sieht so aus: (log=zur Basis 2) RANDOM(a,b){ max=b-a r=0 for(i=0;i<ceil(log(max));i++){ r+=RANDOM(0,1)2^i } if(r<=max){ return r+a; }else{ return(RANDOM(a,b) } } (oh gott ist das Code posten hier furchtbar - was mach ich falsch?) Ich glaube das müsste soweit passen. (Oder sind nicht alle gleich wahrscheinlich?^^) Nun zur Laufzeit: Die Zeile r+=... hat wohl konstante Laufzeit (das 2^ist ja nur ein Bitshift) Also kommt man für den ersten Teil auf ceil(log(b-a) Soweit so gut, der zweite Teil ruft ja evt. das ganze nochmal auf, mit der Wahrscheinlichkeit, die dem Anteil der Zahlen entspricht, die größer sind als max und sich mit ceil(log(max)) Bits darstellen lassen. Ich komme also auf folgende Formel: $\begin{eqnarray} \sum\limits_{k=0}^\infty ((\frac{2^{ceil(log(b-a))}-1-b+a }{2^{ceil(log(b-a))}-1})^{k}ceil(log(b-a))) \end{eqnarray}$ Stimmt das so erstmal für die Laufzeit? Ist ja ein bisschen hässlich so, wie lässt sich das weiter vereinfachen? Und wie komme ich auf eine sinnvolle asymptotische Angabe? Vielen Dank schonmal! PS: Nein, ihr macht nicht meine Hausaufgaben, ich bin kein Student sondern mach das nur aus Spaß an der Freude;-)
05.11.2010, 14:41	kiste	Auf diesen Beitrag antworten »
Deinen Code verstehe ich nicht. Du rufst in der Methode die Methode rekursiv wieder auf, ohne die Parameter geändert zu haben? Warum setzt du nicht $\begin{eqnarray} \mathrm{random}(a,b) = a + (b-a)\mathrm{random}(0,1) \end{eqnarray}$ ?
05.11.2010, 14:47	minimammut	Auf diesen Beitrag antworten »
ja genau das tue ich. Es ist ja Zufall im Spiel, sodass nicht unbedingt das Gleiche passiert. Die Sache ist die: Wenn ich zum Beispiel eine Zahl zwischen 0 und 6 generieren soll, kann es mit der Methode das sozusagen in der Binärdarstellung zu machen ja passieren, dass eine 7 rauskommt (weil ja ceil(log(6))=3 ist und 2^3 =8) In diesem Fall wird die Methode einfach erneut aufgerufen. edit: Deinen Vorschlag verstehe ich wiederum nicht, das würde doch heißen dass RANDOM(a,b) nur a oder b sein könnte...
05.11.2010, 15:21	kiste	Auf diesen Beitrag antworten »
Ah, random(0,1) ist ein Zufallsbit. Ich dachte es wäre eine zufällige Zahl zwischen 0 und 1. Insbesondere willst du also nur ganze Zahlen. Warum teilst du durch 2^(...)-1 in der Summe und nicht durch 2^(...)? Ansonsten kannst du das ganze mit der Summenformel für die geometrische Reihe vereinfachen: $\begin{eqnarray} \sum_{k=0}^\infty q^k = \frac{1}{1-q} \end{eqnarray}$ für $\begin{eqnarray} \|q\|<1 \end{eqnarray}$
05.11.2010, 18:16	minimammut	Auf diesen Beitrag antworten »
achja sry, nur ganze Zahlen, hatte ich vergessen zu schreiben. ja, die -1... hab nochmal drüber nachgedacht und festgestellt, dass ich n Fehler im Algorithmus habe... da ja a und b inklusive sind, sind es b-a+1 verschiedene Zahlen die vorkommen können. Ich muss also in der Schleife und dann auch in der Funktion jeweils bis ceil(log(b-a+1)) gehen. Damit ist die -1 im Nenner gerechtfertigt, die im Zähler ist wie du richtig festgestellt hast wohl falsch. Die neue Laufzeit heißt also: $\begin{eqnarray} \sum\limits_{k=0}^\infty ((\frac{2^{ceil(log(b-a+1))}-1-b+a }{2^{ceil(log(b-a+1))}})^{k}ceil(log(b-a+1))) \end{eqnarray}$ OK mit der Summenformel komme ich dann auf: $\begin{eqnarray} ceil(log(b-a+1))\frac{1}{1-\frac{2^{ceil(log(b-a+1))}-1-b+a }{2^{ceil(log(b-a+1))}}} \end{eqnarray}$ da die $\begin{eqnarray} \frac{2^{ceil(log(b-a+1))}-1-b+a }{2^{ceil(log(b-a+1))}} \end{eqnarray}$ ja der Teil der erzeugten Zahlen sind die nicht passen, und $\begin{eqnarray} \frac{b-a+1}{2^{ceil(log(b-a+1))}} \end{eqnarray}$ der Teil der durchgeht, lässt es sich vereinfachen in: $\begin{eqnarray} ceil(log(b-a+1))\frac{2^{ceil(log(b-a+1))}}{b-a+1} \end{eqnarray*}$ weiter komme ich erstmal nicht, sieht ja aber schon ein bisschen angenehmer aus! passt das soweit? geht da noch mehr? Und wie siehts mit sinnvollen asymptotischen Betrachtungen aus? Vielen Dank schonmal!
05.11.2010, 18:24	kiste	Auf diesen Beitrag antworten »
Ich hab jetzt nicht jeden Rechenschritt überprüft, könnte also irgendwo ein $\begin{eqnarray} \pm 1 \end{eqnarray}$ falsch sein, aber das macht asymptotisch sowieso nichts aus. Der zweite Term ist ungefähr 1, bis auf eine kleine Konstante(so um die maximal Faktor 1/2 bis Faktor 2). Das Abrunden kannst auch ignorieren. Also hast eine erwartete Laufzeit von $\begin{eqnarray} \mathcal O(\log(b-a+1)) \end{eqnarray}$
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »