Closed
Bug 211590
Opened 21 years ago
Closed 21 years ago
Math.random() uses bad algorithm
Categories
(Core :: JavaScript Engine, defect, P1)
Core
JavaScript Engine
Tracking
()
VERIFIED
FIXED
mozilla1.6beta
People
(Reporter: zack-weg, Assigned: brendan)
Details
(Keywords: js1.5)
Attachments
(2 files)
1.36 KB,
patch
|
brendan
:
review+
|
Details | Diff | Splinter Review |
727 bytes,
text/html
|
Details |
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.
Comment 2•21 years ago
|
||
cc'ing Brendan, Waldemar -
Assignee: rogerl → khanson
Status: UNCONFIRMED → NEW
Ever confirmed: true
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•21 years ago
|
||
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)
Assignee | ||
Comment 8•21 years ago
|
||
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+
Assignee | ||
Comment 9•21 years ago
|
||
Taking for 1.6b checkin. /be
Assignee | ||
Comment 10•21 years ago
|
||
Fixed. /be
Status: NEW → RESOLVED
Closed: 21 years ago
Resolution: --- → FIXED
Updated•19 years ago
|
Flags: testcase?
Comment 11•19 years ago
|
||
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+
Comment 12•18 years ago
|
||
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•17 years ago
|
||
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 15•17 years ago
|
||
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•16 years ago
|
||
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.
Description
•