Trigonometric functions using fdlibm.

src/math.js

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 "use strict";
 
 // This file relies on the fact that the following declarations have been made
 // in runtime.js:
 // var $Object = global.Object;
 
@@ skipping 38 matching lines @@
 // ToNumber (valueOf) is called.
 function MathAtan2JS(y, x) {
   return %MathAtan2(TO_NUMBER_INLINE(y), TO_NUMBER_INLINE(x));
 }
 
 // ECMA 262 - 15.8.2.6
 function MathCeil(x) {
   return -MathFloor(-x);
 }
 
-// ECMA 262 - 15.8.2.7
-function MathCos(x) {
-  x = MathAbs(x);  // Convert to number and get rid of -0.
-  return TrigonometricInterpolation(x, 1);
-}
-
 // ECMA 262 - 15.8.2.8
 function MathExp(x) {
   return %MathExpRT(TO_NUMBER_INLINE(x));
 }
 
 // ECMA 262 - 15.8.2.9
 function MathFloor(x) {
   x = TO_NUMBER_INLINE(x);
   // It's more common to call this with a positive number that's out
   // of range than negative numbers; check the upper bound first.
@@ skipping 82 matching lines @@
   var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
   // Division by 0x100000000 through multiplication by reciprocal.
   return (x < 0 ? (x + 0x100000000) : x) * 2.3283064365386962890625e-10;
 }
 
 // ECMA 262 - 15.8.2.15
 function MathRound(x) {
   return %RoundNumber(TO_NUMBER_INLINE(x));
 }
 
-// ECMA 262 - 15.8.2.16
+// ECMA 262 - 15.8.2.17
+function MathSqrt(x) {
+  return %_MathSqrtRT(TO_NUMBER_INLINE(x));
+}
+
+// Non-standard extension.
+function MathImul(x, y) {
+  return %NumberImul(TO_NUMBER_INLINE(x), TO_NUMBER_INLINE(y));
+}
+
+// -------------------------------------------------------------------
+
+// A straightforward translation of fdlibm routines for sin, cos, and
+// tan, by Raymond Toy (rtoy@google.com).
+
+// ====================================================
+// Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
+//
+// Developed at SunSoft, a Sun Microsystems, Inc. business.
+// Permission to use, copy, modify, and distribute this
+// software is freely granted, provided that this notice
+// is preserved.
+// ====================================================
+
+var invpio2 = 6.36619772367581382433e-01;
+var pio2_1 = 1.57079632673412561417e+00;
+var pio2_1t = 6.07710050650619224932e-11;
+var pio2_2 = 6.07710050630396597660e-11;
+var pio2_2t = 2.02226624879595063154e-21;
+
+// Table of values of multiples of pi/2 from pi/2 to 50*pi/2. This is
+// used as a quick check to see if an argument is close to a multiple
+// of pi/2 and needs extra bits for reduction.  This array contains
+// the high word the multiple of pi/2.
+
+var npio2_hw = [
+  0x3FF921FB, 0x400921FB, 0x4012D97C, 0x401921FB, 0x401F6A7A, 0x4022D97C,
+  0x4025FDBB, 0x402921FB, 0x402C463A, 0x402F6A7A, 0x4031475C, 0x4032D97C,
+  0x40346B9C, 0x4035FDBB, 0x40378FDB, 0x403921FB, 0x403AB41B, 0x403C463A,
+  0x403DD85A, 0x403F6A7A, 0x40407E4C, 0x4041475C, 0x4042106C, 0x4042D97C,
+  0x4043A28C, 0x40446B9C, 0x404534AC, 0x4045FDBB, 0x4046C6CB, 0x40478FDB,
+  0x404858EB, 0x404921FB
+];
+
+macro REMPIO2(x)
+  var n, y0, y1;
+  var hx = %_DoubleHi(x);
+  var ix = hx & 0x7fffffff;
+
+  if (ix < 0x4002d97c) {
+    // |x| ~< 3*pi/4, special case with n = +/- 1
+    if (hx > 0) {
+      var z = x - pio2_1;
+      if (ix != 0x3ff921fb) {
+        // 33+53 bit pi is good enough
+        y0 = z - pio2_1t;
+        y1 = (z - y0) - pio2_1t;
+      } else {
+        // near pi/2, use 33+33+53 bit pi
+        z -= pio2_2;
+        y0 = z - pio2_2t;
+        y1 = (z - y0) - pio2_2t;
+      }
+      n = 1;
+    } else {
+      // Negative x
+      var z = x + pio2_1;
+      if (ix != 0x3ff921fb) {
+        // 33+53 bit pi is good enough
+        y0 = z + pio2_1t;
+        y1 = (z - y0) + pio2_1t;
+      } else {
+        // near pi/2, use 33+33+53 bit pi
+        z += pio2_2;
+        y0 = z + pio2_2t;
+        y1 = (z - y0) + pio2_2t;
+      }
+      n = -1;
+    }
+  } else if (ix <= 0x413921fb) {
+    // |x| ~<= 2^19*(pi/2), medium size
+    var t = MathAbs(x);
+    n = MathRound(t * invpio2);
+    var fn = n;
+    var r = t - fn * pio2_1;
+    var w = fn * pio2_1t;
+    // First round good to 85 bit
+    if (n < 32 && ix != npio2_hw[n - 1]) {
+      // Quick check for cancellation
+      y0 = r - w;
+    } else {
+      var j = ix >> 20;
+      y0 = r - w;
+      var i = j - (( %_DoubleHi(y0) >> 20) & 0x7ff);
+      if (i > 16) {
+        // 2nd iteration needed, good to 118
+        t = r;
+        w = fn * pio2_2;
+        r = t - w;
+        w = fn * pio2_2t - ((t - r) - w);
+        y0 = r - w;
+      }

[Raymond Toy, 2014/06/02 17:26:11]

As you mentioned via email, you've removed the 3rd iteration. This is really
needed if you want to be able to reduce multiples of pi/2 accurately.

[Yang, 2014/06/03 07:01:45]

That's true. However, the reduction step is not exposed as a library function.
From what I have seen, the third step seems to only affect y1. With a y0 really
close to y1, it does not change the result of sine or cosine. This is also why I
was asking for a test case where removing this third step would make a
difference.

+    }
+    y1 = (r - y0) - w;
+    if (hx < 0) {
+      n = -n;
+      y0 = -y0;
+      y1 = -y1;
+    }
+  } else if (ix >= 0x7ff00000) {

[Raymond Toy, 2014/06/09 21:28:38]

Why is this case removed?

[Yang, 2014/06/10 06:51:54]

This case wasn't removed. It was moved to C++. Motivation being that we don't
need duplicate code in sin/cos/tan when this is a rare case where performance
does not matter.

+    n = 0;
+    y0 = NAN;
+    y1 = NAN;
+  } else {
+    // Need to do full Payne-Hanek reduction here!
+    var r = %RemPiO2(x);
+    n = r[0];
+    y0 = r[1];
+    y1 = r[2];
+  }
+endmacro
+
+// Sine for [-pi/4, pi/4], pi/4 ~ 0.7854
+
+var S1 = -1.66666666666666324348e-01;
+var S2 = 8.33333333332248946124e-03;
+var S3 = -1.98412698298579493134e-04;
+var S4 = 2.75573137070700676789e-06;
+var S5 = -2.50507602534068634195e-08;
+var S6 = 1.58969099521155010221e-10;
+
+function KernelSin(x, y) {
+  var z = x * x;
+  var v = z * x;
+  var r = S2 + z * (S3 + z * (S4 + z * (S5 + z * S6)));
+  return x - ((z * (0.5 * y - v * r) - y) - v * S1);
+}
+
+// Cosine for [-pi/4, pi/4], pi/4 ~ 0.7854
+
+var C1 = 4.16666666666666019037e-02;
+var C2 = -1.38888888888741095749e-03;
+var C3 = 2.48015872894767294178e-05;
+var C4 = -2.75573143513906633035e-07;
+var C5 = 2.08757232129817482790e-09;
+var C6 = -1.13596475577881948265e-11;
+
+function KernelCos(x, y) {
+  var ix = %_DoubleHi(x) & 0x7fffffff;
+  var z = x * x;
+  var r = z * (C1 + z * (C2 + z * (C3 + z * (C4 + z * (C5 + z * C6)))));
+  if (ix < 0x3fd33333) {
+    return 1 - (0.5 * z - (z * r - x * y));
+  } else {
+    var qx;
+    if (ix > 0x3fe90000) {
+      qx = 0.28125;
+    } else {
+      qx = %_ConstructDouble(%_DoubleHi(0.25 * x), 0);
+    }
+    var hz = 0.5 * z - qx;
+    var a = 1 - qx;
+    return a - (hz - (z * r - x * y));
+  }
+}
+
+// Tangent for [-pi/4, pi/4], pi/4 ~ 0.7854
+
+var T0 = 3.33333333333334091986e-01;
+var T1 = 1.33333333333201242699e-01;
+var T2 = 5.39682539762260521377e-02;
+var T3 = 2.18694882948595424599e-02;
+var T4 = 8.86323982359930005737e-03;
+var T5 = 3.59207910759131235356e-03;
+var T6 = 1.45620945432529025516e-03;
+var T7 = 5.88041240820264096874e-04;
+var T8 = 2.46463134818469906812e-04;
+var T9 = 7.81794442939557092300e-05;
+var T10 = 7.14072491382608190305e-05;
+var T11 = -1.85586374855275456654e-05;
+var T12 = 2.59073051863633712884e-05;
+
+function KernelTan(x, y, returnTan) {
+  var z;
+  var w;
+  var hx = %_DoubleHi(x);
+  var ix = hx & 0x7fffffff;
+
+  if (ix < 0x3e300000) {
+    // x < 2^-28
+    // We don't try to generate inexact.
+    if (((ix | %_DoubleLo(x)) | (returnTan + 1)) == 0) {
+      return 1 / Math.abs(x);
+    } else {
+      if (returnTan == 1) {
+        return x;
+      } else {
+        // Compute -1/(x + y) carefully
+        var w = x + y;
+        var z = %_ConstructDouble( %_DoubleHi(w), 0);
+        var v = y - (z - x);
+        var a = -1 / w;
+        var t = %_ConstructDouble( %_DoubleHi(a), 0);
+        var s = 1 + t * z;
+        return t + a * (s + t * v);
+      }
+    }
+  }
+  if (ix >= 0x3fe59429) {
+    // |x| > .6744
+    if (x < 0) {
+      x = -x;
+      y = -y;
+    }
+    var pio4 = 7.85398163397448278999e-01;
+    var pio4lo = 3.06161699786838301793e-17;
+    z = pio4 - x;
+    w = pio4lo - y;
+    x = z + w;
+    y = 0;
+  }
+  z = x * x;
+  w = z * z;
+  //
+  // Break x^5*(T[1]+x^2*T[2]+...) into
+  // x^5(T[1]+x^4*T[3]+...+x^20*T[11]) +
+  // x^5(x^2*(T[2]+x^4*T[4]+...+x^22*[T12]))
+  //
+  var r = T1 + w * (T3 + w * (T5 + w * (T7 + w * (T9 + w * T11))));
+  var v = z * (T2 + w * (T4 + w * (T6 + w * (T8 + w * (T10 + w * T12)))));
+  var s = z * x;
+  r = y + z * (s * (r + v) + y);
+  r = r + T0 * s;
+  w = x + r;
+  if (ix >= 0x3fe59428) {
+    return (1 - ((hx >> 30) & 2)) *
+      (returnTan - 2.0 * (x - (w * w / (w + returnTan) - r)));
+  }
+  if (returnTan == 1) {
+    return w;
+  } else {
+    // Compute -1/(x+r) accurately
+    z = %_ConstructDouble( %_DoubleHi(w), 0);
+    v = r - (z - x); // z+v = r+x
+    var a = -1 / w;
+    var t = %_ConstructDouble( %_DoubleHi(a), 0);
+    s = 1 + t * z;
+    return t + a * (s + t * v);
+  }
+}
+
+
+function MathSinSlow(x) {
+  REMPIO2(x);
+  if (n & 2) {
+    if (n & 1) {
+      return -KernelCos(y0, y1);
+    } else {
+      return -KernelSin(y0, y1);
+    }
+  } else {
+    if (n & 1) {
+      return KernelCos(y0, y1);
+    } else {
+      return KernelSin(y0, y1);
+    }
+  }
+}
+
+function MathCosSlow(x) {
+  REMPIO2(x);
+  if (n & 2) {
+    if (n & 1) {
+      return KernelSin(y0, y1);
+    } else {
+      return -KernelCos(y0, y1);
+    }
+  } else {
+    if (n & 1) {
+      return -KernelSin(y0, y1);
+    } else {
+      return KernelCos(y0, y1);
+    }
+  }
+}
+
+function MathTanSlow(x) {
+  REMPIO2(x);
+  // flag is 1 if n is even and -1 if n is odd
+  var flag = (n & 1) ? -1 : 1;
+  return KernelTan(y0, y1, flag)
+}
+
+//ECMA 262 - 15.8.2.16
 function MathSin(x) {
   x = x * 1;  // Convert to number and deal with -0.
   if (%_IsMinusZero(x)) return x;
-  return TrigonometricInterpolation(x, 0);
-}
-
-// ECMA 262 - 15.8.2.17
-function MathSqrt(x) {
-  return %_MathSqrtRT(TO_NUMBER_INLINE(x));
-}
-
-// ECMA 262 - 15.8.2.18
+  if ((%_DoubleHi(x) & 0x7fffffff) <= 0x3fe921fb) {
+    // |x| < pi/4, approximately.  No reduction needed.
+    var z = x * x;
+    var v = z * x;
+    var r = S2 + z * (S3 + z * (S4 + z * (S5 + z * S6)));
+    return x + v * (S1 + z * r);
+  }
+  return MathSinSlow(x);
+}
+
+//ECMA 262 - 15.8.2.7
+function MathCos(x) {
+  x = x * 1;  // Convert to number;
+  if ((%_DoubleHi(x) & 0x7fffffff) <= 0x3fe921fb) {
+    // |x| < pi/4, approximately.  No reduction needed.
+    return KernelCos(x, 0);
+  }
+  return MathCosSlow(x);
+}
+
+//ECMA 262 - 15.8.2.18
 function MathTan(x) {
-  return MathSin(x) / MathCos(x);
-}
-
-// Non-standard extension.
-function MathImul(x, y) {
-  return %NumberImul(TO_NUMBER_INLINE(x), TO_NUMBER_INLINE(y));
-}
-
-
-var kInversePiHalf      = 0.636619772367581343;      // 2 / pi
-var kInversePiHalfS26   = 9.48637384723993156e-9;    // 2 / pi / (2^26)
-var kS26                = 1 << 26;
-var kTwoStepThreshold   = 1 << 27;
-// pi / 2 rounded up
-var kPiHalf             = 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 kPiHalf1            = 1.570796325802803040;      // 0x00000054fb21f93f
-var kPiHalf2            = 9.920935796805404252e-10;  // 0x3326a611460b113e
-
-var kSamples;            // Initialized to a number during genesis.
-var kIndexConvert;       // Initialized to kSamples / (pi/2) during genesis.
-var kSinTable;           // Initialized to a Float64Array during genesis.
-var kCosXIntervalTable;  // Initialized to a Float64Array during genesis.
-
-// This implements sine using the following algorithm.
-// 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:
-//    dsin(x)/dx = cos(x) = sin(pi/2-x) for x in [0, pi/2].
-// 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.
-function TrigonometricInterpolation(x, phase) {
-  if (x < 0 || x > kPiHalf) {
-    var multiple;
-    while (x < -kTwoStepThreshold || x > kTwoStepThreshold) {
-      // 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 * kInversePiHalfS26) * kS26;
-      x = x - multiple * kPiHalf1 - multiple * kPiHalf2;
-    }
-    multiple = MathFloor(x * kInversePiHalf);
-    x = x - multiple * kPiHalf1 - multiple * kPiHalf2;
-    phase += multiple;
-  }
-  var double_index = x * kIndexConvert;
-  if (phase & 1) double_index = kSamples - double_index;
-  var index = double_index | 0;
-  var t1 = double_index - index;
-  var t2 = 1 - t1;
-  var y1 = kSinTable[index];
-  var y2 = kSinTable[index + 1];
-  var dy = y2 - y1;
-  return (t2 * y1 + t1 * y2 +
-              t1 * t2 * ((kCosXIntervalTable[index] - dy) * t2 +
-                         (dy - kCosXIntervalTable[index + 1]) * t1))
-         * (1 - (phase & 2)) + 0;
+  x = x * 1;  // Convert to number and deal with -0.
+  if (%_IsMinusZero(x)) return x;
+  if ((%_DoubleHi(x) & 0x7fffffff) <= 0x3fe921fb) {
+    // |x| < pi/4, approximately.  No reduction needed.
+    return KernelTan(x, 0, 1);
+  }
+  return MathTanSlow(x);
 }
 
 // -------------------------------------------------------------------
 
 function SetUpMath() {
   %CheckIsBootstrapping();
 
   %SetPrototype($Math, $Object.prototype);
   %SetProperty(global, "Math", $Math, DONT_ENUM);
   %FunctionSetInstanceClassName(MathConstructor, 'Math');
@@ skipping 36 matching lines @@
     "max", MathMax,
     "min", MathMin,
     "imul", MathImul
   ));
 
   %SetInlineBuiltinFlag(MathCeil);
   %SetInlineBuiltinFlag(MathRandom);
   %SetInlineBuiltinFlag(MathSin);
   %SetInlineBuiltinFlag(MathCos);
   %SetInlineBuiltinFlag(MathTan);
-  %SetInlineBuiltinFlag(TrigonometricInterpolation);
+  %SetInlineBuiltinFlag(KernelSin);
+  %SetInlineBuiltinFlag(KernelCos);
+  %SetInlineBuiltinFlag(KernelTan);
 }
 
 SetUpMath();