BigInt: RandomRange Funktion?

[Z4ppy]

@Meflin: Schaut ja eigentlich ganz gut aus, is aber glaube ich ein bisschen zu viel des Guten (ohne Blick auf die Source, kb aufs Reggen :D)

MfG Z4ppy

[gammatester]

Es gibt eine schnellere (mit sehr kleiner Bias) und eine etwas langsamere Methode, die allerdings Gleichverteilung erzeugt. Der Einfachheit sollen bigints zwischen 0 und R-1 erzeigt werden. Wenn R n bits braucht, erzeugst Du ein bigint x mit n random bits.

Methode 1: random = x mod R (wie gesagt hier hast Du eine kleine Störung der Gleichverteilung, die allerdings umso kleiner ist, als R größer wird)

Methode 2:

Code:

repeat
  x = n random bits
  until x<R;
random = x;

Als einfachen cryptografischen Generator kannst Du ISAAC von Bob Jenkins verwenden, statt des Pascal-Link auf seiner Seite kannst Du gleich direkt meine deutsche Seite gehenWE's (C)PRNG.

Gammatester

[Z4ppy]

THX, allerdings muss ich zugeben, dass ich mit dieser Unit net ganz klarkomm :oops:
Was bedeutet denn dieses ctx in jeder Prozedur/Funktion?
Wie generiert man dort nun eine Zufallszahl zwischen 1 und x?

MfG Z4ppy

€dit: Ich glaub, ich werd des random = x mod R machen, denn ich hab ohnehin riesige Primzahlen (1000 bis 20000 stellig :D) in meinem Programm ;) Von denen kann ich dann halt n R berechnen... Was sollte man denn als x nehmen?

[gammatester]

Zitat:

Zitat von Z4ppy

THX, allerdings muss ich zugeben, dass ich mit dieser Unit net ganz klarkomm :oops:
Was bedeutet denn dieses ctx in jeder Prozedur/Funktion?
Wie generiert man dort nun eine Zufallszahl zwischen 1 und x?

MfG Z4ppy

€dit: Ich glaub, ich werd des random = x mod R machen, denn ich hab ohnehin riesige Primzahlen (1000 bis 20000 stellig :D) in meinem Programm ;) Von denen kann ich dann halt n R berechnen... Was sollte man denn als x nehmen?

ctx ist ein Kontext-Record, d.h. Du kannst mehrere Generatoren gleichzeitig haben, bei Delphi hast Du nur einen Kontext nämlich randseed (ein Kontext ist so ähnlich wie eine Klasse oder ein Objekt). Rufe eine der Init-Prozeduren mit Deinen seed(s) auf und dann eine der Funktion isaac_word, oder isaac_long etc. Wenn Du viele Bytes brauchst isaac_read. Wenn Du ein 32-Bit Dword brauchst geht's mit ctx.next und ctx.nextres.

Welche Funktionen Du verwenden kannst, hängt von den biginst ab. Wenn's ein array of cardinal ist, etwa isaac_read(ctx, @DeinArray, length(DeinArray)*sizeof(cardinal)).

Zitat:

Wie generiert man dort nun eine Zufallszahl zwischen 1 und x?

Soll wohl heißen 1 <= ZZ <= x: Wenn dein x zwischen 2^(n-1) und 2^n liegt, mußt Du mindestens n Bits erzeugen, d.h. Du liest mindestens n bits in ein bigint y, bildest y mod x und addierst 1. Bei der letzten Frage: mit x mod R ist halt zwischen 0 und R-1 und wenn Du 1 draufaddierst zwischen 1 und R.

Gammatester

[Z4ppy]

Danke für deine Erklärung, muss aber gleich weg, werds mir daher später ansehen...

Ich meinte: Was muss x sein ;) Eine beliebige, möglichst grosse Zahl?

MfG Z4ppy

[Z4ppy]

Nun nochmal: ich nehme random:=x mod R, R ist eine riesige Zahl - was muss x sein?

MfG Z4ppy

[gammatester]

Zitat:

Zitat von Z4ppy

Nun nochmal: ich nehme random:=x mod R, R ist eine riesige Zahl - was muss x sein?

Und auch noch mal :wink: - damit jetzt endlich klar ist was gemacht werden soll:


R ist eine riesige Zahl und Du sucht eine Zufallszahl z mit 0 <= z < R.

Sei l = ceil(log2(R)) die Bitlänge von R.

Die bessere Methode:

Code:

repeat
  erzeuge l Zufalls-BITS
  mach aus den l BITS ein bigint x >=0
until x < R
z := x;

Mit der mod-Methode erzeugst Du l+k BITS, machst aus diesen BITS ein bigint x und setzt z := x mod R.

Je größer k ist, desto bessere Gleichverteilung erhältst Du. Also zB k=32: Abweichung von der Gleichverteilung ca 1 : 4 Milliarden.

Gruß Gammatester

[Z4ppy]

Und wie erzeugt man nun ein Zufallsbit? Und wie macht man daraus ein BigInt?!

MfG Z4ppy

[gammatester]

Zitat:

Zitat von Z4ppy

Und wie erzeugt man nun ein Zufallsbit? Und wie macht man daraus ein BigInt?!

Siehe Beitrag #14. Im übrigen kann man das ganz natürlich besser und mit Beweisen nachlesen, z.B. in Kapitel 9.2: Generating a random number from a given interval von Victor Shoup's Buch: A Computational Introduction to Number Theory and Algebra (Version 2) als PDF erhältlich auf http://shoup.net/ntb.

Wenn Du konkreten Code sehen willst, kannst Du ihn in meinem MPArith-Archiv (gleiche URL wie Beitrag #12) finden, ich werde mir jedenfalls keinen Code für die im Beitrag #1 genannte bigint-Klasse antun.

Gruß Gammatester

[Z4ppy]

Hmm, mir is grad noch ne ganz einfache methode eingefallen :D
Man generiert quasi einfach einen Zufallsstring aus Ziffern... Man muss die Zufallszahl natürlich in einer Variable zwischenspeichern, um sicher zu gehen, dass die Zahl mit Zufügen der Ziffer net grösser wird, als R... Am Schluss kann man den String ja dann einfach in nen BigInt umwandeln...

Werde das morgen mal testen, müsste aber eigentlich funktionieren...

MfG Z4ppy