javascript - 使用 ULP 比较 double (最后一位的单位)

Question

我已经成功编写了一个基于 Ulps 的函数，该函数比较两个 double 是否相等。根据this page ，可以使用绝对和相对 epsilon 的组合或使用整数 (Ulps) 进行比较。

我已经制作了基于 epsilon 和基于 Ulps 的函数。这是基于 epsilon 的函数:

var IsAlmostEqual_Epsilon = function(a, b)
{
  if (a == b) return true;
  var diff = Math.abs(a - b);
  if (diff < 4.94065645841247E-320) return true;
  a = Math.abs(a);
  b = Math.abs(b);
  var smallest = (b < a) ? b : a;
  return diff < smallest * 1e-12;
}

And this is the Ulps based (DoubleToInt64Bits, subtract, negate and lessthan functions are in the below mentioned JSBIN):

var IsAlmostEqual_Ulps = function(A, B)
{
  if (A==B) return true;
  DoubleToInt64Bits(A, aInt);
  if(aInt.hi < 0) aInt = subtract(Int64_MinValue, aInt);
  DoubleToInt64Bits(B, bInt);
  if(bInt.hi < 0) bInt = subtract(Int64_MinValue, bInt);
  var sub = subtract(aInt, bInt);
  if (sub.hi < 0) sub = negate(sub);
  if (lessthan(sub, maxUlps)) return true;
  return false;
}

According to Bruce Dawson the Ulps based is preferred. IsAlmostEqual_Ulps is working ok according to test base of 83 cases, but the function is pretty slow. It takes about 700-900 ms to complete the test base (JSBIN) when executed as a standalone html (outside JSBIN). Epsilon based IsAlmostEqual_Epsilon takes only about 100 ms.

Is there anything that can be done to speedup IsAlmostEqual_Ulps function? You can propose also a completely different solution or some fixings to my code.

I have tested already the inlining everything, but it cuts the time only about 5-10%. I'm hunting something like 50-80% improvement in execution time. 100-500% improvement would be fine, but it may be only a dream.

right_answers in the JSBIN code are got using C# IsAlmostEqual function (see at the top of JSBIN code). Both above functions give the same results in all 83 cases.

---

EDIT:

C++ version from here:

bool IsAlmostEqual(double A, double B)
{
    //http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
    long long aInt = reinterpret_cast<long long&>(A);
    if (aInt < 0) aInt = -9223372036854775808LL - aInt;
    long long bInt = reinterpret_cast<long long&>(B);
    if (bInt < 0) bInt = -9223372036854775808LL - bInt;
    return (std::abs(aInt - bInt) <= 10000);
}

Answer 1

有一种方法肯定会更快(目前快于 native 代码速度的 1.5 倍)，那就是使用 asm.js ，一个高度可优化的 Javascript 子集。

这是unreal gaming engine在其上运行，以了解性能类型(需要一点加载时间，但运行非常流畅，使用 Firefox 或 chrome)。

它的工作方式是使用静态类型语言编写代码:C 或 C++。然后编译成LLVM C++虚拟机的字节码。然后使用emscripten编译器生成 asm.js Javascript 代码。

如果浏览器没有检测和优化 asm.js，它将作为 Javascript 运行。如果浏览器(例如最新版本的 Chrome/Firefox)检测到 asm.js，您将获得接近 native 的性能。

检查blog post John Resig(jQuery 的创建者)对此的看法。如今，您无法比浏览器中的速度更快，而且它会变得越来越快(请参阅 Mozilla 团队博客文章 here )。