Closed Bug 211590 Opened 21 years ago Closed 21 years ago

Math.random() uses bad algorithm

Categories

(Core :: JavaScript Engine, defect, P1)

defect

Tracking

()

VERIFIED FIXED
mozilla1.6beta

People

(Reporter: zack-weg, Assigned: brendan)

Details

(Keywords: js1.5)

Attachments

(2 files)

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
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.
cc'ing Brendan, Waldemar -
Assignee: rogerl → khanson
Status: UNCONFIRMED → NEW
Ever confirmed: true
Attached patch proposed patchSplinter Review
Attached file 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.
FWIW, IE6 seems to give the same results on the testcase as Mozilla.
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 on attachment 127018 [details] [diff] [review]
proposed patch

Seems everyone (including me) has forgotten this bug and its patch. Can this go
in?
Attachment #127018 - Flags: review?(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
Attachment #127018 - Flags: review?(brendan) → review+
Taking for 1.6b checkin.

/be
Assignee: khanson → brendan
Keywords: js1.5
Priority: -- → P1
Target Milestone: --- → mozilla1.6beta
Fixed.

/be
Status: NEW → RESOLVED
Closed: 21 years ago
Resolution: --- → FIXED
Flags: testcase?
Checking in regress-211590.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-211590.js,v  <--  regress-211590.js
initial revision: 1.1
Flags: testcase? → testcase+
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.
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
verified fixed 1.9.0 linux/mac*/windows.
Status: RESOLVED → VERIFIED
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
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...
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: