From 2c7ebfa7f0fc5034de0255a2a83a39722187f973 Mon Sep 17 00:00:00 2001 From: "yangguo@chromium.org" Date: Wed, 20 Nov 2013 15:04:37 +0000 Subject: [PATCH] Increase precision when finding the remainder after division by pi/2. R=jkummerow@chromium.org Review URL: https://codereview.chromium.org/66703005 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@17933 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/math.js | 74 ++++++++++++++++++++++++------------- test/mjsunit/mjsunit.js | 10 +++++ test/mjsunit/sin-cos.js | 47 +++++++++++++++++++++-- test/mozilla/mozilla.status | 4 -- 4 files changed, 101 insertions(+), 34 deletions(-) diff --git a/src/math.js b/src/math.js index e1798fa59..2df0ec2a5 100644 --- a/src/math.js +++ b/src/math.js @@ -217,16 +217,19 @@ var InitTrigonometricFunctions; // Also define the initialization function that populates the lookup table // and then wires up the function definitions. function SetupTrigonometricFunctions() { - // TODO(yangguo): The following table size has been chosen to satisfy - // Sunspider's brittle result verification. Reconsider relevance. - var samples = 4489; - var pi = 3.1415926535897932; - var pi_half = pi / 2; - var inverse_pi_half = 2 / pi; - var two_pi = 2 * pi; - var four_pi = 4 * pi; - var interval = pi_half / samples; - var inverse_interval = samples / pi_half; + var samples = 1800; // Table size. Do not change arbitrarily. + var inverse_pi_half = 0.636619772367581343; // 2 / pi + var inverse_pi_half_s_26 = 9.48637384723993156e-9; // 2 / pi / (2^26) + var s_26 = 1 << 26; + var two_step_threshold = 1 << 27; + var index_convert = 1145.915590261646418; // samples / (pi / 2) + // pi / 2 rounded up + var pi_half = 1.570796326794896780; // 0x192d4454fb21f93f + // We use two parts for pi/2 to emulate a higher precision. + // pi_half_1 only has 26 significant bits for mantissa. + // Note that pi_half > pi_half_1 + pi_half_2 + var pi_half_1 = 1.570796325802803040; // 0x00000054fb21f93f + var pi_half_2 = 9.920935796805404252e-10; // 0x3326a611460b113e var table_sin; var table_cos_interval; @@ -234,6 +237,9 @@ function SetupTrigonometricFunctions() { // 1) Multiplication takes care of to-number conversion. // 2) Reduce x to the first quadrant [0, pi/2]. // Conveniently enough, in case of +/-Infinity, we get NaN. + // Note that we try to use only 26 instead of 52 significant bits for + // mantissa to avoid rounding errors when multiplying. For very large + // input we therefore have additional steps. // 3) Replace x by (pi/2-x) if x was in the 2nd or 4th quadrant. // 4) Do a table lookup for the closest samples to the left and right of x. // 5) Find the derivatives at those sampling points by table lookup: @@ -241,8 +247,30 @@ function SetupTrigonometricFunctions() { // 6) Use cubic spline interpolation to approximate sin(x). // 7) Negate the result if x was in the 3rd or 4th quadrant. // 8) Get rid of -0 by adding 0. - var Interpolation = function(x) { - var double_index = x * inverse_interval; + var Interpolation = function(x, phase) { + if (x < 0 || x > pi_half) { + var multiple; + while (x < -two_step_threshold || x > two_step_threshold) { + // Let's assume this loop does not terminate. + // All numbers x in each loop forms a set S. + // (1) abs(x) > 2^27 for all x in S. + // (2) abs(multiple) != 0 since (2^27 * inverse_pi_half_s26) > 1 + // (3) multiple is rounded down in 2^26 steps, so the rounding error is + // at most max(ulp, 2^26). + // (4) so for x > 2^27, we subtract at most (1+pi/4)x and at least + // (1-pi/4)x + // (5) The subtraction results in x' so that abs(x') <= abs(x)*pi/4. + // Note that this difference cannot be simply rounded off. + // Set S cannot exist since (5) violates (1). Loop must terminate. + multiple = MathFloor(x * inverse_pi_half_s_26) * s_26; + x = x - multiple * pi_half_1 - multiple * pi_half_2; + } + multiple = MathFloor(x * inverse_pi_half); + x = x - multiple * pi_half_1 - multiple * pi_half_2; + phase += multiple; + } + var double_index = x * index_convert; + if (phase & 1) double_index = samples - double_index; var index = double_index | 0; var t1 = double_index - index; var t2 = 1 - t1; @@ -251,26 +279,20 @@ function SetupTrigonometricFunctions() { var dy = y2 - y1; return (t2 * y1 + t1 * y2 + t1 * t2 * ((table_cos_interval[index] - dy) * t2 + - (dy - table_cos_interval[index + 1]) * t1)); + (dy - table_cos_interval[index + 1]) * t1)) + * (1 - (phase & 2)) + 0; } var MathSinInterpolation = function(x) { - // This is to make Sunspider's result verification happy. - if (x > four_pi) x -= four_pi; - var multiple = MathFloor(x * inverse_pi_half); - if (%_IsMinusZero(multiple)) return multiple; - x = (multiple & 1) * pi_half + - (1 - ((multiple & 1) << 1)) * (x - multiple * pi_half); - return Interpolation(x) * (1 - (multiple & 2)) + 0; + x = x * 1; // Convert to number and deal with -0. + if (%_IsMinusZero(x)) return x; + return Interpolation(x, 0); } - // Cosine is sine with a phase offset of pi/2. + // Cosine is sine with a phase offset. var MathCosInterpolation = function(x) { - var multiple = MathFloor(x * inverse_pi_half); - var phase = multiple + 1; - x = (phase & 1) * pi_half + - (1 - ((phase & 1) << 1)) * (x - multiple * pi_half); - return Interpolation(x) * (1 - (phase & 2)) + 0; + x = MathAbs(x); // Convert to number and get rid of -0. + return Interpolation(x, 1); }; %SetInlineBuiltinFlag(Interpolation); diff --git a/test/mjsunit/mjsunit.js b/test/mjsunit/mjsunit.js index 129353730..e5fb6c258 100644 --- a/test/mjsunit/mjsunit.js +++ b/test/mjsunit/mjsunit.js @@ -54,6 +54,10 @@ var assertSame; // and the properties of non-Array objects). var assertEquals; + +// The difference between expected and found value is within certain tolerance. +var assertEqualsDelta; + // The found object is an Array with the same length and elements // as the expected object. The expected object doesn't need to be an Array, // as long as it's "array-ish". @@ -247,6 +251,12 @@ var assertUnoptimized; }; + assertEqualsDelta = + function assertEqualsDelta(expected, found, delta, name_opt) { + assertTrue(Math.abs(expected - found) <= delta, name_opt); + }; + + assertArrayEquals = function assertArrayEquals(expected, found, name_opt) { var start = ""; if (name_opt) { diff --git a/test/mjsunit/sin-cos.js b/test/mjsunit/sin-cos.js index 1176b6c9d..b63c15e13 100644 --- a/test/mjsunit/sin-cos.js +++ b/test/mjsunit/sin-cos.js @@ -27,6 +27,8 @@ // Test Math.sin and Math.cos. +// Flags: --allow-natives-syntax + function sinTest() { assertEquals(0, Math.sin(0)); assertEquals(1, Math.sin(Math.PI / 2)); @@ -97,7 +99,7 @@ function abs_error(fun, ref, x) { var test_inputs = []; for (var i = -10000; i < 10000; i += 177) test_inputs.push(i/1257); -var epsilon = 0.000001; +var epsilon = 0.0000001; test_inputs.push(0); test_inputs.push(0 + epsilon); @@ -117,8 +119,8 @@ for (var i = 0; i < test_inputs.length; i++) { var x = test_inputs[i]; var err_sin = abs_error(Math.sin, sin, x); var err_cos = abs_error(Math.cos, cos, x) - assertTrue(err_sin < 1E-13); - assertTrue(err_cos < 1E-13); + assertEqualsDelta(0, err_sin, 1E-13); + assertEqualsDelta(0, err_cos, 1E-13); squares.push(err_sin*err_sin + err_cos*err_cos); } @@ -132,7 +134,7 @@ while (squares.length > 1) { } var err_rms = Math.sqrt(squares[0] / test_inputs.length / 2); -assertTrue(err_rms < 1E-14); +assertEqualsDelta(0, err_rms, 1E-14); assertEquals(-1, Math.cos({ valueOf: function() { return Math.PI; } })); assertEquals(0, Math.sin("0x00000")); @@ -141,3 +143,40 @@ assertTrue(isNaN(Math.sin(Infinity))); assertTrue(isNaN(Math.cos("-Infinity"))); assertEquals("Infinity", String(Math.tan(Math.PI/2))); assertEquals("-Infinity", String(Math.tan(-Math.PI/2))); +assertEquals("-Infinity", String(1/Math.sin("-0"))); + +// Assert that the remainder after division by pi is reasonably precise. +function assertError(expected, x, epsilon) { + assertTrue(Math.abs(x - expected) < epsilon); +} + +assertEqualsDelta(0.9367521275331447, Math.cos(1e06), 1e-15); +assertEqualsDelta(0.8731196226768560, Math.cos(1e10), 1e-08); +assertEqualsDelta(0.9367521275331447, Math.cos(-1e06), 1e-15); +assertEqualsDelta(0.8731196226768560, Math.cos(-1e10), 1e-08); +assertEqualsDelta(-0.3499935021712929, Math.sin(1e06), 1e-15); +assertEqualsDelta(-0.4875060250875106, Math.sin(1e10), 1e-08); +assertEqualsDelta(0.3499935021712929, Math.sin(-1e06), 1e-15); +assertEqualsDelta(0.4875060250875106, Math.sin(-1e10), 1e-08); +assertEqualsDelta(0.7796880066069787, Math.sin(1e16), 1e-05); +assertEqualsDelta(-0.6261681981330861, Math.cos(1e16), 1e-05); + +// Assert that remainder calculation terminates. +for (var i = -1024; i < 1024; i++) { + assertFalse(isNaN(Math.sin(Math.pow(2, i)))); +} + +assertFalse(isNaN(Math.cos(1.57079632679489700))); +assertFalse(isNaN(Math.cos(-1e-100))); +assertFalse(isNaN(Math.cos(-1e-323))); + + +function no_deopt_on_minus_zero(x) { + return Math.sin(x) + Math.cos(x) + Math.tan(x); +} + +no_deopt_on_minus_zero(1); +no_deopt_on_minus_zero(1); +%OptimizeFunctionOnNextCall(no_deopt_on_minus_zero); +no_deopt_on_minus_zero(-0); +assertOptimized(no_deopt_on_minus_zero); diff --git a/test/mozilla/mozilla.status b/test/mozilla/mozilla.status index 9e23dce35..d5e851c93 100644 --- a/test/mozilla/mozilla.status +++ b/test/mozilla/mozilla.status @@ -599,10 +599,6 @@ # Negative hexadecimal literals are parsed as NaN. This test is outdated. 'ecma/TypeConversion/9.3.1-3': [FAIL_OK], - - # Math.tan expectations are more strict than the spec. - 'ecma/Math/15.8.2.18': [FAIL_OK], - ##################### FAILING TESTS ##################### # This section is for tests that fail in V8 and pass in JSC. -- 2.34.1