#136464 - 2005-03-25 11:26 PM
Weekend Mini Challenge - Create Random Number Generator UDF
|
NTDOC
Administrator
   
Registered: 2000-07-28
Posts: 11634
Loc: Space
|
Went looking for a best of breed RANDOM number generator and so far was unable to find one that is really all that close to being random on a fast computer.
So here is the challenge. Write a RANDOMIZE function that supports the following criteria
- 1. Must be able to handle a MIN/MAX input range
- 2. Must support both whole and decimal numbers
- 3. Must not readily (obviously detectable pattern) duplicate numbers in successive calls including small range of 1-10
- 4. Must support calls similar to this
Random(0.000, 0.999) Random(1, 5) Random(500, 10000)
- 5. Use of seed or method to ensure randomness should be controlled by the UDF
- Example:
For $ = 1 To 50 Random(0.000, 0.999) ? Next
- 6. Must support Explicit and NoVarsInStrings just like all other UDFs
Here is an example Random method from a mini putt challenge Kixtart Mini-putt challenge for tonight
This challenge does not have the same restrictions though as that one did, this is not a Golf challenge but rather a UDF Challenge.
Though a number after a number may still be random it is not if success calls show a simlar duplicate pattern
Example of duplicate
Though the 6 after the 6 may be random it is not if you call the function 10 times and you see values that repeat in a pattern.
|
|
Top
|
|
|
|
#136469 - 2005-03-27 04:16 AM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
NTDOC
Administrator
   
Registered: 2000-07-28
Posts: 11634
Loc: Space
|
Okay... here are some examples from Bryce, Shawn and Al None of them meet the criteria though.
Code:
function Random($min, $max, optional $seed) if $seed srnd($seed) endif $random = rnd($max) do $random = rnd($max) until $random >= $min and $random <= $max Endfunction
Code:
function random($min, $max, optional $seed) DIM $i, $burn, $nul srnd((-1)*@ticks*(val($seed)+1)) $burn = rnd(50) for $i = 1 to $burn $nul = rnd($max) next $random = rnd($max) while $random < $min or $random > $max $random = rnd($max) loop endfunction
Code:
function random($min,optional $max) dim $seed do $seed=@ticks do until $seed<>@ticks SRND(IIF(@TICKS<0,(-(@TICKS*@msecs*7)),@TICKS*@MSECS*7)) $random=rnd($max) until $random>=$min and $random<=$max Endfunction
Code:
Function Randomize() Dim $ticks $ticks = @ticks If $ticks < 0 $ticks = -1 * $ticks EndIf SRND($ticks) EndFunction
|
|
Top
|
|
|
|
#136470 - 2005-03-28 05:52 PM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
Jack Lothian
MM club member
   
Registered: 1999-10-22
Posts: 1169
Loc: Ottawa,Ontario, Canada
|
I looked into this a few years ago & I believe that all the high quality & fast random number generators require specialized bit minipulation functions that are not available in Kixtart. I suspect that you could create these functions in Kixtart UDFs but the result would no longer be fast.
The Mersenne Twister is probably the leading candidate for a fast/high-quality generator but Kixtart is missing too many native functions too really get any speed.
But if want to do this seriously why would you use Kixtart - can't you live with the native random number generator provided by the MS system? For most every day applications this function is perfectly adequate. Yes the function fails some tests concerning randomness but they are pretty esoteric & probably irrelevant for most aplications.
AH; I see Bryce & Shawn are using the MS function
Edited by Jack Lothian (2005-03-28 05:54 PM)
|
|
Top
|
|
|
|
#136472 - 2005-03-28 08:42 PM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
Bryce
KiX Supporter
   
Registered: 2000-02-29
Posts: 3167
Loc: Houston TX
|
i see the biggest challenge is the floating point stuff, since rnd() does not support it. Perhaps a suggestion for rudd?
I was taking a crack at it a little while ago, but then i had to play Indiana Jones and recover a lost email from 2 years ago... before my time here, and the new servers....
|
|
Top
|
|
|
|
#136473 - 2005-03-28 08:50 PM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
Shawn
Administrator
   
Registered: 1999-08-13
Posts: 8611
|
It was JACK himself that once showed me how to work floating-point random numbers, in the range 0 to 1, Jack - step in here anytime:
Code:
for $i = 0 to 20 ?"rnd=" 0.001 * rnd(1000) next
|
|
Top
|
|
|
|
#136475 - 2005-03-30 04:04 PM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
Richard H.
Administrator
   
Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
|
In case anyone needs it, here is a pseudo-random number generator to start with.
Apply whatever modifiers you need to get the required ranges.
I've not tested it exhaustively, beyond making sure that it kind of works.
Code:
$=SetOption("Explicit","ON") Dim $i $i=rng(@TICKS) For $i=1 to 50 rng() ? Next Function rng(Optional $iSeed) Dim $vDiscard If Not IsDeclared($_RNG_PERSISTENT) Global $_RNG_PERSISTENT EndIf If VarType($iSeed) $_RNG_PERSISTENT=CInt($iSeed) EndIf $_RNG_PERSISTENT=CInt(&FFFFFFFFFF) & CInt($_RNG_PERSISTENT) $_RNG_PERSISTENT=CInt($_RNG_PERSISTENT*1103515245 +12345) ; Emulate 16 bit shift right ($rng>>16) $rng=DecToHex($_RNG_PERSISTENT) $rng=SubStr($rng,2,Len($rng)-3) If $rng="" $rng=0 EndIf ; Convert hex to Decimal $vDiscard=Execute("$$rng=&"+$rng+" & &FFFFFFFF") EndFunction
|
|
Top
|
|
|
|
#136476 - 2005-03-30 04:44 PM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
Richard H.
Administrator
   
Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
|
Here is the full thing, with support for max, min and decimal places: Code:
Break ON $=SetOption("Explicit","ON") Dim $i,$r,$max,$min $r=rng(0,0,@TICKS) While "TRUE" AND Not KBHit() rng(10.00,20.99) ? Loop Function rng($iMin,$iMax,Optional $iSeed) Dim $vDiscard,$sDecimal,$i,$iFactor $sDecimal="." ; Establish how many decimals to use If InStr($iMin,$sDecimal) $iFactor=Len($iMin)-InStrRev($iMin,$sDecimal) EndIf If InStr($iMax,$sDecimal) $i=Len($iMax)-InStrRev($iMax,$sDecimal) EndIf If $i>$iFactor $iFactor=$i EndIf $iFactor=CInt("1"+Left("000000",$iFactor)) ; Ensure min and max are in the right order If $iMax < $iMin $i=$iMin $iMin=$iMax $iMax=$i EndIf $iMax=$iMax * $iFactor $iMin=$iMin * $iFactor ; Fix max to base (0) $iMax=($iMax-$iMin+1) If Not IsDeclared($_RNG_PERSISTENT) Global $_RNG_PERSISTENT EndIf If VarType($iSeed) $_RNG_PERSISTENT=CInt($iSeed) EndIf $_RNG_PERSISTENT=1103515245*$_RNG_PERSISTENT+12345 ; Emulate 16 bit shift right ($rng>>16) $rng=DecToHex($_RNG_PERSISTENT) $rng=SubStr($rng,2,Len($rng)-3) If $rng="" $rng=0 EndIf ; Convert hex to Decimal and fix to scope ; $vDiscard=Execute("$$rng=&"+$rng) $vDiscard=Execute("$$rng=CDbl(((&"+$rng+" mod "+$iMax+") + "+$iMin+")) / "+$iFactor) EndFunction
|
|
Top
|
|
|
|
#136478 - 2005-03-30 07:54 PM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
NTDOC
Administrator
   
Registered: 2000-07-28
Posts: 11634
Loc: Space
|
Richard,
Excellent entry. Couple observations.
1. Does not meet criteria for SetOption('NoVarsInStrings','On')
2. On small range 1,10 duplicates are found seeming repeatably (granted it is possible that on such a small range this is as random as KiX may be able to get to)
Examples of return data when range is set to 1,10
Aside from that, very nice entry in the challenge. Thank you for taking the time to enter.
|
|
Top
|
|
|
|
#136479 - 2005-03-30 08:35 PM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
NTDOC
Administrator
   
Registered: 2000-07-28
Posts: 11634
Loc: Space
|
Richard, just an update on further observations of running your code example. Range set to 0,999 whole numbers. In this range I would expect few duplicates (some, but not many) however as you can see there appears to be groups of duplicates occuring in the code (when it is sorted in order for us to more easily spot them) Out of 248 numbers generated there were 25 groups of duplicates with some being repeated up to 3 times.
48,54,107,140,192,200,244,321,353,433,460,465,467,482,512,530,696,732,740,749,755,816,883,927,992
(Not duplicates, but weird to have such a straight as well 394-397 in a range of 1000 numbers and only returning 248 numbers in all.)
1 4 6 7 10 12 17 19 23 27 29 39 44 48 48 54 54 59 61 62 69 71 74 85 97 103 106 107 107 109 111 113 118 131 133 137 140 140 144 147 148 153 154 159 161 167 177 179 181 182 187 192 192 192 197 199 200 200 213 215 216 217 230 232 238 240 244 244 250 252 254 263 272 273 279 285 307 309 312 313 321 321 325 327 328 338 339 343 352 353 353 353 355 366 370 385 386 389 389 390 394 395 396 397 400 402 408 422 426 430 433 433 434 438 442 446 450 454 456 460 460 465 465 467 467 467 469 471 473 482 482 485 487 490 492 494 500 508 512 512 521 522 529 530 530 531 533 534 544 546 548 552 585 596 600 601 611 615 621 625 643 647 658 668 669 673 676 679 696 696 698 700 703 722 731 732 732 737 740 740 744 747 749 749 750 751 755 755 777 779 786 789 801 804 808 810 811 813 816 816 818 821 824 828 829 831 833 838 841 843 846 847 849 853 857 870 872 883 883 883 894 896 900 901 916 917 921 927 927 930 931 936 938 942 943 950 956 959 960 962 970 972 975 978 981 992 992 999
|
|
Top
|
|
|
|
#136481 - 2005-03-31 10:46 AM
Re: Weekend Mini Challenge - Create Random Number Generator UDF
|
Richard H.
Administrator
   
Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
|
Minor change made so that it is "NoVarsInStrings" safe.
I'm not convinced that there is a repeating pattern, though you will need a larger sample to prove it.
The script below graphs the results from the RNG. You will see that the results are fairly linear, which indicates a good spread of values. More importantly, the pattern of growth changes - I'd expect a repeating set to have both an unbalanced set returned and an obvious pattern of growth.
Try changing the $iSampleSet value (to a multiple of 50). After subtracting $iBase, the process will plot
- $iSampleSet=50 Every result
- $iSampleSet=100 Even numbers
- $iSampleSet=250 Numbers divisible by 5
- $iSampleSet=5000 Hundreds
...and so on.
It's not a mathematical proof (my maths ain't that good) but it looks ok from an empirical standpoint.
I've got another algorithm somewhere, but it needs large number support. I'll dig it out next chance I get to spend some more time on this.
Code:
Break ON $=SetOption("Explicit","ON") $=SetOption("ASCII","ON") $=SetOption("NoVarsInStrings","ON") Dim $r,$iMaxScale,$iRow,$iSampleSize,$iSampleRate,$iBase,$iSampleCount Dim $iResults[50] $iMaxScale=100 $iSampleSize=5000 $iBase=1234 CLS DrawGraph($iMaxScale,$iResults) $iSampleSize=Int($iSampleSize/50)*50 At(23,40) "Sample size=" $iSampleSize ", Base=" $iBase $iSampleRate=$iSampleSize/50 $r=rng(0,0,@TICKS) While "TRUE" AND Not KBHit() $r=rng($iBase,$iBase+$iSampleSize-1) $iSampleCount=$iSampleCount+1 $r=$r-$iBase ; Only record results from sample If Not ($r mod $iSampleRate) At(23,0) "Last: " $r " " $r=$r/$iSampleRate At(23,15) "Sample Count: " $iSampleCount $iResults[$r]=$iResults[$r]+1 $iRow=$iResults[$r]/($iMaxScale/20) If $iRow>20 $iMaxScale=$iMaxScale*2 DrawGraph($iMaxScale,$iResults) Else If Not (($r+1) mod 5) Color y+/n EndIf If $iRow AT(22-$iRow,$r+11) "*" EndIf Color w/n EndIf EndIf Loop Get $r Function DrawGraph($iMaxScale,$iResults) Dim $iRow,$iCol At(1,0) Right(" "+$iMaxScale,9) For $iRow = 1 to 21 At($iRow,10) "|" Next At(22,10) "+" For $iCol=0 to 49 If Not (($iCol+1) mod 5) Color y+/n EndIf At(22,$iCol+11) "-" For $iRow=1 to 20 At(22-$iRow,$iCol+11) If ($iResults[$iCol]/($iMaxScale/20)) >= $iRow "*" Else " " EndIf Next Color w/n Next Exit 0 EndFunction Function rng($iMin,$iMax,Optional $iSeed) Dim $vDiscard,$sDecimal,$i,$iFactor Dim $ ; Fixes problem with "NoVarsInStrings" set to "ON" $sDecimal="." ; Establish how many decimals to use If InStr($iMin,$sDecimal) $iFactor=Len($iMin)-InStrRev($iMin,$sDecimal) EndIf If InStr($iMax,$sDecimal) $i=Len($iMax)-InStrRev($iMax,$sDecimal) EndIf If $i>$iFactor $iFactor=$i EndIf $iMax=CDbl($iMax) $iMin=CDbl($iMin) $iFactor=CInt("1"+Left("000000",$iFactor)) ; Ensure min and max are in the right order If $iMax < $iMin $i=$iMin $iMin=$iMax $iMax=$i EndIf $iMax=$iMax * $iFactor $iMin=$iMin * $iFactor ; Fix max to base (0) $iMax=($iMax-$iMin+1) If Not IsDeclared($_RNG_PERSISTENT) Global $_RNG_PERSISTENT EndIf If VarType($iSeed) $_RNG_PERSISTENT=CInt($iSeed) EndIf $_RNG_PERSISTENT=1103515245*$_RNG_PERSISTENT+12345 ; Emulate 16 bit shift right ($rng>>16) $rng=DecToHex($_RNG_PERSISTENT) $rng=SubStr($rng,2,Len($rng)-3) If $rng="" $rng=0 EndIf ; Convert hex to Decimal and fix to scope $vDiscard=Execute("$$rng=CDbl((((&"+$rng+") mod "+$iMax+") + "+$iMin+")) / "+$iFactor) EndFunction
|
|
Top
|
|
|
|
Moderator: Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart
|
0 registered
and 1046 anonymous users online.
|
|
|