Zufals-Boolean erzeugen

[tigerman33]

Eine andere Variante, wenn man das Array umgehen will (obwohl das ja auch eine gute Lösung ist) wäre auch folgendes:

Delphi-Quellcode:

ABool := random <= (f - n) / (s - m)

Dabei ist f die Anzahl an trues die man erreichen will, s die Spanne in der das erreicht werden soll (in eurem Beispiel 1000). n und m sind Zählervariablen, in denen die Anzahl an schon erreichten trues bzw. die schon verstrichene Spanne gespeichert wird.

Beispiel: Im 20. von 1000 Würfen, es ist schon 3 mal true gewürfelt worden und soll insgesamt 500 mal true geben:#

ABool := random <= (500 - 3) / (1000 - 19)

[negaH]

Was ist mit

Delphi-Quellcode:

Result := Odd(Random(100));

Gruß Hagen

[Nikolas]

Zitat:

Result := Odd(Random(100));

Es geht schon nicht mehr darum, einen zufälligen Boolean zu bekommen, sondern Möglichkeiten zu garantieren (!) dass True und False gleich oft erscheinen.

// Hast du eigentlich einen Bot, der meldet, wenn in einem Thread eines der Wörter 'Zufallalgorhytmus' oder 'Veschlüsselung' auftaucht? :mrgreen:

[negaH]

Ja und ? Das macht exakt mein Vorschlag, denn der PRNG muß als guter RNG garantieren das er auf lange Sicht gerade und ungerade Zahlen gleichmäßig verteilt.

Davon abgesehen, eine Garantie das man bei 1000 zufällig erzeugten Booleans exakt 50% jeweils TRUE oder FALSE sind kann es bei Zufall eben nicht geben. Dies wäre nämlich nicht mehr zufällig, also ein Widerspruch insich. Entweder will man es zufällig oder nicht.
Eine Folge von 1000 erzeugten TRUE Werten ist zwar sehr unwahrscheinlich aber denoch ein möglicher und gültiger Output eines Zufallsgenerators.

Gruß Hagen

[negaH]

Es besteht aber die Möglichkeit eine solche "Zufallssequenz" ganz einfach zu erzeugen.

Delphi-Quellcode:

var
  LastValue: Boolean;
  LastValid: Boolean := False;

function RandomBoolean: Boolean;
begin
  if not LastValid then
    LastValue := Odd(Ramdom(2));
  Result := LastValue;  
  LastValue := not LastValue;
  LastValid := not LastValid;
end;

Diese Funktion erzeugt Tuples aus TRUE/FALSE bzw FALSE/TRUE Werten zufällig. Ruft man sie also mit geradzahliger Anzahl auf so ist garantiert das 50% TRUE/FALSE sind. Der maximale Abstand zwischen zwei TRUE bzw FALSE Werten beträgt 2.

Aus dieser kleinen Funkton lässt sich sehr einfach mathematisch ableiten das wenn man längere uniforme Abstände erreichen möchte sich die WorstCase-Gleichverteilung immer weiter von 50% entfernen muß. Und bei "echt" zufälligen Sequenzen die mathematisch mögliche WorstCase-Gleichverteilung exakt einer unendlich langen Sequenz sein muß. Heist auch eine unendlich lange Sequenz aus lauter TRUE oder FALSE Werten ist eine wahrscheinlich mögliche zufällige Sequenz.

Gruß Hagen

[negaH]

Zitat:

Zitat von alzaimar

@Olli:Ob ich nun

Delphi-Quellcode:

bRand := Boolean (Random (2))

nehme, oder

Delphi-Quellcode:

bRand := Boolean (Random (10000) mod 5000)

ist, zumindest beim Delphi-Randomgenerator, auch mathematisch ein und die selbe Sosse.

Nein ist es nicht. Beide Lösungen sind schlichtweg falsch da der direkte Cast eines Integers nach Boolean syntaktisch absolut undefiniert ist.

PASCAL konforme Lösungen wären:

Delphi-Quellcode:

begin
  Result := Odd(Random(2));

  Result := Random(2) <> 0;
  
  Result := Random(2) = 0;

  Result := Random(1000) >= 500;
end;


const
  Boolean: array[0..1] of Boolean = (False, True);
begin
  Result := Boolean[Random(2]);
end;

alles andere ist Quatsch mit Sosse.

Gruß Hagen

[Jelly]

Zitat:

Zitat von negaH

eine Garantie das man bei 1000 zufällig erzeugten Booleans exakt 50% jeweils TRUE oder FALSE sind kann es bei Zufall eben nicht geben. Dies wäre nämlich nicht mehr zufällig, also ein Widerspruch insich.

Das freut mich zu hören, denn auf mich hört ja keiner :mrgreen:

[alzaimar]

Zitat:

Zitat von negaH

Zitat:

Zitat von alzaimar

@Olli:Ob ich nun

Delphi-Quellcode:

bRand := Boolean (Random (2))

nehme, oder

Delphi-Quellcode:

bRand := Boolean (Random (10000) mod 5000)

ist, zumindest beim Delphi-Randomgenerator, auch mathematisch ein und die selbe Sosse.

Nein ist es nicht. Beide Lösungen sind schlichtweg falsch da der direkte Cast eines Integers nach Boolean syntaktisch absolut undefiniert ist.

Klappt aber (bis auf das ... mod 5000, was mod 2 heissen sollte) wunderbar und liefert unter Delphi gleichverteilte Boolsche Werte. :mrgreen:

Prinzipiell hast Du aber Recht, denn das Typecasting Bool-->Integer ist von System zu System unterschiedlich implementiert.

Aber bitte, in Zukunft mit Mass kritisieren und vorher vielleicht das eine oder Andere ausprobieren.

Unabhängig davon hört in dem Thread sowieso keiner auf den Anderen. Ich hatte schon vorher das Paradoxon mit den 'garantiert gleichverteilten 1000 Zufallszahlen' erklärt, aber das wurde ignoriert. Na nun, egal.

[negaH]

@alzaimar:

ich weis das dies funktioniert. Aber nur weil der Compiler einen Boolean als

FALSE = 0
TRUE <> 0

ansieht, was aber nicht offiziell dokumentiert ist. Der Compiler kann diese Logik benutzen weil auf Intel CPUs die Anfrage auf == 0 oder <> 0 über die Prozessorflags und deren Auswertung per Bedingte Sprünge so easy ist. Würde der Borland Compiler aber zb. auf ARM Kernen laufen so ginge dies eben nicht mehr.
Offiziell ist ein Boolean aber als

FALSE = 0
TRUE = 1

definiert. Was aber keine plausible Begründung für (Integer mod 2) in [0,1] in Boolean sein darf, da sich diese Definition jederzeit ändern könnte.

Angenommen folgender Code:

Delphi-Quellcode:

function BooleanToString1(Value: Boolean): String;
const
  sBoolean: array[Boolean] of String = ('FALSE', 'TRUE');
begin
  Result := sBoolean[Value];
end;

function BooleanToString2(Value: Boolean): String;
const
  sBoolean: array[Boolean] of String = ('FALSE', 'TRUE');
begin
  Result := sBoolean[Value <> False];
end;

procedure Test;
var
  S: String;
begin
  S := BooleanToString1(Boolean(2));
  WriteLn(S);

end;

//  und

begin
  if Boolean(2) then
  begin
    WriteLn('test');
  end;
end;

probier ihn aus.
Man muß dann schon BooleanToString2() benutzen um falsche TypCast zu eliminieren und den Code Bulletproof zu machen, was aber im Grunde nur duch die ungültigen TypCast zb. anderer Programmierer verursacht wurde.
Im zweiten Beispiel sieht man das der Compiler den Bytewert 2 einfach auf <> 0 abfragt und dieses über die Möglichkeiten der Intel CPUs als gültiges TRUE akzeptiert.

Das heist: solche ungültigen TypCast nach Boolean funktionieren innerhalb von Anfragen immer sauber, auf Grund der spezifischen Umsetzung in den Machinencode der Intel CPUs. Sie führen aber bei bestimmten PASCAL/Delphi konformen Sourcen, wie in BooleanToString1() gesehen, zu unvorhersehbarem Verhalten des Programmes. Dies wird dann zu Zugriffsverletzungen führen, obwohl der Code in BooleanToString1() absolut astreiner Delphi Source ist.

Wir alle können uns nun sicher vorstellen wie der Programmierer von BooleanToString1() stundenlang in seinem Sourcecode nach der Ursache dieser Zugriffsverletzungen suchen wird.

Gruß Hagen

[negaH]

Zitat:

Ich hatte schon vorher das Paradoxon mit den 'garantiert gleichverteilten 1000 Zufallszahlen' erklärt, aber das wurde ignoriert. Na nun, egal.

Und weil dieser Hinweis essentiell richtig ist, und das nun schon von 3-4 Leuten mit anderen Worten gesagt wurde, habe ich's eben ein 5'tes mal wiederholt. Vielleicht wird es ja dann noch deutlicher ;)

Aber, selbst wenn der Poster der Frage kein Intresse mehr an der Lösung dieser Frage hat, so ist die Wahrscheinlichkeit denoch sehr groß das später andere Antwortsuchende über diese Thread stolpern, und eben davon lernen. Soll heisen: die momentane "Ignoranz" muß man einfach akzeptieren und mit der Hoffnung vorlieb nehmen das Andere sich ihr Wissen rausziehen werden. Sieh es positiv :)

Gruß Hagen