Fix off-by-one error in PRNG.

Fix off-by-one error in PRNG.

BUG=

Committed: https://crrev.com/0d97d5380854ba571672c2b33bfc6b6c03b69853
Cr-Commit-Position: refs/heads/master@{#10328}

[the sun, 2015-10-19 15:10:52]

solenberg@webrtc.org changed reviewers:
+ pbos@webrtc.org

[pbos-webrtc, 2015-10-19 15:12:03]

lgtm

[pbos-webrtc, 2015-10-19 15:22:22]

pls fix, then lgtm

https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc
File webrtc/test/random.cc (right):

https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc#newcode34
webrtc/test/random.cc:34: float uniform = Rand() * (high - low) + low;
Wait, this actually causes a bad distribution, if we do this (with 1.0
inclusive) then 2, 3 gives that 3 is infinitely (ok, 1 out of 2**32) unlikely.

Revert this line and divide kScale by 2**32 instead so that 1.0 is inclusive,
then the previous line was OK.

https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.h
File webrtc/test/random.h (right):

https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.h#newcode27
webrtc/test/random.h:27: // Return pseudo-random number in the interval [0.0,
1.0].
Let's make this one [0.0, 1.0).

[terelius, 2015-10-19 15:27:23]

terelius@webrtc.org changed reviewers:
+ terelius@webrtc.org

[terelius, 2015-10-19 15:27:24]

https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc
File webrtc/test/random.cc (right):

https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc#newcode34
webrtc/test/random.cc:34: float uniform = Rand() * (high - low) + low;
On 2015/10/19 15:22:21, pbos-webrtc wrote:
> Wait, this actually causes a bad distribution, if we do this (with 1.0
> inclusive) then 2, 3 gives that 3 is infinitely (ok, 1 out of 2**32) unlikely.
> 
> Revert this line and divide kScale by 2**32 instead so that 1.0 is inclusive,
> then the previous line was OK.

I was actually about to file a bug about this independently. As Peter points
out, this gives the wrong distribution, but with the +1, the computation
overflows.

I am quite convinced that the only way to solve this completely is to use
unsigned.

[the sun, 2015-10-19 15:31:55]

On 2015/10/19 15:27:24, terelius wrote:
> https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc
> File webrtc/test/random.cc (right):
> 
>
https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc#newcode34
> webrtc/test/random.cc:34: float uniform = Rand() * (high - low) + low;
> On 2015/10/19 15:22:21, pbos-webrtc wrote:
> > Wait, this actually causes a bad distribution, if we do this (with 1.0
> > inclusive) then 2, 3 gives that 3 is infinitely (ok, 1 out of 2**32)
unlikely.
> > 
> > Revert this line and divide kScale by 2**32 instead so that 1.0 is
inclusive,
> > then the previous line was OK.
> 
> I was actually about to file a bug about this independently. As Peter points
> out, this gives the wrong distribution, but with the +1, the computation
> overflows.
> 
> I am quite convinced that the only way to solve this completely is to use
> unsigned.

Excluding the 1.0 from the distribution should do it as well, right?

[terelius, 2015-10-19 15:40:19]

On 2015/10/19 15:31:55, the sun wrote:
> On 2015/10/19 15:27:24, terelius wrote:
> > https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc
> > File webrtc/test/random.cc (right):
> > 
> >
>
https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc#newcode34
> > webrtc/test/random.cc:34: float uniform = Rand() * (high - low) + low;
> > On 2015/10/19 15:22:21, pbos-webrtc wrote:
> > > Wait, this actually causes a bad distribution, if we do this (with 1.0
> > > inclusive) then 2, 3 gives that 3 is infinitely (ok, 1 out of 2**32)
> unlikely.
> > > 
> > > Revert this line and divide kScale by 2**32 instead so that 1.0 is
> inclusive,
> > > then the previous line was OK.
> > 
> > I was actually about to file a bug about this independently. As Peter points
> > out, this gives the wrong distribution, but with the +1, the computation
> > overflows.
> > 
> > I am quite convinced that the only way to solve this completely is to use
> > unsigned.
> 
> Excluding the 1.0 from the distribution should do it as well, right?

No. If you ask for a uniformly distributed integer in the range [INT_MIN,
INT_MAX], you'll get a difference 0xFFFFFFFF so when you add 1 you end up
multiplying the floating point random number by 0.

In fact there are even more problems which can give you a negative difference.
Multiplying the floating point rand by this negative number and adding the
(negative) low limit gives something that is outside the desired interval and
possibly lower than INT_MIN.

Feel free to reassign this bug to me if you want.

[terelius, 2015-10-19 16:01:45]

On 2015/10/19 15:40:19, terelius wrote:
> On 2015/10/19 15:31:55, the sun wrote:
> > On 2015/10/19 15:27:24, terelius wrote:
> > > https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc
> > > File webrtc/test/random.cc (right):
> > > 
> > >
> >
>
https://codereview.webrtc.org/1412183002/diff/1/webrtc/test/random.cc#newcode34
> > > webrtc/test/random.cc:34: float uniform = Rand() * (high - low) + low;
> > > On 2015/10/19 15:22:21, pbos-webrtc wrote:
> > > > Wait, this actually causes a bad distribution, if we do this (with 1.0
> > > > inclusive) then 2, 3 gives that 3 is infinitely (ok, 1 out of 2**32)
> > unlikely.
> > > > 
> > > > Revert this line and divide kScale by 2**32 instead so that 1.0 is
> > inclusive,
> > > > then the previous line was OK.
> > > 
> > > I was actually about to file a bug about this independently. As Peter
points
> > > out, this gives the wrong distribution, but with the +1, the computation
> > > overflows.
> > > 
> > > I am quite convinced that the only way to solve this completely is to use
> > > unsigned.
> > 
> > Excluding the 1.0 from the distribution should do it as well, right?
> 
> No. If you ask for a uniformly distributed integer in the range [INT_MIN,
> INT_MAX], you'll get a difference 0xFFFFFFFF so when you add 1 you end up
> multiplying the floating point random number by 0.
> 
> In fact there are even more problems which can give you a negative difference.
> Multiplying the floating point rand by this negative number and adding the
> (negative) low limit gives something that is outside the desired interval and
> possibly lower than INT_MIN.
> 
> Feel free to reassign this bug to me if you want.

After discussing with pbos@, it seems we are solving two different overflows.
Changing the interval to [0,1) seems like a good idea and it will solve the
problem pbos had. I am talking about another case where low is negative and high
is large. I can solve that one after this CL lands.

[terelius, 2015-10-19 16:37:08]

The CQ bit was checked by terelius@webrtc.org

[terelius, 2015-10-19 16:37:09]

The patchset sent to the CQ was uploaded after l-g-t-m from pbos@webrtc.org
Link to the patchset: https://codereview.webrtc.org/1412183002/#ps20001 (title:
"made Rand() interval exclusive of 1.0")

[commit-bot: I haz the power, 2015-10-19 16:37:21]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1412183002/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1412183002/20001

[commit-bot: I haz the power, 2015-10-19 17:32:37]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-10-19 17:32:37]

Try jobs failed on following builders:
  android_arm64_rel on tryserver.webrtc (JOB_TIMED_OUT, no build URL)
  android_dbg on tryserver.webrtc (JOB_TIMED_OUT, no build URL)
  android_rel on tryserver.webrtc (JOB_TIMED_OUT, no build URL)

[the sun, 2015-10-19 21:04:18]

The CQ bit was checked by solenberg@webrtc.org

[commit-bot: I haz the power, 2015-10-19 21:04:27]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1412183002/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1412183002/20001

[commit-bot: I haz the power, 2015-10-19 21:07:49]

Committed patchset #2 (id:20001)

[commit-bot: I haz the power, 2015-10-19 21:07:52]

Patchset 2 (id:??) landed as
https://crrev.com/0d97d5380854ba571672c2b33bfc6b6c03b69853
Cr-Commit-Position: refs/heads/master@{#10328}