211590 - Math.random() uses bad algorithm

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[zack-weg]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.3) Gecko/20030505
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.3) Gecko/20030505

The comments in jsmath.c claim to use the same algorithm to obtain pseudo random
numbers as Java does, but in fact the code does not.
It uses 0x5D0EECE66DL multiplier instead of 0x5DEECE66DL.
            ^

Additionally, the method to construct a random double from random bits in
random_nextDouble() is bad.
See http://java.sun.com/j2se/1.4.1/docs/api/java/util/Random.html#nextDouble() .


Reproducible: Always

Steps to Reproduce:
1. Look at the code: http://lxr.mozilla.org/seamonkey/source/js/src/jsmath.c#293

Comment 1

[zack-weg]

Note: Using 54 bits for constructing a double means that |Math.random() < 1| is
not always true, which violates the ECMAScript spec and may cause problems.

Comment 2

[Phil Schwartau]

cc'ing Brendan, Waldemar -

Comment 3

[zack-weg]

Attachment: proposed patch

Comment 4

[zack-weg]

Attachment: testcase

This HTML testcase tests the 53th bit of numbers returned from Math.random().
There may be (but should not) more bits after the 53th bit if the number is
less than 1/2. The second test tests the 53th bit after forcing the additional
bits to be rounded.

Both results should be around 50%, but are 37.5% resp. 25% in Mozilla. An
existant 54th bit will force the 53th bit to be even when rounded away. If all
54 bits were set, the result is 1, but a minimal loop in the js shell doing
nothing else than testing random numbers will take some 100 years on today's
PCs until you can expect this to happen.

Comment 5

[Phil Schwartau]

FWIW, IE6 seems to give the same results on the testcase as Mozilla.

Comment 6

[zack-weg]

For the record: On Linux, Opera 7.11 gives 0%/0% because it uses only 32 bits.
Konqueror 3.1.2 gives about 50%/42% (if you remove toFixed() from the testcase,
which makes it fail altogether), because it seems to use 64 bits and rounding
errors are distributed among more bits (partly invisible to the user if cut by
rounding to a double).

Comment 7

[zack-weg]

Comment on attachment 127018 [details] [diff] [review]
proposed patch

Seems everyone (including me) has forgotten this bug and its patch. Can this go
in?

Comment 8

[Brendan Eich [:brendan]]

Comment on attachment 127018 [details] [diff] [review]
proposed patch

Zack, thanks for fixing this.  The patched code is ancient, transcribed from
old Java code in mid 1995.  I don't remember how the 0x5DEECE66DL becoming
0x5D0EECE66DL error occurred -- probably just a bleary-eyed blunder made late
at night by yours truly.  The other error was copied directly from early Java
code (see the link you cite:

    [In early versions of Java, the result was incorrectly calculated as:

  return (((long)next(27) << 27) + next(27))
      / (double)(1L << 54);

    This might seem to be equivalent, if not better, but in fact it introduced
a large nonuniformity because of the bias in the rounding of floating-point
numbers: it was three times as likely that the low-order bit of the significand
would be 0 than that it would be 1! This nonuniformity probably doesn't matter
much in practice, but we strive for perfection.]

).

Thanks again.

/be

Comment 9

[Brendan Eich [:brendan]]

Taking for 1.6b checkin.

/be

Comment 10

[Brendan Eich [:brendan]]

Fixed.

/be

Comment 11

[Bob Clary [:bc] (inactive)]

Checking in regress-211590.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-211590.js,v  <--  regress-211590.js
initial revision: 1.1

Comment 12

[Bob Clary [:bc] (inactive)]

FYI: when testing 1.8.0.1, 1.8, 1.9a1 on linux/macosx/win2k3 for opt and debug builds I occasionally get some failures:

js1_5/Regress/regress-211590.js Math.random should be random 
expected: between 49% and 51%:

linux  : 48.950  : 2006-01-21-15-34-02-firefox-1.5-opt-1.8_2006012021
linux  : 51.400  : 2006-01-21-21-44-48-firefox-trunk-dbg-1.9a1_2006012022
macosx : 48.940  : 2006-01-21-15-58-46-firefox-1.5-opt-mac-1.8_2006012022
win2k3 : 48.770  : 2006-01-21-18-32-16-firefox-trunk-opt-1.9a1_2006012023
win2k3 : 51.370  : 2006-01-21-18-31-55-firefox-trunk-opt-1.9a1_2006012023

Not sure if this is meaningful or if we just want to handle everything in bug 322529.

Comment 13

[Bob Clary [:bc] (inactive)]

I'm tired of these random failures, so I've increased the range to 48.5-51.5

/cvsroot/mozilla/js/tests/js1_5/Regress/regress-211590.js,v  <--  regress-211590.js
new revision: 1.3; previous revision: 1.2

Comment 14

[Bob Clary [:bc] (inactive)]

verified fixed 1.9.0 linux/mac*/windows.

Comment 15

[Bob Clary [:bc] (inactive)]

relax range to 48-52% to reduce spurious failures.

Checking in regress-211590.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-211590.js,v  <--  regress-211590.js
new revision: 1.4; previous revision: 1.3

Comment 16

[Boris Zbarsky [:bzbarsky]]

Would it make sense to test the first 52 bits as well, not just the 53rd?  I'd think that all bits should be random here...