RandomLua Library

[linux-man]

After some experiments and talk at the Eternity topic, I became aware of the problems with random generators. Since I don't intend to compile C code for every platform, I decide to create a Pure Lua Random Generator (probably another one...).
So after 6 long hours, a new library is born. It's too late to continue, but I'm thinking about adding Multiply-with-carry tomorrow.

2 algorithms:
Mersenne twister http://en.wikipedia.org/wiki/Mersenne_twister, very good and slow
Linear congruential generator http://en.wikipedia.org/wiki/Linear_con ... _generator, fast and, well, it works... kind of.
The LGC comes with 3 different pre-defined parameters.

Lua Code Sample:

Code: Select all

require('randomlua')

l1 = lcg(0) -- Linear congruential generator (Ansi C params)
l2 = lcg(0, 'nr') --Linear congruential generator (Numerical recipes params)
l3 = lcg(0, 'mvc') -- Linear congruential generator (Microsoft Visual C params)
c1 = mwc(0) -- Multiply-with-carry (Ansi C params)
c2 = mwc(0, 'nr') -- Multiply-with-carry (Numerical recipes params)
c3 = mwc(0, 'mvc') -- Multiply-with-carry (Microsoft Visual C params)
m = twister(0) -- Mersenne twister

for n = 1, 10 do
   io.write(string.format("%8d%8d%8d%8d%8d%8d%16d\n", l1:random(0), l2:random(0), l3:random(0), c1:random(0), c2:random(0), c3:random(0), m:random(0)))
end

and the result is (on Ubuntu Natty 32 and 64 bits and Windows XP):

Code: Select all

   12345   62303   40643   12345   62303   40643      1737743152
    5758   10546   36474   58949   29249   61405        88390169
   10207   63209   23381   58684   55448   60123      1910268388
    7212   21300    8388   54232   58804   31419      2110758764
   38645   58627   19575    3267   57182   15042      1066366237
    7306   50822   21854    1507   38400   26758      2100784455
   25339   27693   38569   18384   51023    7760      1180052548
   53016   24488   48840   10551   31460   14949      2007277539
   44401   48871   33387   49358   56269   34767       548338701
   30550   44826   33666   53843    2237    9028      2124904168

Please just try it everywhere to compare results.
m = twister(0) define a seed = 0. That's just for comparison. Usually it's better to initialize the generators without params. m = twister() call a seed tonumber(tostring(os.time()):reverse():sub(1,10)) (thanks, slime)
There is only needed to define a seed when choosing the LCG params, as in l3 = lcg(0, 'mvc'). After that call l3:randomseed()

:random() works the same way you're used to, except that twister:random(0) return the original 32 bits integer.

:randomseed(s) to change seed. Again, randomseed() call a nice os.time seed

Many thanks to the LuaBit Author

Edit: After some tests I found that the lcg was giving incredible bad values, because I was using all 32 bits. That won't work. Now lgc return a much better 16 bits value. random(0) to get that value, as with Twister.

Edit: v0.2 with Multiply-with-carry http://en.wikipedia.org/wiki/Multiply-with-carry
n = mwc(seed)
The rest is the same. mwc:random(0) return a 16 bit random.
Edit: v0.3 - Code optimizations. Faster.
Edit:v0.3.1 - some time for testing. Fixed Twister. Love file for testers.

[Lap]

I've ported twister and MWC to lua and tested them quite extensively. I can't justify using twister for most of the randoms since it is just too slow. I don't have much experience with the LGC, but I think that overall MWC has the best combination of speed and "randomness".

[kikito]

Forgive my pedancy, but shouldn't this be called "PseudoRandomLua"?

[Taehl]

Mmm, randomness. I approve. But why is the Mersenne Twister algorithm slow? I've read that it's rather fast, all considered.

Also, do you think you can make it (at least an option to) return normalized numbers (decimals between 0 and 1)? I, personally, would find it much more useful that way.

[linux-man]

Forgive my pedancy, but shouldn't this be called "PseudoRandomLua"?

For the same reason we call math.random when we should call math.pseudorandom?

Mmm, randomness. I approve. But why is the Mersenne Twister algorithm slow? I've read that it's rather fast, all considered.

Also, do you think you can make it (at least an option to) return normalized numbers (decimals between 0 and 1)? I, personally, would find it much more useful that way.

All considered. Compared to LCG is extremely slow - lots of calculations. To get 100000 pseudo-randoms it takes 0,4 s with LCG and 22 s with Twister.

As I said I'll add MWC. It's fast and better than LCG, but Twister is the best.

random() will return numbers between 0 and 1

Library updated!

[linux-man]

v 0.2 with Multiply with carry

[Boolsheet]

To get 100000 pseudo-randoms it takes 0,4 s with LCG and 22 s with Twister.

You should be able to make the mersenne twister at least 6 times faster by only using arithmetic and logic operations for the bitwise operations (Has its few restrictions, but works for unsigned 32-bit values). The modulo operator '%' is usually faster than the math.mod function.
It's still much slower compared to the other generators in Lua 5.14, but the native bitwise functions in 5.2 could bring it very close.

[Lap]

Mmm, randomness. I approve. But why is the Mersenne Twister algorithm slow? I've read that it's rather fast, all considered.

I haven't touched the stuff in a few months, but if I remember right, it is almost entirely due to having to use ghetto bit operations since our version of Lua doesn't natively support them.

[linux-man]

To get 100000 pseudo-randoms it takes 0,4 s with LCG and 22 s with Twister.

You should be able to make the mersenne twister at least 6 times faster by only using arithmetic and logic operations for the bitwise operations (Has its few restrictions, but works for unsigned 32-bit values). The modulo operator '%' is usually faster than the math.mod function.
It's still much slower compared to the other generators in Lua 5.14, but the native bitwise functions in 5.2 could bring it very close.

Thanks a lot for the % tip: less 5 seconds! Then I dropped bit.lua code, defined local functions and did my own bitwise operators.
Right now I have the following times for getting 100000 random numbers:
math.random() 0.02 s
lcg:random() 0.04 s
mwc:random() 0.05 s
twister:random() 7.50 s
It's closer to 3 times faster than the 6 times you propose, but I'm running out of ideas.
Uploaded v 0.3
Edit: Thanks again. Twister time dropped 2 s.

[Boolsheet]

It's closer to 2.5 times faster than the 6 times you propose, but I'm running out of ideas.

To be honest, I didn't try to optimize your code. I timed another implementation and compared.
If you're going for speed, then try to avoid calls to c functions like math.floor whenever possible. By computing 'a % 2' you already know if you have to floor or not. Just subtract 1 before you divide by 2 in that case.
Stuff like that. If it's really worth the effort is another question.