2

I have succeeded in writing an Ulps based function that compares two doubles for equality. According to this page, the comparison can be made using a combination of absolute and relative epsilon or using integers (Ulps).

I have made both epsilon based and Ulps based functions. This is the epsilon based function:

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);
}
4

3 回答 3

2

以下是如何使用类型化数组的新浏览器功能提高性能的基本要点。请注意，由于没有提供本机 64 位 int 视图，因此您必须根据 2 个 32 位 int 自行修改逻辑，并确保字节顺序不会影响不同系统上的计算。我只是想解决问题的 javascript 速度部分，而不是浮点编码方面的专家。希望这很清楚：

var IsAlmostEqual_Ulps = function(A, B)
{
  var smallBufferA = new ArrayBuffer(8); //8 bytes = 64bits
  var viewAsDoubleA = new Float64Array(smallBufferA); //byteOffset=0, length=8 optional
  var viewAsIntA = new Int32Array(smallBufferA); //byteOffset=0, length=8 optional
  viewAsDoubleA.set([A]);
  console.log(viewAsIntA);
  var smallBufferB = new ArrayBuffer(8); //8 bytes = 64bits
  var viewAsDoubleB = new Float64Array(smallBufferB); //byteOffset=0, length=8 optional
  var viewAsIntB = new Int32Array(smallBufferB); //byteOffset=0, length=8 optional
  viewAsDoubleB.set([B]);
  console.log(viewAsIntB);
  //The logic below is just illustrative and may not be right. Please test & adjust
  var A_lo=viewAsIntA[1];
  var B_lo=viewAsIntB[1];
  var A_hi=viewAsIntA[0];
  var B_hi=viewAsIntB[0];
  if(A_hi<0){A_hi=Int32_MinValue-A_hi;}
  if(A_hi<0){A_hi=Int32_MinValue-A_hi;}
  //You'll have to rewrite these slightly, I think you know how
  var sub = subtract(viewAsIntA, viewAsIntB); 
  if (sub.hi < 0) sub = negate(sub);
  if (lessthan(sub, maxUlps)) return true;
}

例如，如果您调用IsAlmostEqual_Ulps(3.14159,3.14159001)，您将登录到控制台：

[-266631570, 1074340345]
[-244113572, 1074340345]

这应该会给你带来最大的性能提升。如果您想让它更快，您应该在函数调用之间重用现有缓冲区（来自全局范围或闭包），以免产生构造函数开销和垃圾收集。

于 2014-02-04T07:01:47.583 回答
2

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

这是在其上运行的虚幻游戏引擎，以了解性能类型（需要一点加载但运行非常流畅，使用 firefox 或 chrome）。

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

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

查看关于它的 John Resig（jQuery 的创建者）的博客文章。如今，您在浏览器中无法获得比这更快的速度，而且它一直在变得更快（请参阅此处的 Mozilla 团队博客文章）。

于 2014-01-30T22:21:07.790 回答
1

好吧，因为我最初的“洞察力”并没有太大帮助，所以这里有另一个答案，它只是采用您现有的函数并重新组织它们以最大限度地减少重复的对象构造函数调用：

var ULPS2 = function(){
  var buf2 = new ArrayBuffer(8);
  var dataView2A = new DataView(buf2);
  var dataView2B = new DataView(buf2);
  var aInt=new Int64(0, 0), bInt=new Int64(0, 0);
  var sub;

  this.IsAlmostEqual=function(A,B){
    if (A==B) return true;
    dataView2A.setFloat64(0, A);
    aInt.lo = dataView2A.getInt32(4) | 0;
    aInt.hi = dataView2A.getInt32(0) | 0;
    dataView2B.setFloat64(0, B);
    bInt.lo = dataView2B.getInt32(4) | 0;
    bInt.hi = dataView2B.getInt32(0) | 0;

    if(aInt.hi < 0) aInt = subtract(Int64_MinValue, aInt);

    if(bInt.hi < 0) bInt = subtract(Int64_MinValue, bInt);
    sub = subtract(aInt, bInt);
    if (sub.hi < 0) sub = negate(sub);
    if (lessthan(sub, maxUlps)) return true;
    return false;
  }

}
var Ulps2=new ULPS2();

根据http://jsbin.com/IWoyIDO/2/在 Chrome 和 Firefox 中的测试，它似乎产生了 30%-50% 的改进。不是惊人的，但至少比你最初提到的 5-10% 的改进要好。

于 2014-02-04T22:51:12.587 回答