zufallszahlen

Tim schrieb:

Wichtig ist das Konzept.

deshalb frage ich mich ja, was du gegen modulo hast. wenn mich nicht alles täuscht, ist rand() umso 'zufälliger', je mehr der unteren bits man behält, und nicht wegdividiert und -shiftet, so wie bei deinen zweifelhaften beispielen.

~fricky schrieb:

Tim schrieb:

Wichtig ist das Konzept.

deshalb frage ich mich ja, was du gegen modulo hast. wenn mich nicht alles täuscht, ist rand() umso 'zufälliger', je mehr der unteren bits man behält, und nicht wegdividiert und -shiftet, so wie bei deinen zweifelhaften beispielen.

a) Modulo (wenn nicht gerade mit 2^x verwendet) erzeugt eine Ungleichverteilung (siehe z.B. Marcus Artikel zum Zufall)
b) Nein, gerade die unteren Bits sind/waren typischerweise die "schlechten" Bits.

Korhil

pointercrash() schrieb:

SG1 schrieb:

hellijhb's Lösung würde in dem Fall nur die zweite Zahl verwerfen, marge's Lösung würde BEIDE Zahlen verwerfen. Und das wirkt sich selbstverständlich auf die Gesamtverteilung aus, wie Korhil schon ausgeführt hat.

Himmelherrgot, gebt Verstand herab vom Himmel!
Lernt ihr denn gar nix mehr in der Schule?
Es ist doch kackegal, ob eine oder zwei oder alle Zahlen verworfen werden. Closed is closed.
Bitte nehmt mal einen Bronstein zur Hand, ich hab' versucht, das trivial zu erklären, vielleicht war das einfach nicht trivial genug. Viel besser krieg' ich das aber nicht hin:
Du hast eine gleichmäßige Verteilung der Ereignisse mit 1/n. Unterereignisse haben nur Einfluß, wenn Du Zurücklegen berücksichtigst. Ist aber bei der Aufgabenstellung nicht der Fall.
Vor dem Antworten BITTE Nachdenken.

Entschuldige, das ich wohl so schwer von Begriff bin, aber wenn ich das mal durchspiele mit 100.000 Durchläufen erhalte ich folgende Durchschnittswerte:

Lösung marge:
z1 = 8,26
z2 = 8,23
z3 = 8,25

andere Lösung:
z1 = 16,47
z2 = 8,28
z3 = 4,13

Ich glaub, ich hab in der Schule gelernt, das das nicht mal annähernd das gleiche (oder zumindest ähnliche) ist. Mit Zufall kann man sich da wohl auch nicht rausreden, oder ?

pointercrash**

Korhil schrieb:

Ich glaub, ich hab in der Schule gelernt, das das nicht mal annähernd das gleiche (oder zumindest ähnliche) ist. Mit Zufall kann man sich da wohl auch nicht rausreden, oder ?

"Auch große Geister haben nur ihre fünf Finger breite Erfahrung, - gleich daneben hört ihr Nachdenken auf: und es beginnt ihr unendlicher leerer Raum und ihre Dummheit." - Friedrich Nietzsche

OK, ich gieße das jetzt auch in Code, als Nachdenkhilfe ... gebt mir ein paar Minuten Zeit ...

Tim schrieb:

b) Nein, gerade die unteren Bits sind/waren typischerweise die "schlechten" Bits.

ach, so rum war das. ok, das erklärt ein wenig deine zahlen-trickserei.
http://en.wikipedia.org/wiki/RANDU

pointercrash**

Korhil schrieb:

Ich glaub, ich hab in der Schule gelernt, das das nicht mal annähernd das gleiche (oder zumindest ähnliche) ist. Mit Zufall kann man sich da wohl auch nicht rausreden, oder ?

Wenn jeder deine Dummheit kennt, dann bist du endlich prominent. - Erhard H. Bellermann

OK, dann habe ich in der Bekanntheitsskala noch zugelegt, ihr habt recht und ich nicht, ich kriege die Mathe nur noch nicht auf die Reihe, d.h. mir ist es noch nicht ganz klar, den Abschnitt im Bronstein kapier' ich nicht und ich werde wohl ein paar alte Uni- Scripten mit aufs Klo nehmen müssen.

Also tatsächlich führt die Einengung des Ereignisraums zu einer Verzerrung Richtung niedriger Zahlen. Morgen dann mehr für alle, die's genau wissen wollen.

Aber erstmal Abbitte Richtung Korhil&Co

meine meinung zu dem ergebnis von hellihjbs lösung:

die erste zahl z1 ist gleichverteilt auf den gesamten zahlenraum. im durchschnitt wird z1 somit den wert ~16 haben. somit bleibt für z2 + z3 im schnitt ein wertebereich von ~16 übrig, den sie sich teilen müssen.

nun kommt z2 an die reihe, nachdem z1 ermittelt wurde. z2 wird im schnitt somit mit 0 - 16 auskommen müssen - was wiederum im mittel den wert 8 ergibt.

dann bleibt noch z3 übrig. für z3 bleibt im schnitt der wertebereich von 0 bis 8 - was wiederum im mittel 4 ergibt.

somit hat die lösung im mittel z1 > z2 > z3

das ganze tritt bei der ursprünglichen lösung des OPs nicht auf, da in dem fall z1, z2 und z3 nicht abhängig voneinander sind.

pwr schrieb:

das ganze tritt bei der ursprünglichen lösung des OPs nicht auf, da in dem fall z1, z2 und z3 nicht abhängig voneinander sind.

aber er hat 'ne schleife drin, die unvorhersehbar oft rumeiert.
wie wär's mit sowas?

int a = rand();
  int b = rand();
  int c = rand();
  int div = (a+b+c)/34;
  a = a / div;
  b = b / div;
  c = c / div;

dürfte doch die anforderung erfüllen, dass die summe nicht grösser als 33 sein darf, oder?

Korhil

~fricky schrieb:

pwr schrieb:

das ganze tritt bei der ursprünglichen lösung des OPs nicht auf, da in dem fall z1, z2 und z3 nicht abhängig voneinander sind.

aber er hat 'ne schleife drin, die unvorhersehbar oft rumeiert.
wie wär's mit sowas?
int a = rand();
  int b = rand();
  int c = rand();
  int div = (a+b+c)/34;
  a = a / div;
  b = b / div;
  c = c / div;
dürfte doch die anforderung erfüllen, dass die summe nicht grösser als 33 sein darf, oder?

Ich würde dem jetzt auf die Schnelle mal wiedersprechen, da bei einem kurzen Test zu hohe Durchschnittswerte (10,xx) raus kamen.

Korhil schrieb:

Ich würde dem jetzt auf die Schnelle mal wiedersprechen, da bei einem kurzen Test zu hohe Durchschnittswerte (10,xx) raus kamen.

den kannst du ja zurechtbiegen, z.b. indem du den drei 'rands' wieder ein mod(irgendwas) verpasst. (und dafür sorgst, dass 'div' nicht 0 wird).

pointercrash**

Hallo Leute,

sorry, wegen Zeitmangels erst jetzt Rückmeldung. Also, ich hab's eingesehen, daß helihjbs "Lösung" eine unzulässige Verteilung herbeiführt, weil die Würfe eben nicht mehr unabhängig sind.
Ich hab' jetzt ein wenig herumgebosselt und das da fabriziert:

#include <stdlib.h>
#include <math.h>

int main(void);
        const unsigned long int wuerfe = 1000000;
        #define  N 33
        #define  N1 34

int random (int max) 
        {
                return rand() / (RAND_MAX / max + 1); // [0... max]
        }

int main(void)
{

        unsigned int  summe, rest, z1, z2, z3, i;
        double abweichung;
        unsigned long int geworfen,a,b;
        unsigned long int heli[N1];
        unsigned long int marge[N1];
        unsigned long int imarge[N1];
        unsigned long int sum_heli = 0;
        unsigned long int sum_marge = 0;
        unsigned long int sum_imarge = 0;

        for (i = 0; i<(N1); i++)
        {
                heli[i] = 0;
                marge[i] = 0;
                imarge[i] = 0;
        }

        srand(12);

// Heli- Section
        printf("Running Heli\n");
        srand(12);
        geworfen = 0;
        do
        {
                rest = N;
                z1 = random(rest);
                heli[z1]++;
                rest -= z1;
                z2 = random(rest);
                heli[z2]++;
                rest -= z2;
                z3 = random(rest);
                heli[z3]++;
                geworfen++;
        }
        while (geworfen < wuerfe);

// marge- Section
        printf("Running marge\n");
        srand(12);
        geworfen = 0;
        do
        {
                do
                {
                        z1 = random(N);
                        z2 = random(N);
                        z3 = random(N);
                        summe = z1 + z2 +z3;
                }
                while (summe > N);
                marge[z1]++;
                marge[z2]++;
                marge[z3]++;
                geworfen++;
        }
        while (geworfen < wuerfe);

// improved marge- Section
        printf("Running improved marge\n");
        srand(12);
        geworfen = 0;
        z1 = random(N);
        z2 = random(N);
        do
        {
            /*
            z1 = random(N);
            // z2 = random(N);
            do
            {
                z2 = z1;
                z1 = random(N);
                summe = z1 + z2;             
            }
            while (summe > N);
           */
            do
            {
                 z3 = z2;
                 z2 = z1;
                 z1 = random(N);
                // z1 = random(N);
                // z2 = random(N);
                // z3 = random(N);
                summe = z1 + z2 + z3;                  

            }
            while (summe > N);

                imarge[z1]++;
                imarge[z2]++;
                imarge[z3]++;
                geworfen++;
                // z1 = random(N);
                // z2 = random(N);
        }
        while (geworfen < wuerfe);

        // Auswertung
        // Kontrolle: Wurffehler vermeiden
       for (i = 0; i<(N1); i++)
        {
                sum_heli += heli[i];
                sum_marge += marge[i];
                sum_imarge += imarge[i];
        }

                printf("%u heli \n", sum_heli);
                printf("%u marge \n", sum_marge);
                printf("%u imarge \n", sum_imarge);

        // Abweichungen in % ermitteln
        for (i = 0; i<(N1); i++)
        {
                a = marge[i];
                b = heli[i];
                abweichung = (double)b - (double)a;
                abweichung = 100.0/(double)marge[i] * abweichung;
                printf("Bei %u heli zu marge %f%%,", i, abweichung);
                b = imarge[i];
                abweichung = (double)b - (double)a;
                abweichung = 100.0/(double)marge[i] * abweichung;
                printf(" imarge zu marge %f%% \n", abweichung);
        }
        return 0;
}

Stört euch nicht an unnötigen Deklarationen, ist nur, damit man im Debugger bequem Watches anlegen kann.
Was mir an Helis Lösung gefallen hat, war, daß man nichts verwirft, das hat mich wohl betriebsblind gemacht.
Ich habe das (Nicht-) Verwerfen zu optimieren versucht und die imarge- Methode entworfen, zunächst indem ich den dritten Wurf erst gar nicht ausgeführt habe, wenn man schon über 33 ist und nachfolgend den dritten Wurf nachgeschoben habe, bis das Ergebnis paßt.

Aber jetzt wird's strange:
- ich habe srand jeweils mit einer seed von 12 gesetzt, damit ich immer den gleichen "Zufall" habe. Nur, wenn ich den imarge- Block durch die astreine marge- Methode ersetze, weichen die Ergebnisse immer noch voneinander ab. Dürfte doch eigentlich nicht sein, oder?
- Daß Heli einfährt, ist unbestreitbar, aber mit nach zwei Würfen Nachschauen (Summe kontrollieren) und neu beginnen habe ich auch Schiffbruch erlitten. Um die 11% Abweichung für die Null war die Folge.
- Rein jeweils einen Wert nachschieben, so, wie es jetzt dasteht, führt zu gleichen Ergebnissen wie zwei marge- Blöcke, ABER wenn ich die vorherigen Würfe NICHT verwerfe (Kommentierung Z. 113/114 aufheben), um neue Würfe zu laden, ergibt sich das gleiche Bild, wie nach zwei Würfen ggf. zu verwerfen.

Kann das jemand erklären? Für heute bin ich zu müde, frickys Methode zu testen, dürfte aber eigentlich probat sein.

Noch was: Ich habe jetzt Pelles C als q&d- Fab getestet, diesen Code frißt es aber nicht, wurde stattdessen mit dem Watcom und einem embedded Compiler getestet. Pelle stört sich daran, daß beim Linken z.B. _rand als externes Symbol nicht aufgelöst werden konnte. Weiß jemand wass dazu?

vlad_tepesch

frickys ansatz sieht recht nett aus, jedoch haben die zahlen immer eine summe von 33, die aufgabe war jedoch kleiner (gleich?) 33
dann is da noch das problem mit dem abrunden bei integer divisionen.
ich würde folgendes machen:

int sum = rand()%34; //34 oder 33)
  int a = rand();
  int b = rand();
  int c = rand();
  float div = ((float)(a+b+c))/sum;
  a = (int)(0.5 + a / div);
  b = (int)(0.5 + b / div);
  c = (int)(0.5 + c / div);

pointercrash**

vlad_tepesch schrieb:

frickys ansatz sieht recht nett aus, jedoch haben die zahlen immer eine summe von 33, die aufgabe war jedoch kleiner (gleich?) 33
... ich würde folgendes machen:
int sum = rand()%34; //34 oder 33)
  int a = rand();
  int b = rand();
  int c = rand();
  float div = ((float)(a+b+c))/sum;
  a = (int)(0.5 + a / div);
  b = (int)(0.5 + b / div);
  c = (int)(0.5 + c / div);

Jetzt bist Du ins gleiche Messer gelaufen wie ich. Die Summen sind nicht gleichmäßig verteilt, man darf sich eben nicht auf einer gleichmäßigen Verteilung basierend die vorherigen Ereignisse zurechtschnitzen.
Und leider auch nicht auf die Zielsumme zusammenhämmern, das gilt für frickys Lösung genauso.
Schaut euch nochmal das da an:

srand(12);
        geworfen = 0;
        z1 = random(N);
        z2 = random(N);
        do
        {

            do
            {
                 z3 = z2;
                 z2 = z1;
                 z1 = random(N);
                summe = z1 + z2 + z3;                    
            }
            while (summe > N);

                imarge[z1]++;
                imarge[z2]++;
                imarge[z3]++;
                geworfen++;
                // z1 = random(N);
                // z2 = random(N);
        }
        while (geworfen < wuerfe);

Die Verteilung ist genauso wie bei der richtigen Ur- Lösung. Nachteil ist, daß dabei Zahlen aus einem gültigen 3er- Wurf im nächsten weiterverwendet werden. Auf den Zeilen 21/22 habe ich z1 und z2 daher neu angelegt. Lustigerweise ändert sich dann aber die Verteilung für ein paar Zahlen über 10% gegenüber der richtigen Lösung.
Das verstehe ich nicht.

pointercrash() schrieb:

man darf sich eben nicht auf einer gleichmäßigen Verteilung basierend die vorherigen Ereignisse zurechtschnitzen.
Und leider auch nicht auf die Zielsumme zusammenhämmern

aber wie willste es sonst machen? die 'zufallswerte' sind wegen dieser forderung, dass alle zusammen nicht grösser als 34 sein dürfen, immer irgendwie voneinander abhängig. also kann man da nix berechnen, ohne die summe zu beachten. es bleibt also nur das rumprobieren in einer schleife (der code des OP, alles andere hier ist mist). naja, ich persönlich finde schleifen und 'floats' doof für sowas. aber anscheinend geht's nicht besser, oder?

pointercrash**

~fricky schrieb:

... naja, ich persönlich finde schleifen und 'floats' doof für sowas. aber anscheinend geht's nicht besser, oder?

Mich hat das viele Weggeschmeiße gestört, das Float- Zeugs sowieso. Bei einmal ist es egal, aber wenn man mal 10 Mio mal würfelt, dauert das doch.
Aber hast Du meinen letzten Codeschnipsel angesehen? Der liefert die gleiche Verteilung ab, wie der Code des OP und ist deutlich schneller. Komischerweise driftet aber die Verteilung weg, wenn man nach einem erfolgreichen Wurf z1 und z2 neu besetzt.

pointercrash() schrieb:

Aber hast Du meinen letzten Codeschnipsel angesehen? Der liefert die gleiche Verteilung ab, wie der Code des OP und ist deutlich schneller.

klar, du rufst pro schleifendurchlauf nur einmal rand auf, während der OP immer alle 3 werte neu erzeugen lässt. ist 'ne optimierung, aber eigentlich das gleiche, nämlich rumprobieren in einer schleife

pointercrash() schrieb:

Komischerweise driftet aber die Verteilung weg, wenn man nach einem erfolgreichen Wurf z1 und z2 neu besetzt.

finde ich auch seltsam...

vlad_tepesch

@pointercrash ein anderes Problem bei dir ist, das du im 2. wurf immer die zahlen des voherigen mitbenutzt.

so wärs richtiger:

for(int i=0; i< wuerfe; ++i)
  {
      at = random(N);
      bt = random(N);
      ct = random(N);
      while (at+bt+ct > N)
      {
        ct = bt;
        bt = at;
        at = random(N);
      }
  }

Is aber auch nicht gleichverteilt, wie übrigens marges erster ansatz auch nicht!

Ich habe aber die Lösung:

at = random(6);
      bt = random(6);
      ct = random(6);

Die summe (a+b+c) ist kleiner 33 und die zahlen a, b und c sind gleichverteilt!

Es ist nicht möglich eine gleichverteilung zu erreichen, wenn jede zahl im Bereich 0-33 liegt. das ist, als wenn man mit 2 würfeln würfelt und bei summe > 6 neu würfelt.
da werden die niedrigeren Würfelaugen öfter liegen bleiben

Korhil

vlad_tepesch schrieb:

@pointercrash ein anderes Problem bei dir ist, das du im 2. wurf immer die zahlen des voherigen mitbenutzt.

so wärs richtiger:
for(int i=0; i< wuerfe; ++i)
  {
      at = random(N);
      bt = random(N);
      ct = random(N);
      while (at+bt+ct > N)
      {
        ct = bt;
        bt = at;
        at = random(N);
      }
  }
Is aber auch nicht gleichverteilt, wie übrigens marges erster ansatz auch nicht!

Ich habe aber die Lösung:
at = random(6);
      bt = random(6);
      ct = random(6);
Die summe (a+b+c) ist kleiner 33 und die zahlen a, b und c sind gleichverteilt!

Es ist nicht möglich eine gleichverteilung zu erreichen, wenn jede zahl im Bereich 0-33 liegt. das ist, als wenn man mit 2 würfeln würfelt und bei zahlen > 6 neu würfelt.
da werden die niedrigeren Würfelaugen öfter liegen bleiben

Du mußt dich - denke ich - von der klassischen Normalverteilung gedanklich verabschieden. Hier liegt ein anderes Problem vor, so dass die Normalverteilung hier halt anders aussieht. Trotzdem gibt es die Normalverteilung zu diesem Problem.

vlad_tepesch

wer will denn eine Normalverteilung?
eine gleichverteilung war das ziel!

hat nicht mal einer von euch lust, was mit logikoperatoren zu machen. 33 ist ja immerhin ganz nah an 2^5. vielleicht geht da was.