Liberty BASIC Community Forum
Liberty BASIC Programming Discussions >> Liberty BASIC Code >> Pseudo Random Number Generation in LB...
http://libertybasic.conforums.com/index.cgi?board=LB3&action=display&num=1280099246

Pseudo Random Number Generation in LB...
Post by Coda on Jul 17th, 2010, 02:53am

Hi,

The current project I am working on is the first where I have had call to generate pseudo randomness in LB. I understand that in LB there is no need to seed the pseudo random algorithms with the system timer as in many other forms of BASIC, in fact 'Randomize Timer' is syntactically incorrect in LB. That's all cool. wink

But... (and here is the BIG but)... I'm getting some disturbing results. If LB contains a decent pseudo random algorithm then I shouldn't notice any patterns or be able to predict the program's next choices... and I can't... ALWAYS. The trouble is... sometimes I can!!

As one tends to run one's own program rather a lot when one is creating it for the purposes of testing new code as you go, I have noticed that I get the same sequence of results feeding out of the program on a basis that is well above chance. To simplify, if I start up my program and it generates for argument's sake 2 pseudo random numbers from 1-26 ie int(rnd(1) * 26) + 1 and then it generates 2 pseudo random numbers from 1-600 ie int(rnd(1) * 600) + 1 then waits until I tell it to produce another such set, the likelihood that I should ever get the same inital set should be pretty damned low and I should not be able to predict the next sets from the first.

What I am finding however is that I get the same first set of numbers maybe every 50 times I run the program and that I can predict the following sets from the initial set.

I notice that the LB randomize function only seems to take fractions between 0 and 1 to 2 decimal places as its input. Does that imply that there are only 98 possible seeds for the LB pseudo random algorthim? ...and further that the seed is incremented or decremented by a predetermined amount at each execution of the rnd function? huh If so that would explain the results I'm getting... but if so, it's not a terribly good situation to be in... undecided

Does anyone know what's going on here? I guess I'm asking if anyone knows how Carl created the funtion...

Any help would be greatly appreciated. grin
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Jul 17th, 2010, 03:36am

Carl borrowed the RNG from someone else.

He has once asked, if one knows a better RNG.

See Request Liberty BASIC source code to test RND for the discussion about the RNG.

Reply 15 on page 2 includes the question about a different RNG.

Re: Pseudo Random Number Generation in LB...
Post by tenochtitlanuk on Jul 17th, 2010, 04:01am

Can you post sample code? I've played quite a bit with Carl's and other PRN generators, and his seems similar in quality to others. Mind you, see Wikipedia for how long it took to realise how weak some early attempts were!
I ran the following 100 times and checked the results by sorting, and see no patterns. It tacks your four example prn's into one string and appends it to a file. Eg if it throws a 13, 8, 421, 353 it appends "013008421353" to the file of previous runs.
My original version looped 100 times, but from your question you imply it was repeating after separate RUNs, so rather than looping, I did it by appending each set of four numbers to a file.
Code:

    nomainwin

    a$ =""

    r  =int( rnd( 1) *  26) + 1
    a$ =a$ +right$( "000" +str$( r), 3)

    r  =int( rnd( 1) *  26) + 1
    a$ =a$ +right$( "000" +str$( r), 3)

    r  =int( rnd( 1) * 600) + 1
    a$ =a$ +right$( "000" +str$( r), 3)

    r  =int( rnd( 1) * 600) + 1
    a$ =a$ +right$( "000" +str$( r), 3)

    open "R:\TestRnd.csv" for append as #r
        #r chr$( 34); a$; chr$( 34)
    close #r

    end
 

PS Are you seeding the PRN???
Re: Pseudo Random Number Generation in LB...
Post by Rod on Jul 17th, 2010, 04:58am

Great minds, I did the undernoted. If I'm following what you are asking then I'm not replicating the problem. I just wonder if your program is setting the seed at any point? If so is it doing it more often than you think.

Also the seed number goes far beyond .nn and you can easily test that by feeding it ever smaller increments.

I suppose there are better random number generators but how would you ever know :)


Code:
dim a$(1000)
for n = 1 to 1000
    a=int(rnd(0)*26)+1
    a$=right$("00"+str$(a),2)
    b=int(rnd(0)*26)+1
    b$=right$("00"+str$(b),2)
    timer 10,[done]
    wait
    [done]
    timer 0
    c=int(rnd(0)*600)+1
    c$=right$("000"+str$(c),3)
    d=int(rnd(0)*600)+1
    d$=right$("000"+str$(d),3)
    a$(n)=a$+b$+c$+d$
next
sort a$(),1,1000
for n= 1 to 999
    print a$(n)
    if a$(n)=a$(n+1) then print "Match"
next
 

Re: Pseudo Random Number Generation in LB...
Post by tenochtitlanuk on Jul 17th, 2010, 07:19am

You could of course use one of the web's random number generators- these are driven by atmospheric noise, radioactive decay or w.h.y. You'd have to call the page and parse the result out from the html in most cases.
It is a deep physics/philosophy matter where pseudo-random shades into or is distinguishable from random!
See http://www.random.org/
RAND Corp publishes a list of a million random numbers at http://www.rand.org/pubs/monograph_reports/2005/digits.txt.zip & you could try starting at a point in it chosen by LB's own rnd( function...
Or you could buy one of the hardware generators- eg http://www.comscire.com/Products/R2000KU/ .... a tad expensive!
If you try a software prng of your own, let us know what you are trying. I can always add it to my random display/check program which at present compares four different ways...

Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 17th, 2010, 09:21am

Hi guys,

Thanks for your speedy responses. grin

I have read the link, Stefan, and am a little disturbed as it sounds a bit like Carl got it off a guy down the pub. LOL. I'm sure it's probably a reasonable algorithm especially if others such as tenochtitlanuk say they have also tested it statistically. However, I can't help but feel there may be some problem with the way it is being implemented.

Yes, you are quite right tenochtitlanuk. It seems to be successive re-runs that causes the problem to show itself, which leads me to beleive that it is something to do with the way in which LB is seeding the algorithm either at its own startup or when it builds the program. Is it seeded internally by the system time in some way? Does anyone know?

To those who inquired: No, I am not seeding the function at any point, myself.

I might be able to post some code but its part of a very large program and I would have to modify it significantly so that it would run when posted and you would have to have the patience to run it maybe 50 times or more to see the pattern, so I will hold off on that for the moment if that's ok. There is nothing mysterious about it.

With regard to Carl's request for a better PRNG, I believe the current trend is towards an algorithm called the 'Mersenne Twister'. Pseudocode for which can be found at various places around the web including at Wikipedia. I would write a function for it and bypass Carl's 'rnd' but without having tried it, I fear it would be quite slow in tokenised LB... and unfortunately my C is attrocious so I can't really write a dll.

Rod, I think you might be right about the length of the seed but again, there seems to be something odd going on whereby the higher 'bytes' of the seed seem to have a more significant effect upon the output of the function than do the lower 'bytes'... which is not what I would normally expect from a random seed.

Quote:
I suppose there are better random number generators but how would you ever know smiley


There are many statistical tests which can be performed to check entropy and thereby the quality of a pseudorandom algorithm.

LOL. I suppose I could also just use that German octapus! LOLOLOL

P.S. Does anyone know what Carl's actual algorithm is?
Re: Pseudo Random Number Generation in LB...
Post by psycho on Jul 17th, 2010, 10:30am

Coda,

I created a seed generator to try and help with this type of problem. I'm sure something better can be done but so far it's worked well for my needs. Give it a try and see if you get less predictable results.

Code:
    gosub [Seed_Generator]
    for x = 1 to 10
        print int(rnd(1)*100)
    next x
    end

[Seed_Generator]
    seed1 = time$("ms")/100000000
    randomize (seed1)
    seed2 =seed1+rnd(0)
    if seed2>1 then seed2=seed2-1
    'old fashion delay will vary by processor speed and adds random variable
    for delay = 1 to 750000
    next delay
    randomize (seed2)
    seed3 = time$("ms")/100000000+rnd(0)
    if seed3>1 then seed3=seed3-1
    randomize (seed3)
    seed4 = time$("ms")/100000000+rnd(0)
    seed = seed4-seed2
    if seed < 0 then seed = seed * (-1)
    if seed > 1 then seed=seed-1
    randomize (seed)
    return
 
 


John "Psycho" Siejkowski
Re: Pseudo Random Number Generation in LB...
Post by Rod on Jul 17th, 2010, 1:02pm

Errr..... what about my thousand iterations that didn't issue one single matching pair despite your assertion that I would see one in every fifty?

Also you implied that there were only 100 seeds, how many are there?

If Liberty BASIC's RNG does not work, prove it. (with code) It should be easy because it is as you say,predictable. wink

Quote:
There are many statistical tests which can be performed to check entropy and thereby the quality of a pseudorandom algorithm.


And how does Liberty score?

I also value Psycho's input and will be interested to see how his suggestion impact the results.
Re: Pseudo Random Number Generation in LB...
Post by tenochtitlanuk on Jul 17th, 2010, 5:36pm

Since my program specifically was repeatedly run, I don't understand your comment 'It seems to be successive re-runs that causes the problem'.
If you or anyone else has code showing 'predictability' I'll be very interested; also I'd love working code of the Mersenne twister. I've asked previously on the forums for interesting PRNGs. It could very easily be added then to my PRNG test/demos at http://www.diga.me.uk/PRNGCheck.html which is a later version of the one on my site at eduweb.
Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 20th, 2010, 03:00am

Hi guys.

Firstly let me say how much I appreciate everyone’s help and input. You guys are the best. Sorry for the delay in getting back to your questions but I haven’t been able to devote time to my project for a few days.

Secondly, I would like to say, just to dispel any thoughts to the contrary, that I LOVE LB to pieces! I think it is the most awesome tool and language in the universe and I am not here criticising it to bring it into disrepute. I am here critiquing a small aspect of it because a) I have hit upon a troubling incongruity with which I need help and as many brains and as much info as possible to solve; b) because I believe genuinely that there is a problem in either LB itself or in Smalltalk or in whatever language Smalltalk itself might be written in etc; c) because if it turns out there is a problem then I want to help Carl fix it to strengthen his great product (for everyone’s benefit) and lastly d) because, the fact that I am receiving poor and unexpected results, for whatever reason, is simply the truth and I believe the truth should always be able to be spoken without fear.

Let me now address your questions:

Quote:
If Liberty BASIC's RNG does not work, prove it. (with code) It should be easy because it is as you say,predictable. wink


Rod, the reasons I hung off on posting code were three-fold. 1. My whole program is highly dependent on external files (which you guys don’t have) and so needed heavy adaptation to run for you; 2. The section of my program involved in the issue was both particularly highly dependent on external files and variables set up elsewhere in the program and 3. because it appears that there is some strange critical dependence on initial conditions component involved, whereby small changes to the program (like giving you a slightly adapted version of the algorithms that will run on your computers without externalities) seems at times to affect the outcome. I have noticed this phenomenon with LB before with the well known ‘groupbox draw error’. The placement and addition or subtraction of even rem’ed out code in the source file can alter how the ‘groupbox draw error’ manifests at run time. Ie. whether or not it occurs at all and which gbox or gboxes are affected. I don’t understand why… I don’t understand how… I just know that it does and it seems something similar is at play in this problem too. I have however, produced code that will run on your computers and will show the problem and have posted it below.

Quote:
And how does Liberty score?


In statistics, one usually only runs tests for borderline cases where the answer is not obvious. As my code below demonstrates, as I am only getting about 4 possible initial outputs, the results are, as sad as it makes me to say it, and without wanting to sound facetious or rude, you would have to agree with me under such circumstances beyond poor and thus beyond worth testing. If you are interested I think tenochtitlanuk may have run some stat tests on it from what he is saying.

Quote:
Also you implied that there were only 100 seeds, how many are there?


I don’t know. What I do know is that with good generators of randomness, small changes in input should be able randomly to lead to small or large changes in output and that for argument’s sake, if we have a seed XXXXXXXXXXXXXXXX and we change the seed thusly: XXXXXXXXXXXXXXXY or thusly: YXXXXXXXXXXXXXXX neither change should have any greater or less a likely baring on the output. As I have said, the random number generator used in LB does not seem to exhibit those qualities. Lower bytes can be expected to produce less change. I also know that PRNG’s can have larger internal seeds than one is sometimes allowed to seed them with. Ie. there are A to Z starting points but feedback of the looping of the algorithm produces internal states or ‘seeds’ outside that range on successive loops. Why? I don’t know. This is always an arbitrary decision by the language’s creator, perhaps in an attempt to simplify the seeding process but always cripples the potential of the algorithm.

Quote:
Since my program specifically was repeatedly run, I don't understand your comment 'It seems to be successive re-runs that causes the problem'.


Tenochtitlanuk, I’m sorry I was a little unclear about this. You need to re-run LB, itself, not just the program to see the fault. Doing so causes the program to behave in the same way as compiling to token code and re-running from starting the interpreter engine… In fact if you plan to test the code I post below for yourself, that is how I recommend you run it (after compiling to a folder) to save yourself the time and hassle of closing and restarting the LB environment

Quote:
I'd love working code of the Mersenne twister. I've asked previously on the forums for interesting PRNGs..


I’m sorry, I don’t have any working LB code for the Mersenne Twister but I will be certain to let you have it if I write it. I really appreciate your help. In the meantime, pseudocode and many copies of working code in other languages can be found at wikipedia if you are interested.

Quote:
I created a seed generator to try and help with this type of problem.


Thankyou for sharing your code, Psycho. I haven’t had chance to check it out properly yet but rest assured I will. I was already planning to test randomising the seed myself using the system time between successive ‘throws’ but if the things I have mentioned above turn out to be true then it may not be of much help. I will get back to you.

Continued in next post...
Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 20th, 2010, 03:02am

Here is some code that shows the problem. As I say, you will need either to compile to .exe before running or restart LB itself for the problem to show itself. The program loops 1-X times (or in this demo version 1-1 times, as set by the variable, ListNo) inside that main loop it repeats 1-Y times (or in this demo version 1-1 times, as set by the variable, NameNo) and then also inside the main loop, repeats most of the same actions as in the secondary loop 1 last time to account for a special case of the variables in my program. The only changes I have made to my original code are that I have isolated the code concerned, I have artificially set up the required variables, I have rem’ed out references to external files and I have printed the results of the random number generation and various program variables to a window for inspection.

Code:
'Start Variable initialisation for posted demo ---

DIM alphafilter(8, 26), qtyRecords(8, 26)

GenderMode$ = "g"
ListNo = 1 'do the whole operation once for the purposes of the posted demo
NameNo = 1 'loop the first part once for the purposes of the posted demo

for c = 1 to 8
    for cc = 1 to 26
        alphafilter(c, cc) = 1 'ie all letters are chosen (ticked) for all 8 filters
    next cc
next c

for c = 1 to 3
    for cc = 1 to 26
        qtyRecords(c, cc) = 50 * cc 'set all records lengths to some abitrary but different amount for purposes of posted demo
    next cc
next c

'---End Variable initialisation for posted demo

'Start Actual program code with externalities rem'ed so that it will run ---

[MakeButtonClick]

for c = 1 to ListNo
        for cc = 1 to NameNo

            if SpecificName$(cc) <> "" then RanName$ = SpecificName$(cc): goto [skipcalc1]

            'set gender or choose one if mixed
            if GenderMode$ = "m" then
                gn = int(rnd(1)* 2) + 1
                    if gn = 1 then
                        gn$ = "g"
                    end if
                    if gn = 2 then
                        gn$ = "b"
                    end if
                else
                gn$ = GenderMode$
            end if

            'choose a letter and reject if not ticked
            [TryAgain1]
            nm = int(rnd(1)* 26) + 1
            if alphafilter(cc, nm) = 0 AND Filtertype(cc) = 1 then goto [TryAgain1] 'choose another random number if the letter is exclused (will never trip in this demo as all letters are set to 1)

            'weighting algorthm for nm
            wn = rnd(1)

            totalpopulation = 0
            if gn$ = "g" then nv = 1
            if gn$ = "b" then nv = 2
            if Filtertype(cc) = 1 then
                for ccc = 1 to 26
                    totalpopulation = totalpopulation + alphafilter(cc,ccc) * qtyRecords(nv,ccc)
                next ccc
                    else
                        for ccc = 1 to 26
                            totalpopulation = totalpopulation + qtyRecords(nv,ccc)
                        next ccc
            end if

            if wn > qtyRecords(nv,nm)/totalpopulation then goto [TryAgain1]

            'open file and get data

            'open "Rand\r"+gn$+CHR$(nm + 96) for random as #1 len=18
            'field #1, 18 as RanName$

            'qtyBytes = lof(#1)
            'the above lines are rem'ed for purposes of posted demo

            rn = int(rnd(1)* qtyRecords(nv,nm)) + 1

            'gettrim #1, rn
            'close #1
            'the above lines are rem'ed for purposes of posted demo

            [skipcalc1]

            WholeName$ = WholeName$ +" "+ RanName$

            print nm, rn, wn, qtyRecords(nv,nm), totalpopulation, qtyRecords(nv,nm)/totalpopulation
            'the above line is for the purposes of the posted demo only to show the random numbers nm, rn, wn and some calculated results

        next cc

'do special case of 8th and last category

            if SpecificName$(8) <> "" then RanName$ = SpecificName$(8):goto [skipcalc2]

            'choose a letter and reject if not ticked
            [TryAgain2]
            nm = int(rnd(1)* 26) + 1
            if alphafilter(8, nm) = 0 AND Filtertype(8) = 1 then goto [TryAgain2] 'choose another random number if the letter is exclused (will never trip in this demo as all letters are set to 1)

            'weighting algorithm for nm
            wn = rnd(1)

            totalpopulation = 0
            if Filtertype(8) = 1 then
                for ccc = 1 to 26
                    totalpopulation = totalpopulation + alphafilter(8,ccc) * qtyRecords(3,ccc)
                next ccc
                    else
                        for ccc = 1 to 26
                            totalpopulation = totalpopulation + qtyRecords(3,ccc)
                        next ccc
            end if


            if wn > qtyRecords(3,nm)/totalpopulation then goto [TryAgain2]
            'open file and get data

            'open "Rand\rs"+CHR$(nm + 96) for random as #1 len=18
            'field #1, 18 as RanName$

            'qtyBytes = lof(#1)
            'qtyRecords = qtyBytes/18
            'the above lines are rem'ed for purposes of posted demo

            rn = int(rnd(1)* qtyRecords(3,nm)) + 1

            'gettrim #1, rn
            'close #1
            'the above lines are rem'ed for purposes of posted demo

            [skipcalc2]

            WholeName$ = WholeName$ +" "+ RanName$

            'print #main.texteditNameReturn, WholeName$
            'the above lines are rem'ed for purposes of posted demo

            WholeName$ = ""
            print nm, rn, wn, qtyRecords(3,nm), totalpopulation,  qtyRecords(3,nm)/totalpopulation
            'the above line is for the purposes of the posted demo only to show the random numbers nm, rn, wn and some calculated results
    next c

'--- End Actual program code with externalities rem'ed so that it will run

wait
 

As you will see, the only 4 combinations that are forthcoming are as follows:

15 193 0.11952991e-1 750 17550 0.42735043e-1
23 287 0.01538520 1150 17550 0.65527066e-1

12 586 0.32526338e-1 600 17550 0.34188034e-1
15 193 0.11952991e-1 750 17550 0.42735043e-1

6 178 0.14179122e-1 300 17550 0.17094017e-1
15 193 0.11952991e-1 750 17550 0.42735043e-1

15 449 0.20410529e-1 750 17550 0.42735043e-1
15 193 0.11952991e-1 750 17550 0.42735043e-1

The most important numbers are in the first 3 columns. The first column is a weighted or ‘windowed’ (if you like) random number. One expects this number NOT to exhibit ‘normal’ ‘rectangular window’ random behaviour because it has been programmed NOT to behave that way. One would expect, however a much greater variance than always the same 4 sets of numbers. The second and third column are the most interesting of all. These are supposedly ‘normal’ unweighted and independently drawn random numbers and yet they seem to exhibit complete dependence on the previous draws!!!!!!!!!!!!!! This would seem to indicate that either the period of LB’s PRNG is way too short or that the PRNG is being seeded by LB in some poor way with a reduced number of initial seeds or that there is some other inherent bad quality to the PRNG being used. It is hard to be a detective and work backwards to pinpoint the exact problem. I am hoping Carl weighs in on this.

Continued in next post...
Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 20th, 2010, 03:03am

To prove a point that there is nothing mysterious or bad about my programming (LOL apart for my preference for goto statements rather than do-while loops etc which some neo-purists out there will no doubt cringe at… sorry I don’t care about processor ticks at this speed… or arbitrary impositions of style-police at this point in life LOLOLOL), I have imported my exact code into the very old and ‘primitive’ Qbasic as a test and posted it below for anyone who wants to try it in that language to rule out my code as a contributing factor. I have made no changes to the code for the Qbasic version, except these few inconsequential necessities: 1. Line labels have been converted to Qbasic format so the program will run; 2. The unnecessary & syntactically incorrect ‘wait’ command has been removed from the end and 3. The necessary command ‘Randomize Timer’ (supposedly already underlyingly executed in LB and therefore unnecessary and certainly syntactically incorrect) has been added to the start. You will find successive runs (even after exiting Qbasic) produce very different and quite random results, as one would expect from the code.

Code:
'QBASIC CODE
'Start Variable initialisation for posted demo ---

RANDOMIZE TIMER

DIM alphafilter(8, 26), qtyRecords(8, 26)

GenderMode$ = "g"
ListNo = 1 'do the whole operation once for the purposes of the posted demo
NameNo = 1 'loop the first part once for the purposes of the posted demo

FOR c = 1 TO 8
    FOR cc = 1 TO 26
        alphafilter(c, cc) = 1 'ie all letters are chosen (ticked) for all 8 filters
    NEXT cc
NEXT c

FOR c = 1 TO 3
    FOR cc = 1 TO 26
        qtyRecords(c, cc) = 50 * cc 'set all records lengths to some abitrary but different amount for purposes of posted demo
    NEXT cc
NEXT c

'---End Variable initialisation for posted demo

'Start Actual program code with externalities rem'ed so that it will run ---

MakeButtonClick:

FOR c = 1 TO ListNo
        FOR cc = 1 TO NameNo

            IF SpecificName$(cc) <> "" THEN RanName$ = SpecificName$(cc): GOTO skipcalc1

            'set gender or choose one if mixed
            IF GenderMode$ = "m" THEN
                gn = INT(RND(1) * 2) + 1
                    IF gn = 1 THEN
                        gn$ = "g"
                    END IF
                    IF gn = 2 THEN
                        gn$ = "b"
                    END IF
                ELSE
                gn$ = GenderMode$
            END IF

            'choose a letter and reject if not ticked
TryAgain1:
            nm = INT(RND(1) * 26) + 1
            IF alphafilter(cc, nm) = 0 AND Filtertype(cc) = 1 THEN GOTO TryAgain1 'choose another random number if the letter is exclused (will never trip in this demo as all letters are set to 1)

            'weighting algorthm for nm
            wn = RND(1)

            totalpopulation = 0
            IF gn$ = "g" THEN nv = 1
            IF gn$ = "b" THEN nv = 2
            IF Filtertype(cc) = 1 THEN
                FOR ccc = 1 TO 26
                    totalpopulation = totalpopulation + alphafilter(cc, ccc) * qtyRecords(nv, ccc)
                NEXT ccc
                    ELSE
                        FOR ccc = 1 TO 26
                            totalpopulation = totalpopulation + qtyRecords(nv, ccc)
                        NEXT ccc
            END IF

            IF wn > qtyRecords(nv, nm) / totalpopulation THEN GOTO TryAgain1

            'open file and get data

            'open "Rand\r"+gn$+CHR$(nm + 96) for random as #1 len=18
            'field #1, 18 as RanName$

            'qtyBytes = lof(#1)
            'the above lines are rem'ed for purposes of posted demo

            rn = INT(RND(1) * qtyRecords(nv, nm)) + 1

            'gettrim #1, rn
            'close #1
            'the above lines are rem'ed for purposes of posted demo

skipcalc1:

            WholeName$ = WholeName$ + " " + RanName$

            PRINT nm, rn, wn, qtyRecords(nv, nm), totalpopulation, qtyRecords(nv, nm) / totalpopulation
            'the above line is for the purposes of the posted demo only to show the random numbers nm, rn, wn and some calculated results

        NEXT cc

'do special case of 8th and last category

            IF SpecificName$(8) <> "" THEN RanName$ = SpecificName$(8): GOTO skipcalc2

            'choose a letter and reject if not ticked
TryAgain2:
            nm = INT(RND(1) * 26) + 1
            IF alphafilter(8, nm) = 0 AND Filtertype(8) = 1 THEN GOTO TryAgain2 'choose another random number if the letter is exclused (will never trip in this demo as all letters are set to 1)

            'weighting algorithm for nm
            wn = RND(1)

            totalpopulation = 0
            IF Filtertype(8) = 1 THEN
                FOR ccc = 1 TO 26
                    totalpopulation = totalpopulation + alphafilter(8, ccc) * qtyRecords(3, ccc)
                NEXT ccc
                    ELSE
                        FOR ccc = 1 TO 26
                            totalpopulation = totalpopulation + qtyRecords(3, ccc)
                        NEXT ccc
            END IF


            IF wn > qtyRecords(3, nm) / totalpopulation THEN GOTO TryAgain2
            'open file and get data

            'open "Rand\rs"+CHR$(nm + 96) for random as #1 len=18
            'field #1, 18 as RanName$

            'qtyBytes = lof(#1)
            'qtyRecords = qtyBytes/18
            'the above lines are rem'ed for purposes of posted demo

            rn = INT(RND(1) * qtyRecords(3, nm)) + 1

            'gettrim #1, rn
            'close #1
            'the above lines are rem'ed for purposes of posted demo

skipcalc2:

            WholeName$ = WholeName$ + " " + RanName$

            'print #main.texteditNameReturn, WholeName$
            'the above lines are rem'ed for purposes of posted demo

            WholeName$ = ""
            PRINT nm, rn, wn, qtyRecords(3, nm), totalpopulation, qtyRecords(3, nm) / totalpopulation
            'the above line is for the purposes of the posted demo only to show the random numbers nm, rn, wn and some calculated results
    NEXT c

'--- End Actual program code with externalities rem'ed so that it will run
 

I don’t know what else to say. I guess for the moment I will have to write my own function.
Re: Pseudo Random Number Generation in LB...
Post by tsh73 on Jul 20th, 2010, 05:03am

There no need to convert stuff to QBASIC or understand Coda's code. Look at this:

Code:
for i = 1 to 100
    print i, int(rnd(1)*10000)
next
 


Run basic from a shortcut - load "untitled.bas" from LRU list - run program - copy results into Excel.

I did that 6 times.
Then I seached for first number from first column, in other columns.
That's that I got:
2nd test - numbers from 40 to 100 precisely matched first test (1..61) (verified with Excel formula, not with just eyes)
3rd - numbers from 23 to 100 precisely matched first test
4th - no match at all
5th - again, from 40 precisely matched first test
6th - from 22 precisely matched first test

So while I do not know if RND itself statistically sound, it's obvious that seeding it on a LB start is really flacky.

*and this should go as BUG report*

EDIT:
but if you seed it yourself, then no match found (again, 6 tests)
Code:
ms = time$("ms")/(24*60*60*1000)
randomize ms

for i = 1 to 100
    print i, int(rnd(1)*10000)
next
 


So may be writing your own generator is a bit too much?
Re: Pseudo Random Number Generation in LB...
Post by Rod on Jul 20th, 2010, 06:41am

Ha!, boy do I love clarity. For me the problem resolves to the point CODA makes about the seed value and it's impact on the generator and it is the same whether you seed inside the program or on start up. Neither of these actions currently result in a large enough change or disturbance.

Code:
seed$=".11111111111111111"
for n=17 to 1 step -1
    randomize, val(right$(seed$,n))
    print int(rnd(0)*1000)
next
 


It's only relatively large changes in the seed value that trigger change, the RNG would be more robust if smaller changes in the seed value resulted in larger disturbance.

Ideally for me the result of the above code should have produced widely varying results, still predictable for each individual seed entered but they should definitely not be ordered as they are.

That's my ill informed tuppence worth. All you guys should check out the Rosetta thread and read up on the RNG tasks.
Re: Pseudo Random Number Generation in LB...
Post by tsh73 on Jul 20th, 2010, 07:06am

You probably mean left$? Help file says randomize should be seeded with 0..1 numbers.

But yes, problem is apparent either way.

EDIT: seeding with big values is bad
Code:
randomize 11111111111111111
z=rnd(1)
z=rnd(1)
 

It dies with "divide by zero" error.

EDIT2:
well, small seed changes produces small initial difference. But I thought, it doesn't matter much because later sequience surely should diverge?
Alas, no - see for yourself.
*very bad*
Code:
seed$=".11111111111111111"
for n=17 to 1 step -1
    rr = val(left$(seed$,n))
    randomize rr
    print "***", n, rr,"***"
    for i = 1 to 10
        print i, int(rnd(0)*1e17)
    next
next
 

Re: Pseudo Random Number Generation in LB...
Post by uncleBen on Jul 20th, 2010, 10:19am

When you don't seed the generator, it appears to continue the sequence from the previous run (the seed is stored somewhere).

First run:

Code:
randomize 0.5
for i = 1 to 10
    print int(rnd(1) * 100); " ";
next
 


Then run the same without randomizing:
Code:
for i = 1 to 10
    print int(rnd(1) * 100); " ";
next
 


And finally generate 20 values with the same seed

Code:
randomize 0.5
for i = 1 to 20
    print int(rnd(1) * 100); " ";
next
 


As to making a mersenne twister DLL (in C++, uses Boost as external library): http://codepad.org/1W67PuRW

The resulting DLL is around 500 KB, though: boost seems to pull in C++ I/O streams which should be a complete waste of space here.

Usage example with randtest.bas

Code:
    'Test the random number generator to see if it can draw
    'uniformly random dots!
    WindowWidth = 410
    WindowHeight = 440
    open "random generator test" for graphics as #draw
    open "C:/cprogrammid/lb_random.dll" for dll as #rand
    calldll #rand, "SeedWithTime", result as void 'else uses same seed each time
    print #draw, "trapclose [quit]"
    print #draw, "down ; size 2"
    for x = 1 to 5000
        print #draw, "place "; Rand(); " "; Rand()
        print #draw, "go 1"
    next x
    close #rand
    wait

[quit]
    close #draw
    end

function Rand()
    calldll #rand, "RandomDouble", result as double
    Rand = int(result * 400)
end function

 


Re: Pseudo Random Number Generation in LB...
Post by tsh73 on Jul 20th, 2010, 1:31pm

uncleBen,
I didn't quite get - did you post the DLL?
If not please do, so folks doesn't have to install GCC + boost just to try it wink
Re: Pseudo Random Number Generation in LB...
Post by Rod on Jul 20th, 2010, 3:25pm

Or just share your views or indeed the .bmp!

Are we all agreed it is the seeding that is the weakness? Bar that I believe the RNG is as robust as many others.

I wonder if the seeding can be tweaked separately from the RNG itself?

Someone better versed than I should post on the wish list.
Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 23rd, 2010, 06:22am

Hi Guys,

Thanks for all your help and info. grin Sorry, my demo code was more complicated than it turned out was required. rolleyes I couldn't get the problem to show on my computer with anything but my actual program code... what did I say about critical dependence on initial conditions... tongue

Quote:
Are we all agreed it is the seeding that is the weakness?

Yes, I think you are right, Rod, that that is most likely the case. I have had a look at tenochtitlanuk's program. It doesn't constitute rigorous statistical testing but the visual presentation would indeed likely show certain major flaws. I think there are two problems with the seeding (a) LB's internal initial seeding and (b) the seeding that is allowed through the LB 'randomize' function. Both definately need an overhaul. I would feel better though, if I knew for sure that LB contained a well known, well documented and well tested algorithm and it would be nonetheless nice to have the Mersenne Twister or another similar newer better algorithm included in a future update. These fields of investigation move forward all the time and it is always best to have something up-to-date. grin

tenochtitlanuk, BTW, just so you know, I have had a few probs with running your program on my system. Win 98SE. When I choose the internal LB rnd function, the program crashes before the 'auto-scaling' kicks in. Also, the graphical window on the right draws with black horizontal striations which is different to how you picture it on your web page. Hope that is helpful information to you.

UncleBen, thankyou sooo much for posting the info about creating the mersenne twister in a dll file and invoking it from LB. I downloaded the boost libraries and have unpacked them but I cannot seem to build the dll using my Borland C++ 4.52 compiler. I have spent all day trying, in fact (thus, reminding me how I find trying to get C or C++ to do anything is like trying to play 'pick-up-sticks' in boxing gloves and why I LOVE LB so darned much!!!!) LOL. I think at least 25% or more of the problem with C for me is the irritatingly complicated IDE's!!! Anyways, further investigation reveals that I have to build something in DOS called 'jam' first and then use that to build something called 'buildboost' or something and all of that crashes and I think it's all incompatible with windows 98SE anyway. I'm not sure. I don't suppose there is somewhere we could get a pre-built dll? wink Please... please...
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Jul 23rd, 2010, 11:41am

I've created a different DLL, if you wish. It's 7KB compiled, and is based on public-domain code of the Mersenne Twister. Really, I think the only difference from uncleBen's DLL is that this one returns integers, not floats. (If you want floats, I'm sure it can be added pretty easily.) It also does not yet have an option for a user-specified seed, if you want that, I'll add it grin

Here's the DLL and LB code. I included VS2008 source code, as well.

http://www.box.net/shared/oq5m3a0z4d
Re: Pseudo Random Number Generation in LB...
Post by tenochtitlanuk on Jul 23rd, 2010, 5:23pm

Glad you've tied down this randomize bug, tho' it has never been a problem in the ways I use rnd().
My article DID warn you of bugs in my prog. I haven't such early versions as 95 or 98 to try my prog on, but am a bit surprised it fails 'cos I was using LB1.4 back on ME.
The horizontal black lines are only at low counts- there are less numbers in the 'bins' at that stage than the vertical graph size. They disappear after a few scalings. For me!
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Jul 24th, 2010, 04:38am

on Jul 23rd, 2010, 11:41am, Chris Iverson wrote:
Here's the DLL and LB code. I included VS2008 source code, as well.

http://www.box.net/shared/oq5m3a0z4d


The contents of test.bas seem to have been removed, since the archive includes a file of zero length.

Sure one needs to call the Init and the getRandom functions, but not all people are able to get this information from the C source code.

Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Jul 24th, 2010, 04:48am

Here is a simple example of using the DLL.

Code:
    open "MersTwistLB.dll" for DLL as #MersTwist

    calldll #MersTwist, "Init", result as void

    for i = 1 to 10
        calldll #MersTwist, "getRandom", Random as uLong

        print using("###",i), using("#############",Random), using("#.##############",Random / hexdec("FFFFFFFF"))
    next

    close #MersTwist
    end
 

Re: Pseudo Random Number Generation in LB...
Post by tenochtitlanuk on Jul 24th, 2010, 05:50am

Thanks for the demo- and to initialize it to a new seed/ randomize? I generally want a non-predictable PRNG. So yes, Chris, if possible...
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Jul 24th, 2010, 11:26am

Well, right now, you could call Init() again, and it would re-seed with the current time again. I'll throw in an option to allow seeding with a custom number, too.



My apologies for the test.bas file; I'm not sure how that happened.

EDIT: Okay, rebuilt the DLL with a custom seed feature, and also renamed Init() to SeedWithTime(), as it's a more accurate name.

http://www.box.net/shared/oq5m3a0z4d

I'll post the LB code here as well as in the archive, just in case it disappears again.

Code:
open "MersTwistLB" for DLL as #MT

'SeedWithTime() used to be Init(), but this
'name is more accurate
CallDLL #MT, "SeedWithTime",_
ret as void

'getRandom() returns a ulong, an integer,
'not a float
CallDLL #MT, "getRandom",_
ret as uLong

print ret

CallDLL #MT, "getRandom",_
ret as uLong

print ret

'Seed() allows you to set your own seed.
CallDLL #MT, "Seed",_
1234567 as long,_
ret as void

CallDLL #MT, "getRandom",_
ret as ulong

print ret

CallDLL #MT, "getRandom",_
ret as ulong

print ret

close #MT 

Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Jul 25th, 2010, 6:09pm

I would include a getRandomFloat function too.

This would divide the result of the getRandom function by the upper limit.

This way we could better compare both RNGs.

Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Jul 25th, 2010, 7:28pm

The function could look like this:

C - Code:
MERSTWISTLB_API double getRandomFloat(void)
{
	return (double)mt_random() / (double)0xFFFFFFFF;
}
 

Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Jul 29th, 2010, 12:30pm

Thanks, Stefan!

I updated the DLL, available from the same URL.

http://www.box.net/shared/oq5m3a0z4d
Re: Pseudo Random Number Generation in LB...
Post by Rod on Jul 29th, 2010, 2:01pm

I assume we have fixed the seeding with this version, I have not tried the repeated runs test. I did try this.

Code:
    'Test the new random number generator to see if it can draw
    'uniformly random dots!
    WindowWidth = 410
    WindowHeight = 440
    open "random generator test" for graphics_nf_nsb as #draw
    print #draw, "trapclose [quit]"
    print #draw, "down ; size 1"

    open "MersTwistLB" for DLL as #mt

    'we must seed it else we get 0
    calldll #mt, "SeedWithTime",ret as void

    div=4294967296
    for x = 1 to 50000
        scan
        calldll #mt, "getRandom",retX as uLong
        calldll #mt, "getRandom",retY as uLong
        print #draw, "place "; int(retX/div*400); " "; int(retY/div*400)
        print #draw, "go 1"
    next x

    wait

    [quit]
    close #draw
    end
 


Now all credit to Chris, this is stunning. We have an alternative "state of the art" RNG for those folks that feel the need.

It might be my code but it does run a tad slower than the native RNG. Now that may not be an issue but I have a feeling that folks that do delve into RNG's usually want lots of numbers.

So here is my question, is there a simpler fix to sort the start up seeding problem? Can we run a simple bit of code at the front of repeated runs to seed the native RNG and thereafter obtain it's benefits?

I say this having run both for a while and I see not one jot of difference between the images produced by both routines over time.
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Jul 29th, 2010, 3:28pm

For the "running slower" thing, I can see two optimizations to your code.

The first one, if you're using my old DLL version, is to replace the "int(retX/div*400) and "int(retY/div*400)" with "retX mod 400" and "retY mod 400". Both seem to work just as well, but according to LB Assist's profiler, the 'mod' line executes in 1/5th of the time the other line does.

Of course, to go even further, since I added a getRandomFloat() function to my DLL, just use this:

Code:
    'Test the new random number generator to see if it can draw
    'uniformly random dots!
    WindowWidth = 410
    WindowHeight = 440
    open "random generator test" for graphics_nf_nsb as #draw
    print #draw, "trapclose [quit]"
    print #draw, "down ; size 1"

    open "MersTwistLB" for DLL as #mt

    'we must seed it else we get 0
    calldll #mt, "SeedWithTime",ret as void

    for x = 1 to 50000
        scan
        calldll #mt, "getRandomFloat",retX as double
        calldll #mt, "getRandomFloat",retY as double
        print #draw, "place ";int(retX * 400); " "; int(retY * 400)
        print #draw, "go 1"
    next x

    wait

    [quit]
    close #mt
    close #draw
    end 



According to the profiler, this version takes even less time than the MOD version, but should have the same results as your version.
Re: Pseudo Random Number Generation in LB...
Post by Rod on Jul 30th, 2010, 03:17am

Yes it is a lot faster that way, the GetRandomFloat and Int combintion seems fastest.
Re: Pseudo Random Number Generation in LB...
Post by bluatigro on Jul 30th, 2010, 03:29am

i fount the folowing rnd function
on internet [ WARNING : this is c++ ]
Code:
  function IntNoise(32-bit integer: x )
     x = (x<<13) ^ x;
    return ( 1.0 - ( (x * (x * x * 15731 + 789221) + 1376312589) & 7fffffff) / 1073741824.0);    
  end IntNoise function
 

i tryed to make basic from that :
Code:
for i = 0 to 10
  x = IntNoise( x )
  print x
next i
END
function IntNoise( x )
  x = ( x * 2 ^ 13 ) xor x
  hx = x * x * 15731 + 789221
  IntNoise = ( 1.0 - ( x * hx + 1376312589 ) mod byte4( 127 , 255 ,255 , 255 ) / 1073741824.0 ) 
end function
function byte4( a , b , c , d )
  byte4 = a * 256 ^ 3 + b * 256 ^ 2 + c * 256 + d
end function
 

fun : always the same results
what in some cases can by handy
you shout get : -1 < IntNoise < 1
i did not test this many times

randomization shout work like this
Code:
  dummy = IntNoise( timer$( "milliseconds" ) ) 
 


dont ask me how this works
i dont know exactly
i works whit prime numbers
but i think you can use this
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Jul 30th, 2010, 04:27am

The original article, where the article found by Chris is based on is at Random Number Generation and includes another RNG too.



@Rod,

Any native LB function will always be faster, than any code written by the user.



@Chris,

Since you mentioned the profiler, you did not hit Alt+O in the test.bas wink

Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 30th, 2010, 10:12am

For those who requested an LB implementation of The Mersenne Twister, I've coded it! ;)

I've tested it over 2000 number generations against other implementations using the test seed 456231. All appears well. ;D

If you find any bugs, please let me know. You are all most welcome to use the code in your own programs. ;) It's quite well documented within the code.

Here it is! :P

Code:
' "The Mersenne Twister (MT19937 algorithm) in Liberty BASIC" by Napier Thompson.

'incorporating a 'seed generator' algorithm and bitshift algorithms by Napier Thompson  2010.

'This program is based on the Mersenne Twister (MT19937 algorithm) created by Makoto Matsumoto and Takuji Nishimura.

'This Liberty BASIC implementation of the Mersenne Twister algorithm  Napier Thompson 2010.

'This program may be used in whole or part and modified in your own projects without specific permission from the author._
'All I ask is that the author, Napier Thompson, is credited in at least one and preferably all of the following locations_
'(if your program possesses them) in order of descending preference. a) Your program's about box, b) your program's_
'installation literature c) any of your program's relevant documentation. If your program does not possess any of the_
'above, the author MUST be credited prominently somewhere else.

'The author of this program does not guarantee the program's accuracy or that it is error free. Use at your own risk.



' --- START TWISTER SETUP CODE

'Initialise SeedHoler array, index variable, Seed variable and OddEven array

GLOBAL dex
GLOBAL Seed
DIM SeedHolder(624)
OddEven(1) = 0: OddEven(2) = hexdec("&H9908B0DF")
dex = 0

'Rem the two lines below out in your own program.

print "Please wait... Generating a seed and initialising the Mersenne Twister generator's internal state..."
print""

'Call seed generating subroutine which generates an initial 32-bit seed based on time and date.
'This subroutine must be called prior to generating a random number and prior to calling the subroutine 'SeedTwister'.
'Reseeding and hence, recalling this and the 'SeedTwister' sub is time intensive and should not be required however, if_
'you want to reseed you may do so at any time. Just make sure to follow this up with a call to the 'SeedTwister' sub.

'NOTE: If you want to use a constant test seed then you may set the seed yourself by bypassing the call to 'SeedGenerator'_
'and assigning a 32 bit integer (0 to 2^32-1) to the variable, 'Seed' before calling 'SeedTwister'.
'ie... --->

'Seed = "your seed" 'Now don't call 'SeedGenerator'.

call SeedGenerator


'Call seeding subroutine.
'This subroutine must be called prior to generating a random number and after calling the subroutine 'SeedGenerator'.
'Reseeding and hence, recalling this sub is time intensive and should not be required however, if you want to reseed you_
'may do so at any time. Just make sure to precede a call to this sub with a call to the 'SeedGenerator' sub or a 'Seed = x'_
'statement.

'NOTE: If you want access to all 19968 bits of the generator's internal state for seeding purposes then simply bypass both_
'the 'SeedGenerator' and 'SeedTwister' calls and assign 624 32-bit integers (0 to 2^32-1) of your choice to the array,_
'SeedHolder(x) for values of x = 1 to 624. For most purposes this should not be necessary and is unwise unless you know_
'what you are doing.
'ie... --->

'for i to 1 to 624
    'Seed = "your values from a 'read' & 'data' statement or the like"
    'SeedHolder(i) = Seed
'next i 'Now don't call 'SeedGenerator' or 'SeedTwister'.

call SeedTwister


'The Mersenne Twister PRNG is now running and the functions, 'TwisterReal32' and 'TwisterInt32' may now be called. Both_
'take one dummy argument just like the Liberty BASIC RND function ie. RND(1) so... TwisterReal32(1) or TwisterInt32(1).

'NOTE: The Program updates the seed array for every 624 random number that you generate. This means there is a longer_
'delay in the algorithm every 624 numbers but this cannot be avoided as it is how the Mersenne Twister works. It happens_
'in all implementations, it is just less noticeable in compiled languages.

' END TWISTER SETUP CODE ---



' --- START MAIN PROGRAM CODE

'Your main program goes here. This sample program produces 1000 random integers (shown in decimal) & 1000 random real_
'numbers (floating point numbers) using the Mersenne Twister algorithm.

for i = 1 to 200
    for ii = 1 to 5
        MakeNumber(ii) = TwisterInt32(1)
    next ii
    print Using("##########", MakeNumber (1)), Using("##########", MakeNumber (2)), Using("##########", MakeNumber (3)),_
    Using("##########", MakeNumber (4)), Using("##########", MakeNumber (5))
next i

print""

for i = 1 to 200
    for ii = 1 to 5
        MakeNumber(ii) = TwisterReal32(1)
    next ii
    print Using("#.########", MakeNumber (1)), Using("#.########", MakeNumber (2)), Using("#.########", MakeNumber (3)),_
    Using("#.########", MakeNumber (4)), Using("#.########", MakeNumber (5))
next i

end

' END MAIN PROGRAM CODE ---



' --- START FUNCTIONS & SUBROUTINES CODE


'Use this function when you want a random number.
'Returns a Real (Floating Point) number on the interval 0 to 0.999999999...
'(The same interval as Liberty BASIC's RND function).

FUNCTION TwisterReal32(dummy)

    TwisterReal32 = TwisterInt32(1) * (1/hexdec("&H100000000"))

END FUNCTION


'Use this function when you want a random number.
'Returns a 32 bit integer on the interval 0 to 2^32-1.

FUNCTION TwisterInt32(dummy)

    if dex = 0 then

        for i = 0 to 226
            y = (SeedHolder(i + 1) AND hexdec("&H80000000")) OR (SeedHolder(i + 2) AND hexdec("&H7FFFFFFF"))
            SeedHolder(i + 1) = SeedHolder(i + 397 + 1) XOR RSHIFT32(y,1) XOR OddEven((y AND 1) + 1)
        next i

        for i = 227 to 622
            y = (SeedHolder(i + 1) AND hexdec("&H80000000")) OR (SeedHolder(i + 2) AND hexdec("&H7FFFFFFF"))
            SeedHolder(i + 1) = SeedHolder(i - 227 + 1) XOR RSHIFT32(y,1) XOR OddEven((y AND 1) + 1)
        next i

        y = (SeedHolder(624 - 1 + 1) AND hexdec("&H80000000")) OR (SeedHolder(0 + 1) AND hexdec("&H7FFFFFFF"))
        SeedHolder(624 - 1 + 1) = SeedHolder(397 - 1 + 1) XOR RSHIFT32(y,1) XOR OddEven((y AND 1) + 1)

    end if

    y = SeedHolder(dex + 1)
    y = y XOR RSHIFT32(y,11)
    y = y XOR (LSHIFT32(y,7) AND hexdec("&H9D2C5680"))
    y = y XOR (LSHIFT32(y,15) AND hexdec("&HEFC60000"))

    dex = (dex + 1) mod 624

    TwisterInt32 = y XOR RSHIFT32(y,18)

END FUNCTION


'Subroutine to generate a 32 bit seed from &H00000000 to &HFFFFFFFF based on current date and time.
'All possible combinations from &H00000000 to &HFFFFFFFF are possible over a 256-day period with slightly odd distribution_
'where some numbers occur 1/8 more often than other numbers. This is due to the amount of milliseconds that occur in_
'a 24 hour period.

SUB SeedGenerator

    Seed1 = int(time$("milliseconds") / 10) AND hexdec("&HFFFFFF")
    Seed2 = date$("days") AND hexdec("&HFF")
    Seed = Seed2 * hexdec("&H1000000") + Seed1

END SUB


'Subroutine to seed and reseed the PRNG.

SUB SeedTwister

    SeedHolder(1) = Seed AND hexdec("&HFFFFFFFF")
    for i = 1 to 623
        SeedHolder (i + 1) = (hexdec("&H6C078965") * (SeedHolder(i) XOR RSHIFT32(SeedHolder(i),30)) + i) AND hexdec("&HFFFFFFFF")
    next i

END SUB


'This function shifts bits in 32 bit numbers right with no carry ie. they are not folded back and are lost at the lower end.
'This is equivalent to 'LSR' in some assemblers.

FUNCTION RSHIFT32(Number, BitShift)

    For c = 1 To BitShift
        Number = Int((Number AND hexdec("&HFFFFFFFE")) / 2)
    Next c

    RSHIFT32 = Number

END FUNCTION


'This shifts bits in 32 bit numbers left with no carry ie. they are not folded back and are lost at the upper end.
'This is equivalent to 'ASL' in some assemblers.

FUNCTION LSHIFT32(Number, BitShift)

    For c = 1 To BitShift
        Number = ((Number AND hexdec("&H7FFFFFFF")) * 2)
    Next c

    LSHIFT32 = Number

END FUNCTION

' END FUNCTIONS & SUBROUTINES CODE ---
 

Whoops! I've just updated the in-code documentation due to two small errors in description. Sorry, I was rushing.

Stefan: corrected "isEmpty" error in SeedGenerator sub by adding INT() function
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Jul 30th, 2010, 12:04pm

on Jul 30th, 2010, 04:27am, Stefan Pendl wrote:
@Chris,

Since you mentioned the profiler, you did not hit Alt+O in the test.bas wink


No, I didn't tongue Actually, I don't have the LB Pro 4.04 beta yet, I should e-mail Carl. I ran this in 4.03 to use Assist's profiler, but I normally use regular 4.04. Also, I usually do my own code formatting, I don't agree with some of the ways it formats certain things tongue

EDIT: Updated DLL again, added a getRandomRange() function. You pass in a minimum and a maximum value, and the function will return a random number within that rage, inclusive.

http://www.box.net/shared/oq5m3a0z4d
Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 30th, 2010, 11:14pm

Hey Chris, grin

Thanks so much for this DLL version. Greatly appreciated. grin I've no doubt it will run much faster than my LB version. (Although, my LB version is much faster than I would have thought it would be before I coded it). It's quite usable for many applications... depends on the speed of your machine of course and how many numbers you want how quickly. wink

I've just downloaded your DLL and support files. Tell me: Does your floating point function return values on the interval 0 to 1 or 0 to 0.99999999... same as LB and most languages? smiley
Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 31st, 2010, 01:56am

I've just unpacked and run your test.bas file... and I cant get it to work. huh Am I missing something? I just get an error message when I run that says something about a device that is attached to the system being missing or not working or something... I have the DLL in the same folder as the .bas file huh huh cry
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Jul 31st, 2010, 02:28am

on Jul 30th, 2010, 12:04pm, Chris Iverson wrote:
Also, I usually do my own code formatting, I don't agree with some of the ways it formats certain things tongue


Yes, I don't agree with the way SELECT..CASE and DO..LOOP are formated either.

Have you thought about allowing negative numbers for the range, which would need some decision to be included, since the current way of the range only works for positive numbers.

Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Jul 31st, 2010, 11:04am

on Jul 31st, 2010, 02:28am, Stefan Pendl wrote:
Have you thought about allowing negative numbers for the range, which would need some decision to be included, since the current way of the range only works for positive numbers.



Dunno about an official way, since everything in the DLL is handled unsigned. I'd probably simply have to cast it to a LONG, but if you call the getRandomRange() function and set the parameters and return value as LONG instead of ULONG, you can use negative numbers. It's pretty much the same as casting it from LB.

For example:
Code:
    CallDLL #MT, "getRandomRange",_
    -10 as long,_
    -1 as long,_
    ret as long

    print ret 


Also, it's written like this, because -10 is smaller than -1, so it would have to go first.


@Coda: Can you give the the exact error message? I'm trying to figure it out, but I'm unsure why it wouldn't work. What version of Windows are you using?

Also, it returns values between 0 and 0.9999.
Re: Pseudo Random Number Generation in LB...
Post by Coda on Jul 31st, 2010, 9:51pm

Thanks, Chris. smiley

The window is labelled: Warning

The exact error message is: Runtime Error: A device attached to the system is not functioning. ( OS error 16r1F ) (see error.log for more information)

Ive looked my error log doesnt seem to have logged ANYTHING. undecided

I use Windows 98 SE.
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Aug 1st, 2010, 04:36am

You might need to download and install the latest version of the VC++ runtime redistributable package from Microsoft available for Win98.

Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Aug 1st, 2010, 04:51am

on Jul 31st, 2010, 11:04am, Chris Iverson wrote:
Dunno about an official way, since everything in the DLL is handled unsigned. I'd probably simply have to cast it to a LONG, but if you call the getRandomRange() function and set the parameters and return value as LONG instead of ULONG, you can use negative numbers. It's pretty much the same as casting it from LB.

For example:
Code:
    CallDLL #MT, "getRandomRange",_
    -10 as long,_
    -1 as long,_
    ret as long

    print ret 


Also, it's written like this, because -10 is smaller than -1, so it would have to go first.


Currently, it will fail with ranges like -50 to 50, for instance.

Changing the DLL from uLong to Long, did not help either.

If the minimum is negative and the maximum is positive, the modulus does not work right.

I hope, that I am not nitpicking, but I envision people to try the funniest things with a function providing a range.

Re: Pseudo Random Number Generation in LB...
Post by cundo on Aug 1st, 2010, 4:02pm

Dependency walker tells me that there is a file missing:
MSVCR90.DLL
After downloading the file from the internet, the MersTwistLB.dll works.
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Aug 1st, 2010, 4:40pm

on Aug 1st, 2010, 4:02pm, cundo wrote:
Dependency walker tells me that there is a file missing:
MSVCR90.DLL
After downloading the file from the internet, the MersTwistLB.dll works.


That's the problem with the VS compiled DLLs, you always run into dependencies.

The VC Runtime Distribution I pointed to, will take care of this.

Re: Pseudo Random Number Generation in LB...
Post by Coda on Aug 1st, 2010, 10:07pm

I have just downloaded and installed the VC++ package Stefan recommended and it doesn't help. cry I am still getting the same error. A quick search of my system reveals it did not install the MSVCR90.DLL file, mentioned by cundo. I will find and install that to see if it helps and report back. grin
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Aug 1st, 2010, 10:25pm

on Aug 1st, 2010, 04:51am, Stefan Pendl wrote:
Currently, it will fail with ranges like -50 to 50, for instance.

Changing the DLL from uLong to Long, did not help either.

If the minimum is negative and the maximum is positive, the modulus does not work right.

I hope, that I am not nitpicking, but I envision people to try the funniest things with a function providing a range.


Don't worry about seeing nitpicking, because what you are bringing up is a valid use for the DLL, and it should work for the DLL.

The only odd thing for me is, using the values you've given works just fine for me.

Something like this:

Code:
open "MersTwistLB" for DLL as #MT
CallDLL #MT, "SeedWithTime",_
ret as void

for x = 1 to 100
    CallDLL #MT, "getRandomRange",_
    -50 as long,_
    50 as ulong,_
    ret as long

    print ret
next x

close #MT 


Works perfectly. This is strange =/



As for the dependency thing, I'm not using any of the VS libraries for this, so I should be able to remove the dependency. Let me look at the compile options.

EDIT: Well, unfortunately, I can't remove the dependency, because all of the standard libraries are included through that DLL, and that includes the time library that I use in the DLL. I might be able to compile the code with a different compiler, though, but I can't check into that right now.
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Aug 2nd, 2010, 02:10am

Chris,

you just caught me, I had the values swapped.

I think it would be good to include a check to make sure min is always less then max.

Re: Pseudo Random Number Generation in LB...
Post by Coda on Aug 2nd, 2010, 03:07am

I have tried installing the MSVCR90.DLL and there has been no change. This DLL just doesn't work for me. cry I would try to compile it myself using my Borland C compiler but I have recently discovered an error in certain bitwise mathemetical operations required for the Mersenne Twister in code that is compiled by it and no longer trust it. cry Maybe I'll try to get that GCC one...
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Aug 2nd, 2010, 11:16am

Does Dev-C++ work in Windows 98? It's a great IDE for Windows GCC compiling. The only problem is it hasn't been updated in years. That's part of the reason why I prefer to use Visual Studio.

It includes the compiler, too. Sorry about your troubles, I'll include a GCC version of the DLL in my next update.

UPDATE: Ah, I see, the VS2008 Redistributable package wasn't made for Windows 98. I can statically link the runtime library, which will get around needing MSVCRT90, but because it includes a bunch of extra stuff, it'll balloon my DLL to 55KB. I may just end up doing that anyway, if more people have trouble with this. If I can get internet working in my Windows 98 virtual machine, I'll test it myself at some point.



Stefan: That's not a bad idea, but I'm unsure of what to return in the case that the second number isn't less than the first number. I'd think just to return 0, but someone might make the assumption that it's a valid return value.

Hmm, then again, repeated calls with the same erroneous range will all return 0, so that will probably initiate a bug hunt.

I think I'll try just returning 0 for now.
UPDATE: I'm going to change getRandomRange() to use all LONG values. This will make it easier to check for erroneous conditions, and I doubt people are going to use the function for the upper range of ULONG values anyway.


EDIT: Ok, DLL was updated.

Regular Version:
http://www.box.net/shared/oq5m3a0z4d

GCC Version(Includes Dev-C++ Project):
http://www.box.net/shared/p6c8j5tn6f


It looks as if the VS version is better optimized, though. VS's DLL is 8KB, while GCC's is 15.
Re: Pseudo Random Number Generation in LB...
Post by Coda on Aug 2nd, 2010, 8:49pm

Thanks SOOO much, Chris! I'll download it and give it a try as soon as possible. grin
Re: Pseudo Random Number Generation in LB...
Post by Coda on Aug 2nd, 2010, 10:47pm

Chris, my friend, you are a genius, a true gentleman and just about my favourite person on the planet, at the moment!!! grin Your new dll compile works a charm on my computer!!! grin

Thankyou, thankyou, thankyou... from the bottom of my heart THANKYOU!! grin

I didn't know what I was going to do. I couldn't use RND, my own LB Mersenne Twister code worked but was too slow for the large number of psedo-random numbers I needed for my program. Your solution has saved the day!

Thanks also for the tip about Dev-C++. I will look into it as perhaps a better compiler for my mediocre attempts at C programming. grin
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Aug 2nd, 2010, 11:25pm

No problem, glad it worked ^_^


I started out with Dev-C++ as well, I just moved to Visual Studio(including Visual C++ express edition, which is free), because it is, IMO, a better IDE.

Dev-C++ works perfectly fine, though, and it also supports older versions of windows without needing extra steps.

Update: Well, looks like statically compiling won't help run the DLL on Win98 either, so I have to compile it with GCC for earlier versions of Windows. I'm glad I found my old Win98SE install disc ^_^

It was a hassle trying to get the install to run, though, seeing as I had to boot it off of a floppy disk, and my main computer lacks a floppy drive. Managed to get a boot disk image, though.
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Aug 3rd, 2010, 02:48am

on Aug 2nd, 2010, 11:16am, Chris Iverson wrote:
Stefan: That's not a bad idea, but I'm unsure of what to return in the case that the second number isn't less than the first number. I'd think just to return 0, but someone might make the assumption that it's a valid return value.

Hmm, then again, repeated calls with the same erroneous range will all return 0, so that will probably initiate a bug hunt.

I think I'll try just returning 0 for now.
UPDATE: I'm going to change getRandomRange() to use all LONG values. This will make it easier to check for erroneous conditions, and I doubt people are going to use the function for the upper range of ULONG values anyway.


I would just swap numbers and proceed with calculating the random number.

See it this way, the numbers are only limits, which one is the upper or the lower one is only important to the function, the user should not have to worry about it.

Re: Pseudo Random Number Generation in LB...
Post by glimmung on Aug 3rd, 2010, 08:28am

Chris Iverson wrote:

Quote:
I've created a different DLL, if you wish. It's 7KB compiled, and is based on public-domain code of the Mersenne Twister. Really, I think the only difference from uncleBen's DLL is that this one returns integers, not floats. (If you want floats, I'm sure it can be added pretty easily.) It also does not yet have an option for a user-specified seed, if you want that, I'll add it grin

Here's the DLL and LB code. I included VS2008 source code, as well.

http://www.box.net/shared/oq5m3a0z4d


I downloaded the MersTwistLB.dll, and it works a treat. Is this freely available to use and distribute?

I've been using:

Code:
function randomNumber(low, high)
    'This line is to prevent the addition of low causing the number returned to go above the highest value wanted.
    high = high - (low - 1) 
    randomNumber = int(rnd(1) * high) + low
end function
 


I made a strShuffle$ function, adapted from code on a post again by Chris (he - she? - really is a Guru :D), and uses the randomNumber(low, high) function. (Original post: Re: Random words from data...) I've been using this as padding for passwords and the like prior to encryption, and during testing seemed to work well... and then I hit a problem when I used this in a program I am developing, when I thought I would use a random string of 24 characters to name some temporary files for use during run time and then KILLED at the end of use. I know I could just use a counter and name each file "Temp";str$(cnt);".txt", or whatever, but I got me a nifty new function so I wanted to use it. :)

Anyway... on testing I found that the three files it was creating were always named with the same three "random" names:

Quote:
qljsIlqExDgxqrfpXkjrSgyo.txt
KmazcfqgcYJXlNlAbvutqBxz.txt
tAqchKJrnFgcoeGakctnywar.txt


I use:

Code:
n = randomNumber(1, 24)
tempFile$ = mid$(shuffleStr$(strToShuffle$), n, 24) +".txt"
 


So clearly a problem with the randomNumber(low, high) function, since even if the shuffled string is always shuffled the same way, the variable n should be different every time, and then give a different "random" string. Only it doesn't.

???
Re: Pseudo Random Number Generation in LB...
Post by glimmung on Aug 3rd, 2010, 09:07am

To append to above. Thought I'd do a quick test three times with randomNumber function and MersTwistLB.dll. With randomNumber function, produces values for n:

14, 19, 11
14, 19, 11
14, 19, 11

(there are three temporary files, and I ran it three times consecutive)

With MersTwistLB.dll:

16, 17, 17
10, 11, 12
4, 5, 6

................................................

Just noticed that Coda has posted RND problem on bugs forum

http://libertybasic.conforums.com/index.cgi?board=lb4alphatest&action=display&num=1280735852

Unless there's a workaround using RANDOMIZE or something, am quite happy using MersTwistLB.


Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Aug 3rd, 2010, 10:35am

on Aug 3rd, 2010, 02:48am, Stefan Pendl wrote:
I would just swap numbers and proceed with calculating the random number.

See it this way, the numbers are only limits, which one is the upper or the lower one is only important to the function, the user should not have to worry about it.


Ugh, why didn't I think of that? It's a much simpler solution.



glimmung: Go ahead, use the DLL as you wish. I made it for the LB community to take advantage of ^_^


Regarding your random test results, the runs that gave "14, 19, 11", how did you run those tests? Even if the random number generator in LB is weak, I find it very strange that it would give the same numbers three times in a row. You didn't use RANDOMIZE on these tests?

Also, I'm a male, and I don't think I can take credit for the randomNumber() function. I'm pretty sure I found it somewhere in the LB helpfile. grin


Re: Pseudo Random Number Generation in LB...
Post by Rod on Aug 3rd, 2010, 10:36am

Well actually the death of the native RNG is a bit overplayed. It is perfectly functional and fast. The seeding problem only really manifests itself in the very special circumstance that CODA identifies, running multiple programs back to back. The solution is provided in Psycho's post, #7.

So while you mathematicians can revel in the newness of Merser Twisting we humble coders can make perfectly good use of the native functions.

That does not detract in any way from Chris's achievement in delivering the new RNG in .dll format.
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Aug 3rd, 2010, 10:54am

Updated both versions of the DLL.

VS:
http://www.box.net/shared/oq5m3a0z4d

GCC:
http://www.box.net/shared/p6c8j5tn6f



I mainly made the DLL just to see if I could. And I could ^_^


Also, I have to thank my dad for enabling me to get any version of Windows into a testable mode, so I can see if the things I write work on them grin I can finally test on Windows 98 for legacy support.
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Aug 3rd, 2010, 5:31pm

Your latest VS update archive includes the ZIP archive, so there is a problem when you extract the file.

Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Aug 3rd, 2010, 5:42pm

Sorry about that, reuploaded it.
Re: Pseudo Random Number Generation in LB...
Post by Stefan Pendl on Aug 3rd, 2010, 5:57pm

No problem, I can handle such situations, but others might not.

Thanks for fixing this.

Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Aug 3rd, 2010, 9:14pm

Thanks for telling me, I didn't realize I'd done that.
Re: Pseudo Random Number Generation in LB...
Post by glimmung on Aug 8th, 2010, 7:10pm

apologies for long delay, been busy:

Quote:
glimmung: Go ahead, use the DLL as you wish. I made it for the LB community to take advantage of ^_^


Regarding your random test results, the runs that gave "14, 19, 11", how did you run those tests? Even if the random number generator in LB is weak, I find it very strange that it would give the same numbers three times in a row. You didn't use RANDOMIZE on these tests?

Also, I'm a male, and I don't think I can take credit for the randomNumber() function. I'm pretty sure I found it somewhere in the LB helpfile. grin


"glimmung: Go ahead, use the DLL as you wish. I made it for the LB community to take advantage of ^_^"

Cheers man, greatly appreciated.

"Also, I'm a male" - I guessed as such, but you never know!

"Regarding your random test results, the runs that gave "14, 19, 11", how did you run those tests? Even if the random number generator in LB is weak, I find it very strange that it would give the same numbers three times in a row. You didn't use RANDOMIZE on these tests?"

"You didn't use RANDOMIZE on these tests?" Nope.

"how did you run those tests?" Am working on a project that will require updates... the code I was working on, in simulation mode, downloaded an "update.txt" file which was parsed and cross-referenced on the "local" machine, and any new timestamps indicate a new update... in this instance three files... it was at this point I decided to use random file names... and every time I ran it the names were the same. Every time. So I came here... cheesy

Anyway... the randomNumber function is first used in the shuffleStr$, and then in using the mid$ function.... Initially I used left$(text$, 24), but on getting same results everytime, I thought would use mid$, with a random start point... to no avail... and putting "PRINT n" in my code showed the problem.... not just that the random number was always the same, but the shuffled string was also the same, because it is dependent on the randomNumber function.

"I find it very strange that it would give the same numbers three times in a row" - likewise, and hence my concern. What i wanted from it wasn't that critical at the time, but then... I use random numbers in encryption... which is more important.

Um... I think that's it. cheesy
Re: Pseudo Random Number Generation in LB...
Post by Chris Iverson on Aug 8th, 2010, 10:37pm

Would it be possible for you to post the strShuffle function you're using, or some other code that can duplicate that problem? I've tried multiple times, and I still can't find any repeats within three tries.
Re: Pseudo Random Number Generation in LB...
Post by dEEBLE on Nov 7th, 2016, 11:05am

Thank you all for your your help. Rnd(n) is indeed fast -- Looping 1E6 times takes only 15 seconds.

Long ago (~ 45 years) I devised a graphical means to assess the randomness of a generator:

Define a square of sides equal to the largest random number
Assign pairs of random numbers to points on the Cartesian Plane in the square and plot them.

In the generators I was using at the time I'd see repeating parallel line segments of dots with gaps in between them.

I lack the skill to do this in LibertyBasic but perhaps one of you could code it for me.

Thanks.

Dennis


Re: Pseudo Random Number Generation in LB...
Post by Rod on Nov 7th, 2016, 12:06pm

Code:
    'Test the random number generator to see if it can draw
    'uniformly random dots!
    WindowWidth = 410
    WindowHeight = 440
    open "random generator test" for graphics_nsb as #draw
    print #draw, "trapclose [quit]"
    print #draw, "down ; size 2"
    for x = 1 to 50000
        print #draw, "place "; int(rnd(1)*400); " "; int(rnd(1)*400)
        print #draw, "go 1"
    next x

    wait

[quit]
    close #draw
    end
 

Re: Pseudo Random Number Generation in LB...
Post by tenochtitlanuk on Nov 7th, 2016, 5:17pm

Interesting to see a bump on a six-year-old thread!
Re: Pseudo Random Number Generation in LB...
Post by tsh73 on Nov 8th, 2016, 02:40am

I think I see a pattern...
Code:
'Test the random number generator to see if it can draw
'uniformly random dots!
    nomainwin
    WindowWidth = 410
    WindowHeight = 440
    open "random generator test" for graphics_nsb_nf as #draw
    print #draw, "trapclose [quit]"
    print #draw, "down"
    print #draw, "fill 128 128 128"

    print #draw, "font times_new_roman 200 bold "
    print #draw, "place 30 280"
    print #draw, "backcolor 128 128 128"
    print #draw, "color 126 126 126"
    print #draw, "\";chr$(exp(4.331));chr$(acs(0.933)*180)

    timer 1000, [waitAbit]
    wait
    [waitAbit]
    timer 0

'    print #draw, "rule XOR"
   print #draw, "rule ";_r2_mergepen
    print #draw, "color 126 126 126"
    for x = 1 to 150000
    scan
        print #draw, "set "; int(rnd(1)*400); " "; int(rnd(1)*400)
    next x

    wait

[quit]
    close #draw
    end

 

Re: Pseudo Random Number Generation in LB...
Post by Rod on Nov 8th, 2016, 03:03am

Very nice smiley
Re: Pseudo Random Number Generation in LB...
Post by tenochtitlanuk on Nov 8th, 2016, 06:25am

Nice bit of code obfuscation and graphic revelation, Anatoly!
Re: Pseudo Random Number Generation in LB...
Post by cundo on Nov 16th, 2016, 5:15pm

on Nov 8th, 2016, 02:40am, tsh73 wrote:
I think I see a pattern...
Code:
'Test the random number generator to see if it can draw
'uniformly random dots!
    nomainwin
    WindowWidth = 410
    WindowHeight = 440
    open "random generator test" for graphics_nsb_nf as #draw
    print #draw, "trapclose [quit]"
    print #draw, "down"
    print #draw, "fill 128 128 128"

    print #draw, "font times_new_roman 200 bold "
    print #draw, "place 30 280"
    print #draw, "backcolor 128 128 128"
    print #draw, "color 126 126 126"
    print #draw, "\";chr$(exp(4.331));chr$(acs(0.933)*180)

    timer 1000, [waitAbit]
    wait
    [waitAbit]
    timer 0

'    print #draw, "rule XOR"
   print #draw, "rule ";_r2_mergepen
    print #draw, "color 126 126 126"
    for x = 1 to 150000
    scan
        print #draw, "set "; int(rnd(1)*400); " "; int(rnd(1)*400)
    next x

    wait

[quit]
    close #draw
    end

 


That is magic! Really cool.