Page 1 of 2 12>
Topic Options
#136464 - 2005-03-25 11:26 PM Weekend Mini Challenge - Create Random Number Generator UDF
NTDOC Administrator Offline
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
  • 1
    4
    6
    6
    8
    9


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
#136465 - 2005-03-25 11:39 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
lol. me waiting for competition, you provide.

anyway, as nobody else has answered, I rather not do that either.
_________________________
!

download KiXnet

Top
#136466 - 2005-03-26 01:23 AM Re: Weekend Mini Challenge - Create Random Number Generator UDF
NTDOC Administrator Offline
Administrator
*****

Registered: 2000-07-28
Posts: 11634
Loc: Space
I have some sample code, but wow 13 minutes - you only give everyone 13 minutes to respond or you don't want to. Hmmm... seems a little unrealistic that hundreds of users will be on the board a just that time frame.
Top
#136467 - 2005-03-26 01:17 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
hmm...
ja, you probably right.
_________________________
!

download KiXnet

Top
#136468 - 2005-03-27 03:33 AM Re: Weekend Mini Challenge - Create Random Number Generator UDF
NTDOC Administrator Offline
Administrator
*****

Registered: 2000-07-28
Posts: 11634
Loc: Space
Wow, all the complaints about slow weekend and now weekend is half over an still no one try.

I would have thought that at least a few of the Moderators would have tried by now.

Richard had one of the better approaches in the other thread but no try here where there are no restrictions.

Granted nothing generated by a computer is going to be truely random, but I think it can get a lot closer then it currently is, but then again... who knows for sure.

Top
#136469 - 2005-03-27 04:16 AM Re: Weekend Mini Challenge - Create Random Number Generator UDF
NTDOC Administrator Offline
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 Offline
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
#136471 - 2005-03-28 08:33 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
NTDOC Administrator Offline
Administrator
*****

Registered: 2000-07-28
Posts: 11634
Loc: Space
Yes if you want to get technical most advanced learning centers agree that it is generally considered that you can not natively generate a truely random number directly with the computer alone, it takes external input and filtering to achieve.

As for the built-in method of pseudo random I'm just saying that from my own observations it is rather deterministic to a point. In most examples if you were to run the range in the 1-10 and run a specific application for each different number I think you would see that many times you would run the same program 2, 3, or even 4 times out of 10 repeatedly which is not very random even for pseudo in my opinion.

Buy hey... if no one is up for the challenge then so be it. I just think it could be done better then it is even with the limits of native KiX inner workings.

Top
#136472 - 2005-03-28 08:42 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Bryce Offline
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 Offline
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
#136474 - 2005-03-28 11:22 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Shawn Administrator Offline
Administrator
*****

Registered: 1999-08-13
Posts: 8611
Doc,

Erik (kholm) totally golfed-down my Randomize() UDF into "nothing". Albiet the ABS() function wasn't around when Randomize() was done, Erik kinda shows that as a UDF, its kinda redundant now - here is the Randomize() equiv. statement:

SRND(ABS(@TICKS))

-Shawn

Top
#136475 - 2005-03-30 04:04 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Richard H. Administrator Offline
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 Offline
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
#136477 - 2005-03-30 04:52 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
BTW, this RNG has a larger range than KiXtarts RND(), 0-&FFFFF.
Top
#136478 - 2005-03-30 07:54 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
NTDOC Administrator Offline
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

  • 1
    8
    5
    5
    1
    5
    5
    3
    10
    1

  • 4
    2
    2
    10
    1
    10
    10
    6
    2
    1


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 Offline
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
#136480 - 2005-03-30 10:21 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22346
Loc: OK
lol.
isn't it random if it randomly repeats itself?
_________________________
!

download KiXnet

Top
#136481 - 2005-03-31 10:46 AM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Richard H. Administrator Offline
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
#136482 - 2005-04-01 06:58 AM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Jack Lothian Offline
MM club member
*****

Registered: 1999-10-22
Posts: 1169
Loc: Ottawa,Ontario, Canada
Hi Doc,

I don't get much chance to come by here but here is my 2 cents worth. I think you are confusing randomness with a human's desire for evenness & fairness. If you truely want even pulls for each number then forget randomness to some extent. Put in a check of the current size of the piles of each number & shift the selection probabilities so each pile more-or-less stays even with the other piles.

I don't have the inclination to do the combinatorials but I seem to remember a proof of the fact that betting that a triple comes up in series of 10 digits has good odds. (I believe this was discussed in relation to betting on the digits on a dollar bill.) It simular to the idea that in any school classroom of kids the odds favour that at least 1 pair of children will share a birthday.

As another side point, I am not sure which random function is being called by Kixtart but it is my understanding that the random number generators in Excel & VB are of a relatively high quality. For many years MS had a really terrible generator in both apps but the critism of the algorthim became so great they eventually moved from a poorly conceived 50 year old algorthim to one invented in the late 80s. As I understand it, the current MS algorithims are a bit dated but quite acceptable.

Another interesting side point is computer generated card hands tend to look freaker & less random than hand shuffled cards. An analysis of empirical facts showed the opposite was really true. In a real card game, players regroup cards in their hands & thus create small non-random groupings & shuffling does not break up these groupings. But when the dealer gives out the cards the created groups are split evenly between all the players so odd arrangements such as flushes or 4 pairs happen less frequently than they should. Interesting humans interpret this as being more random.

In closing, I suspect both Richard's & the internal MS algorithim are creating reasonably good pseudo-random series but they appear biased to us humans because we equate fairness with equality.

PS: Hi Shawn - sorry for putting my 2 cents worth in & then vanishing. I have little to do with kixtart lately & I stop by this site once or twice a week (usually very late) just to read what you guys are up to. I really enjoy the group on this board & I often find myself briefly dropping by to visit you guys even though I have little to add these days.


Edited by Jack Lothian (2005-04-01 07:04 AM)
_________________________
Jack

Top
#136483 - 2005-04-03 11:51 PM Re: Weekend Mini Challenge - Create Random Number Generator UDF
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11165
Loc: Boston, MA, USA
Lack:

Even if you only post every once in a while you-re having one of the highest signal-to-noise ratios, all signal, no noise ;-) And even the sginal is all information, no carrier waves and so in :-)
_________________________
There are two types of vessels, submarines and targets.

Top
Page 1 of 2 12>


Moderator:  Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart 
Hop to:
Shout Box

Who's Online
0 registered and 1046 anonymous users online.
Newest Members
Viginette, ManuvdWielNL, Sir_Barrington, batdk82, StuTheCoder
17888 Registered Users

Generated in 0.116 seconds in which 0.064 seconds were spent on a total of 13 queries. Zlib compression enabled.

Search the board with:
superb Board Search
or try with google:
Google
Web kixtart.org