Ooops
September 28, 2021, 06:04:22

Author Topic: An unholy bias for 0 (zero) in random (RND)  (Read 988 times)

Offline twgonder

  • Jr. Member
  • **
  • Posts: 29
An unholy bias for 0 (zero) in random (RND)
« on: July 09, 2021, 02:20:40 »
The attached is a sample program that tests for bias in random numbers created by the RND command.
(The program was modified from the documentation examples)
As best as I can tell, RND returns up to 14 decimal places.
This is about 100,000,000,000,000 possibilities.
Zero is just one of those. It should have the same probability as 0.1
Running this program shows a heavy bias for 0,
unless I am missing something.

Could a few people confirm that they have the same problem in their computers/versions, please?
« Last Edit: July 09, 2021, 02:45:01 by twgonder »

Offline bplus

  • Full Member
  • ***
  • Posts: 221
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #1 on: July 09, 2021, 02:45:39 »
To see if we are really getting 0 I tried this:
Code: [Select]
Rem SmallBASIC
Rem Created TWG 07/08/2021
Rem Test random number bias for zero and ranges
Rem Rem there seems to be a big bias for 0
Rem
Dim cntr(6)
For lcnt1 = 1 To 20000000
    r = Rnd
  cntr(6) ++
  IF r < .2 THEN
'     ? " was less than .2 (and >= 0)"
     if r * 100000000000000 = 0 then cntr(0) ++   ' <<<<<<<<<<< bplus mod
     if r = .1 then print "found a .1"
    cntr(1) ++
  ELIF r < .4
'    ? " was less than .4 but >= .2"
    cntr(2) ++
  ELIF r < .6
'    ? " was less than .6 but >= .4"
    cntr(3) ++
  ELIF r < .8
'    ? " was less than .8 but >= .6"
    cntr(4) ++
  ELSE
'    ? " was less than 1 but >= .8"
    cntr(5) ++
  END IF
next lcnt1
for lcnt1 = 1 to 5
  print format("##.00   ",(cntr(lcnt1) / cntr(6) *100));
next lcnt1
print
print "Zero showed up " + cntr(0) + " times."
stop
end
589 times on one run.
And I guess we are getting quite a few. (sb v12.13 on Windows 10 laptop)


Equivalence to 0 cut off:
Code: [Select]
if .00000000000001 = 0 then print "yes" else ? "no"   ' no
if .000000000000009 = 0 then print "yes" else ? "no"   ' yes
« Last Edit: July 09, 2021, 12:52:47 by bplus »

Offline Aurel

  • Sr. Member
  • ****
  • Posts: 351
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #2 on: July 09, 2021, 07:30:51 »
It is normal that is biased to zero because random generator starting from zero
in compiler i am using this function generate RND()

SYS fseed = 0x12345678 ' seed number
'Rnd Function(0->1).......................
SUB RndFn(float d) as float
d=1/0x7fffffff
fseed=(fseed <<< 7)*13
Return abs(d*fseed)
END SUB
(Y)

Offline twgonder

  • Jr. Member
  • **
  • Posts: 29
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #3 on: July 09, 2021, 14:07:01 »
It is normal that is biased to zero because random generator starting from zero
in compiler i am using this function generate RND()

SYS fseed = 0x12345678 ' seed number
'Rnd Function(0->1).......................
SUB RndFn(float d) as float
d=1/0x7fffffff
fseed=(fseed <<< 7)*13
Return abs(d*fseed)
END SUB

Okay, I'm not familiar with that syntax.
Is that the code behind the running of smallBASIC?

Offline Aurel

  • Sr. Member
  • ****
  • Posts: 351
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #4 on: July 09, 2021, 16:58:53 »
I don't know what running behind, i never look into
SB source code 
(Y)

Offline chrisws

  • Full Member
  • ***
  • Posts: 117
    • SmallBASIC
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #5 on: July 13, 2021, 09:27:46 »
RND uses the standard posix C rand() function.

This function isn't cryptographically secure.

According to this, there are some better choices:

https://wiki.sei.cmu.edu/confluence/display/c/MSC30-C.+Do+not+use+the+rand%28%29+function+for+generating+pseudorandom+numbers


Offline Aurel

  • Sr. Member
  • ****
  • Posts: 351
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #6 on: July 13, 2021, 14:41:38 »
chris
you post about rand(x) not rnd

r = rand();  /* Generate a random integer */

rnd() should return decimal number from 0 to 1
(Y)

Offline Ed Davis

  • Jr. Member
  • **
  • Posts: 1
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #7 on: July 14, 2021, 22:14:29 »
RND uses the standard posix C rand() function.

This function isn't cryptographically secure.

According to this, there are some better choices:

https://wiki.sei.cmu.edu/confluence/display/c/MSC30-C.+Do+not+use+the+rand%28%29+function+for+generating+pseudorandom+numbers

Yeah, the C RTL rand() isn't great.  One I've found to work well is by George Marsaglia.  He has actually created a few, but this one works well in my simple macro language:

Code: [Select]
#define SHR3 (jsr^=(jsr<<17), jsr^=(jsr>>13), jsr^=(jsr<<5))
static unsigned long jsr=123456789;

// Return a pseudo random number as an integer in the specified range.
// lo > 0, hi < lo: 0 .. lo - 1
// lo >= 0, hi > lo: lo .. hi inclusive
// otherwise, r
long Random(int lo, int hi) {
    long r = SHR3 & LONG_MAX;   /* force value to be positive */

    if (lo > 0 && hi < lo)
        return r % lo;

    if (lo >= 0 && hi > lo) {
        long range = hi - lo + 1;
        return lo + r % range;
    }

    return r;
}

/* to get a value in range 0..1, use this */
double rnd(void) {
    double r;

    // slight chance we'll get 1.0 - check for, and repeat if so
    while ((r = (double)Random(0, 0) / (double)LONG_MAX) >= 1)
        ;

    return r;
}
« Last Edit: July 14, 2021, 22:41:10 by Ed Davis »

Offline johnno56

  • Jr. Member
  • **
  • Posts: 49
  • Logic is the beginning of Wisdom.
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #8 on: July 14, 2021, 22:26:10 »
Curious. Here is 'my' theory. Let's assume that RND produces, let say, 6 decimal places. Let's also go back to 1977 and use a processor that can perform roughly one million instructions per second (mips). What are the odds of a program recording 'exactly' zero? One in a million. Now let's move forward to 2021. Processors are now measured in gigabits per second. Therefore, the odds of extracting 'exactly' zero are much, much higher. Not even going to go down the road of seeding or randomizing. My point is, that it is highly unlikely that this program, will detect zero or even point one.  But the one thing that impressed me was, how evenly the RND command, generated numbers....

That's my theory. You may fire when ready... I'm not afraid... Well maybe a little... lol
« Last Edit: July 14, 2021, 22:28:14 by johnno56 »
May your journey be free of incident.

Live long and prosper.

Offline bplus

  • Full Member
  • ***
  • Posts: 221
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #9 on: July 15, 2021, 01:39:28 »
I was curious how QB64 holds up under same code, had to adjust to 10000000 limit

Offline chrisws

  • Full Member
  • ***
  • Posts: 117
    • SmallBASIC
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #10 on: July 15, 2021, 23:39:54 »
I was curious how QB64 holds up under same code, had to adjust to 10000000 limit

I tested this in linux and android and these gave zero zero's.


Offline chrisws

  • Full Member
  • ***
  • Posts: 117
    • SmallBASIC
Re: An unholy bias for 0 (zero) in random (RND)
« Reply #11 on: August 04, 2021, 03:19:51 »
I've been experimenting with replacing the standard library rand() with this: https://www.pcg-random.org/

It seems to work well with the test program and also with a rnd%2 test (doesn't alternate 1,0)

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal