Prng

Anyone have a seedable PRNG function written in LSL they would like to share with the community? Or is there one already up somewhere I missed?

I'm sure I could write it without too much trouble, but why reinvent the wheel?

I have one I think...lemme go in world and scrape through my inventory.

Hey Gigs,

Mine was alpha, not numberic, but I found this which might help:

/54/a8/77140/1.html
Is that what you were looking for hun?
Hope that helps!

~Mad

Thanks MadamG, but that's not exactly what I need.

In every other language the PRNG (if they have one) can take a seed. This way you can get the same random sequence over and over if you want, since the sequence will always be the same with the same seed.

I'll write something and put it up here I guess. Might be useful for people that need more than llFrand can offer.

Pseudo-Random Number Generator

EDIT: *smacks head* so thats what PRNG stands for.

btw i wouldn't use the float side of it, it won't give a perfect spread.
The two float versions are interesting, tell me what you think of them. Also if you use more of the digits you increase the granularity of the small floats (but it won't effect their probability).

I looked at that other one, haven't benchmarked it yet, but it would be interesting to see benchmarks on it.

In any case, the one I wrote does an in-game benchmark of 100 random numbers in 1.5 seconds.

Numbers returned are from 0 to 2^31-1

//Linear Congruential Number Generator (LCG), by Gigs Taggart
//Using constants of m=2^31 a=1103515245 c=0;


integer gLastRandVal;



init_random(integer seed)
{
    gLastRandVal=seed;
}


integer random()
{
    gLastRandVal=1103515245*gLastRandVal;
    gLastRandVal=gLastRandVal&0x7FFFFFFF; //make it positive, mod 2^31
    return gLastRandVal;
}

default
{
    state_entry()
    {
        init_random(1);
    }

    touch_start(integer total_number)
    {
        llSay(0, (string)random());
    }
}

EDIT: Removed redundant modulus operation
EDIT2: Fixed flawed constants
EDIT4: Fixed Cycle length

Strife, isn't using an MD5Sum for a random number generator horribly inefficient? If I remember right, MD5 involves like forty multiplies...

Gigs, your algorithm doesn't look right to me. You & with 0x7FFFFFFF, and then modulo by 2^32... I don't think the modulo will do anything in this case. For that matter, & with 0x7FFFFFFF effectively does a modulo by 2^31 - 1.

Looking up the linear congruent random number generator method, it looks like you're supposed to add some constant in, too. If you do that and then remove the modulo line, then it should be good, I think.

Really? i never knew exactly how it worked. I wrote it so it would be overkill. Changing one aspect of the seed would result in very different results.

Lex,

Thanks for the review and feedback on the algorithm. You are correct that LCG allows for a constant added in pre-modulus, but in many cases that constant "c" = 0, such as in the case of the URN12 LCG constants, the ones I chose. Note that the choice of constants strongly affects the period of the LCG PRNG, some constants can lead to very tight loops (short period paths), so I'd rather stick with proven constants.

Ideally we'd work with arbitrarily large numbers, but here we have to work with signed ints and 32 bits.

Here's one page talking about LCG and signed number limitations.

http://csep1.phy.ornl.gov/rn/node15.html#SECTION00046000000000000000

I chose URN12 constants in part because the modulus m is a power of 2, 2^31, so their warning about non-power-of-two modului doesn't apply.

Here are some other common LCG constants:
http://random.mat.sbg.ac.at/~charly/server/node3.html

I'll have to check to see if the actual modulus operation is redundant or not, what you are saying makes sense though, the bitmask is effectively a modulus in itself.

Regarding Strife's algorithm, llMD5String is not too terribly slow, in a relative sense, because LSL is so incredibly slow that the MD5 operation can be carried out without a whole lot of delay over carrying out a few arithmatic operations directly in LSL. For example, I know 100 MD5s takes about 3-4 seconds, as opposed to 100 function calls to the posted LCG which takes about 1.5-2 seconds. This is after testing the "empty loop" speed and subtracting it from the benchmark to get better numbers.

I still haven't benchmarked Strife's algorithm directly, but it is probably not a whole lot slower, it probably is about twice as slow as LCG, not the order of magnitude you'd expect from something that does fundamentally so much more math, such seems to be the nature of LSL.

When and If they upgrade the script core, it's possible that the performance difference will be much more apparent, since script performance will more closely track actual performance and not how slow the LSL interperter is as evaluating lines of code.

Well, MD5 would get the job done, yeah. It's just expensive. Check it out:

http://en.wikipedia.org/wiki/MD5#Pseudocode

Ah, I learn something new every day, thanks



It is, although I misspoke: &ing with 0x7FFFFFFF is like modulus by 2^31. If you & with 2^n - 1, it's exactly equivalent to a modulus by 2^n, but that only works for powers of two. If you want to prove it to yourself, try it with a modulus by 16. 16 = 2^4, which is 10000 in binary. 15 is 1111. If you & with 15, you're basically slicing off all of the bits above and including the 16 bit. Those first four bits just continually count up from 0000 to 1111, so it's essentially a modulus.



True, there is that. Use the tools given.

I've found some very short period sequences in the old constants (when seed=0x4000 0000 and 0x0400 0000 particularly). Here are some new constants that have been tested more fully and should give more random results.

I made a 2GB file of random numbers from this algorithm with these constants, and gzipped it, it came out to be exactly the same randomness as linux /dev/urandom in that test.