RandomLua Library

linux-man
Citizen
Posts: 67
Joined: Thu Apr 28, 2011 4:51 pm

RandomLua Library

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.
Attachments
randomlua.lua
v.0.3.1 Normalization at 31 bits. Tested on linux and windows
randomlua.love
Last edited by linux-man on Tue Aug 16, 2011 12:17 am, edited 12 times in total.

Lap
Party member
Posts: 256
Joined: Fri Apr 30, 2010 3:46 pm

Re: RandomLua Library

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
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Contact:

Re: RandomLua Library

Forgive my pedancy, but shouldn't this be called "PseudoRandomLua"?
When I write def I mean function.

Taehl
Dreaming in associative arrays
Posts: 1024
Joined: Mon Jan 11, 2010 5:07 am
Location: CA, USA
Contact:

Re: RandomLua Library

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.
Earliest Love2D supporter who can't Love anymore. Let me disable pixel shaders if I don't use them, dammit!
Lenovo Thinkpad X60 Tablet, built like a tank. But not fancy enough for Love2D 0.10.0+.

linux-man
Citizen
Posts: 67
Joined: Thu Apr 28, 2011 4:51 pm

Re: RandomLua Library

kikito wrote:Forgive my pedancy, but shouldn't this be called "PseudoRandomLua"?
For the same reason we call math.random when we should call math.pseudorandom?
Taehl wrote: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
Citizen
Posts: 67
Joined: Thu Apr 28, 2011 4:51 pm

Re: RandomLua Library

v 0.2 with Multiply with carry

Boolsheet
Inner party member
Posts: 780
Joined: Wed Dec 29, 2010 4:57 am
Location: Switzerland

Re: RandomLua Library

linux-man wrote: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.
Shallow indentations.

Lap
Party member
Posts: 256
Joined: Fri Apr 30, 2010 3:46 pm

Re: RandomLua Library

Taehl wrote: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
Citizen
Posts: 67
Joined: Thu Apr 28, 2011 4:51 pm

Re: RandomLua Library

Boolsheet wrote:
linux-man wrote: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.
Edit: Thanks again. Twister time dropped 2 s.
Last edited by linux-man on Thu Jul 28, 2011 10:24 am, edited 1 time in total.

Boolsheet
Inner party member
Posts: 780
Joined: Wed Dec 29, 2010 4:57 am
Location: Switzerland

Re: RandomLua Library

linux-man wrote: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.
Shallow indentations.

Who is online

Users browsing this forum: Bing [Bot] and 9 guests