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，您将获得接近原生的性能。

检查 blog post John Resig(jQuery 的创造者)关于它的。如今，您无法获得比浏览器更快的速度，而且速度还在不断提高(请参阅 Mozilla 团队博客文章 here)。