PureBoard

Verfasst: **28.10.2008 20:13**

Moinsen,
hier ein paar Funktionen für (Pseudo-)Zufallszahlen, wie die von Random().
Es können mehrere solcher 'Randomizer' seperat genutzt werden.
Von jedem 'Randomizer' kann man (gleichverteilt) zufällig erhalten:
- long oder quad-Wert im vollen Wertebereich
- boolean (#True oder #False)
- positiver long-Wert durch Maximum nach oben begrenzt
- long-value im Bereich [Minimum, Maximum[
- float oder double-Wert im Bereich [0.0, 1.0[

Zudem lassen sich zufällige double-Werte unter Gaussverteilung (Normalverteilung) mit Mittelwert 0.0 und Standardabweichung 1.0 generieren.

Hier der Code:

Code: Alles auswählen

; #### Randomizer v1.0
; These procedures bring some extended randomize-functionality to all platforms.
; They are algorithmically based on the implementation of the Random()-class in Java.
;
; Usage:
; 1. create a randomizer e.g. by calling *rnd.Randomizer = RND_Create()
; 2. get random long/float/double-values at uniform distribution or double-values at
;   gaussian distribution from *rnd by calling their respective function, e.g. RND_NextLong(*rnd)
;
; That's all. You might use multiple different randomizers at the same time without any conflict.
; Initializing two randomizers with the same seed will result in same behaviour.
;
; by Froggerprogger at 2008-10-28
;
; license: feel free to use this code for anything you want to

; #### Randomizer ####
; The structure identifying a randomizer
Structure Randomizer
  seed.q
  hasNextGaussian.l
  nextNextGaussian.d
EndStructure

; #### RND_NextBits ####
; Creates and returns a random long number, whose lower <bits> bits are set randomly.
; The random seed is taken from <*rnd> and updated there.
; <bits> should lay in range [1, 32]
; This procedure is exensively used by the other randomizing procedures, but might be used seperately.
Procedure.l RND_NextBits(*rnd.Randomizer, bits.l) ; returns number with lower <bits> bits (in range [1, 32]) set randomly
  Protected multiplier.q = $5DEECE66D
  Protected addend.q = $B
  Protected mask1.q = $FFFFFFFFFFFF
  Protected mask2.q = (1<<bits)-1

  *rnd\seed = (*rnd\seed * multiplier + addend) & mask1

  ProcedureReturn (*rnd\seed >> (48-bits)) & mask2
EndProcedure

; #### RND_CreateSeed ####
; Creates a new randomizer and sets its seed based on a modified <seed>
; (Use RND_SetSeed to set the seed without any modification to it.)
; Calling RND_CreateSeed two times with the same <seed> will result in the same behaviour of the both randomizers.
; Returns a pointer to the created randomizer, so e.g. call
; *rnd.Randomizer = RND_CreateSeed(seed)
Procedure.l RND_CreateSeed(seed.q) ; creates a new randomizer by given seed
  Protected multiplier.q = $5DEECE66D
  Protected mask.q = $FFFFFFFFFFFF
  Protected *rnd.Randomizer = AllocateMemory(SizeOf(Randomizer))
  If *rnd
    seed ! multiplier
    seed & mask
    *rnd\seed = seed
    *rnd\hasNextGaussian = #False
  EndIf 
  ProcedureReturn *rnd
EndProcedure

; #### RND_Create ####
; Creates a new randomizer with seed depending on ElapsedMilliseconds().
; Even multiple calls at the same millisecond will result in unique seeds.
; Returns a pointer to the created randomizer, so e.g. call
; *rnd.Randomizer = RND_CreateSeed()
Procedure.l RND_Create() ; creates a new randomizer with random seed
  Static seedUniquer.q = 8682522807148012
  Protected seed.q = seedUniquer + ElapsedMilliseconds()
  seedUniquer + 1
 
  ProcedureReturn RND_CreateSeed(seed)
EndProcedure

; #### RND_SetSeed ####
; Sets the seed of the given randomizer to <seed> without any modification to this value.
; Two randomizers with the same seed will result in the same behaviour.
Procedure RND_SetSeed(*rnd.Randomizer, seed.q)
  *rnd\seed = seed
  *rnd\hasNextGaussian = #False
EndProcedure

; #### RND_Free ####
; Destroys the randomizer given in <*rnd>. Returns wether or not it could be successfully freed.
Procedure.l RND_Free(*rnd.Randomizer) ; destroys the given randomizer (frees any memory used by it)
  ProcedureReturn FreeMemory(*rnd)
EndProcedure

; #### RND_NextLong ####
; Returns a random long in full range of -2147483648 to +2147483647
Procedure.l RND_NextLong(*rnd.Randomizer) ; returns random long in full range of -2147483648 to +2147483647
  ProcedureReturn RND_NextBits(*rnd, 32)
EndProcedure

; #### RND_NextLongMax ####
; Returns a random long in range of 0 to <exclMax>-1
; so inclusive the zero, but exclusive the value <exclMax>
Procedure.l RND_NextLongMax(*rnd.Randomizer, exclMax.l) ; returns random long between 0 (inclusive) and <exclMax> (exclusive)
  If exclMax <= 0
    ProcedureReturn -1
  EndIf
 
  If (exclMax  & (-exclMax)) = exclMax
    Protected q.q = RND_NextBits(*rnd, 31)
    q * exclMax
    q >> 31
    ProcedureReturn q
  Else
    Protected bits.l, val.l
    Repeat
      bits = RND_NextBits(*rnd, 31)
      val = bits % exclMax
    Until (bits - val + (exclMax-1) >= 0)
    ProcedureReturn val
  EndIf 
EndProcedure

; #### RND_NextLongMinMax ####
; Returns a random long in range of <inclMin> to <exclMax>-1
; so inclusive the value <inclMin>, but exclusive the value <exclMax>
; It should hold that <inclMin> is smaller than <exclMin> and that <exclMax> - <inclMin> is smaller than 2^32
Procedure.l RND_NextLongMinMax(*rnd.Randomizer, inclMin, exclMax.l) ; returns random long between <inclMin> (inclusive) and <exclMax> (exclusive)
  ProcedureReturn inclMin + RND_NextLongMax(*rnd, exclMax - inclMin)
EndProcedure

; #### RND_NextQuad ####
; Returns a random long in whole range of -9223372036854775808 to +9223372036854775807
Procedure.q RND_NextQuad(*rnd.Randomizer) ; returns random quad in full range of -9223372036854775808 to +9223372036854775807
  Protected q.q = RND_NextBits(*rnd, 32)
  q << 32
  q + RND_NextBits(*rnd, 32)
  ProcedureReturn q
EndProcedure

; #### RND_NextBoolean ####
; Returns #False or #True by random
Procedure.l RND_NextBoolean(*rnd.Randomizer) ; returns #False or #True by random
  If RND_NextBits(*rnd, 1)
    ProcedureReturn #True
  Else
    ProcedureReturn #False
  EndIf
EndProcedure

; #### RND_NextFloat ####
; Returns a random float-value in range of 0.0 (inclusive) to 1.0 (exclusive)
Procedure.f RND_NextFloat(*rnd.Randomizer) ; returns a random float-value in range of 0.0 (inclusive) to 1.0 (exclusive)
  Protected f.f = RND_NextBits(*rnd, 24)
  f / (1<<24)
  ProcedureReturn f
EndProcedure

; #### RND_NextDouble ####
; Returns a random double-value in range of 0.0 (inclusive) to 1.0 (exclusive)
Procedure.d RND_NextDouble(*rnd.Randomizer) ; returns a random double-value in range of 0.0 (inclusive) to 1.0 (exclusive)
  Protected q.q = RND_NextBits(*rnd, 26)
  q = (q << 27) + RND_NextBits(*rnd, 27)
  Protected d.d = (1<<53)
  d = q / d
  ProcedureReturn d
EndProcedure

; #### RND_NextGaussian ####
; Returns a random double-value that is distributed by Gaussian with mean 0.0 and standard-deviation 1.0
Procedure.d RND_NextGaussian(*rnd.Randomizer)
  If *rnd\hasNextGaussian
    *rnd\hasNextGaussian = #False
    ProcedureReturn *rnd\nextNextGaussian
  Else
    Protected v1.d, v2.d, s.d
    Repeat
      v1 = 2.0 * RND_NextDouble(*rnd) - 1.0 ; between -1 and 1
      v2 = 2.0 * RND_NextDouble(*rnd) - 1.0 ; between -1 and 1
      s = v1 * v1 + v2 * v2
    Until (s < 1 And s <> 0)
    Protected multiplier.d = Sqr(-2.0 * Log(s) / s)
    *rnd\nextNextGaussian = v2 * multiplier
    *rnd\hasNextGaussian = #True
    ProcedureReturn v1 * multiplier
  EndIf
EndProcedure

;-
;- END INCLUDE
;-

;########################################
;- Examples
;########################################
*rnd1.Randomizer = RND_Create()
*rnd2.Randomizer = RND_CreateSeed(987654321)

Debug "### 5 random doubles in [0.0, 1.0["
For i=1 To 5
  Debug RND_NextDouble(*rnd1)
Next

Debug "### 5 random longs in [-5, 5]"
For i=1 To 5
  Debug RND_NextLongMinMax(*rnd1, -5, 6)
Next

Debug "### 5 random longs in full range"
For i=1 To 5
  Debug RND_NextLong(*rnd1)
Next

Dim A.l(10)
Debug "### 10000 uniform distributed doubles in [0.0, 1.0["
For i=1 To 10000
  d.d = RND_NextDouble(*rnd1)
  index.l = Int(d*10.0) ; must use Int() or Round(..., 0) here for rounding downwards
  A(index) + 1
Next
f.f = 0.0
i = 0
While i < 10
  Debug "hits in range " + StrF(f, 1) + " to " + StrF(f + 0.1, 1) + " : " + Str(A(i))
  f.f + 0.1
  i + 1
Wend

Dim A.l(20)
Debug "### 10000 gaussian-distributed doubles"
For i=1 To 10000
  d.d = RND_NextGaussian(*rnd2)
  index.l =  Round(d*2.0 + 10.0, 0)
  If index >= 0 And index < 20
    A(index) + 1
  EndIf
Next

f.f = -5.0
i = 0
While i < 20
  Debug "hits in range " + StrF(f, 1) + " to " + StrF(f + 0.5, 1) + " : " + Str(A(i))
  f.f + 0.5
  i + 1
Wend

RND_Free(*rnd1)
RND_Free(*rnd2)

Verfasst: **29.10.2008 17:58**

Wirklich interessant, das kann ich glaube ich gut gebrauchen.
Wie sieht's mit der Geschwindigkeit aus und der Güte der Zufallszahlen aus im Vergleich zum Standard-Random aus? Hast du da schon irgendwelche Tests zu?

Verfasst: **29.10.2008 21:28**

Die Geschwindigkeit ist deutlich langsamer als die von PB's Random, was sicherlich mehrere Ursachen hat:

Beides sind lineare Kongruenzgeneratoren. PB's Implementierung wird dabei wohl intern mit 32 Bit rechnen und untersützt daher nur zufällige Bitfolgen mit bis zu 31 Bits. Z.B. Random(N) mit N > $7FFFFFFF scheitert, was es umständlicher macht, Zufallszahlen im ganzen Wertebereich zu konstruieren.

Die zentrale Procedure hier ist RND_NextBits(..., N) und sie erzeugt zufällig N Bits für einen variablen Einsatz in der Bildung von zufälligen Longs, Quads, Floats, Doubles, etc.. Obwohl hier nur Aufrufe mit bis zu 32 Bits erfolgen, wird intern sogar mit Quads gerechnet, und unnötige untere Bits rausgeschoben, um die Zufälligkeit etwas weiter zu erhöhen. Trotzdem wurde wo möglich auf Speed optimiert, z.B. die Sonderbehandlung der Zweierpotenzen in RND_NextLongMax oder die gleichzeitige Berechnung zweier aufeinanderfolgender Zufallszahlen der Gaussverteilung.

Ist daher wohl eher ne Sache des Schwerpunkts. PB: Speed und ausreichende Zufälligkeit für die meisten Zwecke bei eingeschränkter Funktionalität , hier: möglichst hohe Zufälligkeit und Funktionalität trotz linearer Kongruenzmethode auf Kosten von Speed. Aber immerhin brauchen bei mir 100000 Aufrufe nur 300 ms, was zumindest für alle meine Zwecke genügt.

Ansonsten: Die Funktionen ließen sich sicherlich abwandeln, so dass bspw. ein RND_FastLongMax intern nur mit longs rechnet.

PureBoard

Erweitertes Random

Erweitertes Random