quick opinion on math.random

classic Classic list List threaded Threaded
34 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

Martijn Loots
On Thu, 25 Jun 2009, edA-qa mort-ora-y wrote:

> Nathan Rixham wrote:
>> I just ran in to this line of code
>> x = Math.random() + Math.random() + Math.random() + Math.random();
>> and my immediate thought was why not just:
>> x = Math.random()*4;
>
> Well, * 4 limits the numbers which can be created.  Consider that if
> random produced only integers * 4 would result in only multiples of
> four.  So * 4 limits the resulting space.
>
> Look at it another way.  Let's assume random is generated 31 bits of
> random.  If you multiply by 4 your maximum value can not be made up of
> 33 bits.  But of those 33 bits only 31 are random, whereas if you add
> four random numbers together you'll get all 33 bits of random.
>
That's true, but not the issue here. It's all about the distribution
of the random numbers: it changes as soon as you add independant
random numbers together. Using this tiny program demonstrates the
distribution of numbers 0 to 9, taking just 1 random random or
summing a number:

class RandTest {
   static var base = 10;
   static var draw = 100000;

   static function rander(rpt: Int) : Int {
     var t = 0.0; for (i in 0...rpt) t += Math.random() * base;
     return Math.floor(t / rpt);
   }

   static function main () {
     var tests: Array<Int> = new Array();
     for (t in 0...4) {
       for (v in 0...base) tests[v] = 0;
       for (r in 0...draw) tests[rander(t + 1)] ++;
       trace("Test " + (t + 1) + " = "+tests);
     }
   }
}

And a result of that:

RandTest.hx:15: Test 1 = [10089, 9984,  9949, 10043,  9960,  9980,  9854, 10075, 10146, 9920]
RandTest.hx:15: Test 2 = [ 2003, 5988, 10085, 14211, 18059, 17830, 13887,  9999,  5875, 2063]
RandTest.hx:15: Test 3 = [  444, 3193,  8525, 16213, 21585, 21743, 16111,  8513,  3212,  461]
RandTest.hx:15: Test 4 = [   94, 1523,  7049, 16681, 24748, 24850, 16404,  7016,  1544,   91]

One can see that the peak of the distribution becomes more and
more pronounced as more individual random values are added.

There's a lot of math to find out about this; most of which I forgot
long ago.. :)

Grtz,
--
-Martijn    @..@    ( Martijn Loots       -  Hengelo  [NL] )
-          (`--')   ( martijn<@>cosix.com -  www.cosix.com )
-         ( >__< )  ----------------------------------------
-         ^^^  ^^^  (   Netwerken, Security, Open Source   )

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

Lars Nilsson
In reply to this post by Mark de Bruijn | Dykam
On Thu, Jun 25, 2009 at 9:16 AM, Mark de Bruijn<[hidden email]> wrote:
> But, as it returns an floating point value, is Math.Random 4 times more
> random? Doesn't it use the whole precision range already, where the *4 just
> increases the factor.

By changing the factor though, you are also multiplying the inherent
value of the least significant bit by 4. Instead of it representing
1/2^n it will now represent 1/2^(n-2). I'm guessing this difference is
mostly irrelevant if the purpose of the random number is to scale it
by some other number and truncate/round to an integer, which is mostly
influenced by the most significant digits in the mantissa. Integer
random numbers are usually cut into a range by using modulo (at least
I do so), which means you're using the least significant digits to
extract your data.

Lars Nilsson

>
> On Thu, Jun 25, 2009 at 1:34 PM, edA-qa mort-ora-y <[hidden email]>
> wrote:
>>
>> Nathan Rixham wrote:
>> > I just ran in to this line of code
>> > x = Math.random() + Math.random() + Math.random() + Math.random();
>> > and my immediate thought was why not just:
>> > x = Math.random()*4;
>>
>> Well, * 4 limits the numbers which can be created.  Consider that if
>> random produced only integers * 4 would result in only multiples of
>> four.  So * 4 limits the resulting space.
>>
>> Look at it another way.  Let's assume random is generated 31 bits of
>> random.  If you multiply by 4 your maximum value can not be made up of
>> 33 bits.  But of those 33 bits only 31 are random, whereas if you add
>> four random numbers together you'll get all 33 bits of random.
>>
>> Having said that, I can't think of many situations that would warrant
>> it.  Plus, if your bit spaces in total is only 31 bits it won't make any
>> difference how many you add together (The top bits are just stripped --
>> this applies even for float).
>>
>>
>> --
>> edA-qa mort-ora-y
>> -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
>>
>> BigTPoker uses haXe and DHLIB
>>        http://BigTPoker.com/?source=haxe-list
>>
>> The dis-Emi-A haXe Library
>>        http://wiki.disemia.com/HaXe
>>
>> A full set of tools, classes, and support facilities aimed at
>> simplifying and expediting game creation in Flash 9.
>>
>> -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
>> Sign: Please digitally sign your emails.
>> Encrypt: I'm also happy to receive encrypted mail.
>>
>>
>> --
>> haXe - an open source web programming language
>> http://haxe.org
>
>
>
> --
> Mark
>
> --
> haXe - an open source web programming language
> http://haxe.org
>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

edA-qa mort-ora-y
In reply to this post by Mark de Bruijn | Dykam
Mark de Bruijn wrote:
> But, as it returns an floating point value, is Math.Random 4 times more
> random? Doesn't it use the whole precision range already, where the *4
> just increases the factor.
>

Okay, yes, it is float.  I'm not sure on the precision in Flash, I think
float is 64-bit. Which gives it a 53bit significand -- this is the part
which is random.

If you multiply by 4 you don't get anymore random bits, though the range
is now 0 thru 4.  If you add four together your range is also 0 thru 4
but you gain a few random bits (2 bits to be precise).

It is rather inefficient to add four random() together just to get ~2
extra bits of randomness.

--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
        http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
        http://wiki.disemia.com/HaXe
       
A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


--
haXe - an open source web programming language
http://haxe.org

signature.asc (260 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

Ian Liu Rodrigues
In reply to this post by Mark de Bruijn | Dykam

But, as it returns an floating point value, is Math.Random 4 times more random? Doesn't it use the whole precision range already, where the *4 just increases the factor.

It is not a matter of "randomness" (or whatever this means), it is a matter of probability distribution. Multiplying a random number by 4 will make a uniform distribution. Adding 4 random numbers will approximate a Gaussian distribution, which was already said on the thread.

Take a look at this page http://mathworld.wolfram.com/UniformSumDistribution.html

Regards,
Ian L.

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

Nathan Rixham
In reply to this post by edA-qa mort-ora-y
edA-qa mort-ora-y wrote:
> Mark de Bruijn wrote:
>> But, as it returns an floating point value, is Math.Random 4 times more
>> random? Doesn't it use the whole precision range already, where the *4
>> just increases the factor.
>>
>
> Okay, yes, it is float.  I'm not sure on the precision in Flash, I think
> float is 64-bit. Which gives it a 53bit significand -- this is the part
> which is random.

floats are 32 bit, decimals are 64 bit

> If you multiply by 4 you don't get anymore random bits, though the range
> is now 0 thru 4.  If you add four together your range is also 0 thru 4
> but you gain a few random bits (2 bits to be precise).
>
> It is rather inefficient to add four random() together just to get ~2
> extra bits of randomness.

exactly what I thought :)

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

edA-qa mort-ora-y
In reply to this post by Martijn Loots
Martijn Loots wrote:
> That's true, but not the issue here. It's all about the distribution
> of the random numbers: it changes as soon as you add independant

Indeed. The change in distribution dwarfs any significant of those extra
bits of randomness.

Being curious I ran your program as-is, and using a Mersenne twister.
They both do exhibit the same pattern.

It kind of makes intuitive sense as well.  I'd better track through my
code looking for such hidden patterns -- perhaps my attempts at extra
randomness elsewhere are actually less random.

--
edA-qa mort-ora-y
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

BigTPoker uses haXe and DHLIB
        http://BigTPoker.com/?source=haxe-list

The dis-Emi-A haXe Library
        http://wiki.disemia.com/HaXe
       
A full set of tools, classes, and support facilities aimed at
simplifying and expediting game creation in Flash 9.

-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
Sign: Please digitally sign your emails.
Encrypt: I'm also happy to receive encrypted mail.


--
haXe - an open source web programming language
http://haxe.org

signature.asc (260 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

Hudson Ansley
An intuitive way to think about adding random numbers is if you throw
1 die, the numbers 1 to 6 are equally likely, but if you throw 2 dice,
7 is the most likely outcome, and 2 and 12 the least.  So, if you
don't understand random numbers, don't play craps ;-)

Regards,
Hudson

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

Mark de Bruijn | Dykam
Thanks, that clarified the schemes at the page Ian Liu linked for me. I'm probably doing wrong math, but should multiplying  by X give a more equally spread the outcome then doing a random generation X times?

On Thu, Jun 25, 2009 at 7:41 PM, Hudson Ansley <[hidden email]> wrote:
An intuitive way to think about adding random numbers is if you throw
1 die, the numbers 1 to 6 are equally likely, but if you throw 2 dice,
7 is the most likely outcome, and 2 and 12 the least.  So, if you
don't understand random numbers, don't play craps ;-)

Regards,
Hudson

--
haXe - an open source web programming language
http://haxe.org



--
Mark

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

Hudson Ansley
yes, multiplying gives an even distribution, adding separate randoms
gives a Gaussian or "normal" distribution.

On Thu, Jun 25, 2009 at 1:48 PM, Mark de Bruijn<[hidden email]> wrote:

> Thanks, that clarified the schemes at the page Ian Liu linked for me. I'm
> probably doing wrong math, but should multiplying  by X give a more equally
> spread the outcome then doing a random generation X times?
>
> On Thu, Jun 25, 2009 at 7:41 PM, Hudson Ansley <[hidden email]>
> wrote:
>>
>> An intuitive way to think about adding random numbers is if you throw
>> 1 die, the numbers 1 to 6 are equally likely, but if you throw 2 dice,
>> 7 is the most likely outcome, and 2 and 12 the least.  So, if you
>> don't understand random numbers, don't play craps ;-)
>>
>> Regards,
>> Hudson
>>
>> --
>> haXe - an open source web programming language
>> http://haxe.org
>
>
>
> --
> Mark
>
> --
> haXe - an open source web programming language
> http://haxe.org
>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

Martijn Loots
In reply to this post by edA-qa mort-ora-y
On Thu, 25 Jun 2009, edA-qa mort-ora-y wrote:

> Martijn Loots wrote:
>> That's true, but not the issue here. It's all about the distribution
>> of the random numbers: it changes as soon as you add independant
>
> Indeed. The change in distribution dwarfs any significant of those extra
> bits of randomness.
>
> Being curious I ran your program as-is, and using a Mersenne twister.
> They both do exhibit the same pattern.
>
> It kind of makes intuitive sense as well.  I'd better track through my
> code looking for such hidden patterns -- perhaps my attempts at extra
> randomness elsewhere are actually less random.

If you used these kind of methods to achieve card shuffling.. you'd
better check yes... :)

--
-Martijn    @..@    ( Martijn Loots       -  Hengelo  [NL] )
-          (`--')   ( martijn<@>cosix.com -  www.cosix.com )
-         ( >__< )  ----------------------------------------
-         ^^^  ^^^  (   Netwerken, Security, Open Source   )

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

James W. Hofmann
In reply to this post by edA-qa mort-ora-y
Quoting "edA-qa mort-ora-y" <[hidden email]>:

>
> It kind of makes intuitive sense as well.  I'd better track through my
> code looking for such hidden patterns -- perhaps my attempts at extra
> randomness elsewhere are actually less random.
>

Randomness is hard to get right. For a brief period in CS history many  
simulation results were tainted because of reliance on the poorly  
distributed RANDU generator:

http://en.wikipedia.org/wiki/RANDU

If you want to maximize randomness, you are optimizing on two  
different fronts: Statistical distribution and low repeatability.  
Non-secure generators like Mersenne Twister focus solely on giving an  
even distribution, while cryptographically secure generators like Blum  
Blum Shub also aim for very large cycle length.

In most cases you can just assume that numbers will tend to become  
more biased the more you manipulate them, and that any PRNG will  
become more repeatable as you grab more numbers, so best practice is  
to take only as much randomness as you need, and then immediately use  
it with the minimum amount of modification.

If you want some very high-grade randomness you could use an external  
source with known entropy(for example, the Quantum Random Bit  
Generator website at http://random.irb.hr/ ), grab a cache of random  
values, and then serve them out to the app one by one. As they're  
used, they'll become tainted and you'll have to get more, but for  
certain kinds of apps this is an acceptable solution, and can even be  
relatively convenient if you have access to a hardware number  
generator on the local system.


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

makc
In reply to this post by edA-qa mort-ora-y
On Thu, Jun 25, 2009 at 5:34 PM, edA-qa mort-ora-y<[hidden email]> wrote:
> It is rather inefficient to add four random() together just to get ~2
> extra bits of randomness.
>

It has been pointed out several times in prior emails that this
operation changes value distribution.
http://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: quick opinion on math.random

makc
some visual aid for non-believers
http://wonderfl.net/code/abff1d905aeac92cd34b9a5220cdbb00311f4716

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

RE: Re: quick opinion on math.random

Kastellanos Nikos
In reply to this post by Hugh Sanderson-2
This reflects what you already knew (or should have) since you were a kid
about monopoly.
There are more probabilities to end up 7 squares ahead than any other
combinations of dice!
As you move away from that square the probability fall.
Ex.: 6&8,5&9, 4&10  etc...


I'm I bore you?   8-)








-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Hugh Sanderson
Sent: Wednesday, June 24, 2009 4:16 AM
To: [hidden email]
Subject: [haXe] Re: quick opinion on math.random

Summing 4 uniform random numbers will produce something that is more  
gaussian distributed.

Consider 2 dice: random(6) + random(6) != random(12)

Or, to get something close to 0 with 4 numbers requires
EACH number must be close to 0.

Hugh

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
12