使用ULP比较双打(最后一个单位) [英] Comparing doubles using ULPs (Units in the last place)
问题描述
我已经成功地编写了一个基于Ulps的函数，该函数将两个double进行相等性比较.根据此页面，可以使用绝对值和相对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;
}
这是基于Ulps的(DoubleToInt64Bits，subtract，negate和lessthan函数在下面提到的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;
}
根据 Bruce Dawson ，最好使用基于Ulps的软件.根据83个案例的测试基础，IsAlmostEqual_Ulps可以正常工作，但是功能相当慢.作为独立html(外部)执行时，大约需要700-900毫秒才能完成测试基础( JSBIN ) JSBIN).基于Epsilon的IsAlmostEqual_Epsilon仅花费大约100毫秒.
是否可以采取任何措施来加快IsAlmostEqual_Ulps功能的速度?您还可以提出完全不同的解决方案或对我的代码进行一些修正.
我已经测试了所有内联函数，但是它只将时间缩短了大约5-10％.我正在寻找将执行时间缩短50-80％的方法. 100-500％的改善是可以的，但这可能只是梦想.
JSBIN代码中的 right_answers是使用C#IsAlmostEqual函数获得的(请参阅JSBIN代码的顶部).在这83种情况下，以上两种功能均得出相同的结果.
来自此处的的C ++版本:
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);
}
好吧，由于我最初的见解"并没有太大帮助，因此，这是另一个答案，它只是将您现有的函数并重新组织它们以最大程度地减少重复的对象构造函数调用:
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();
基于Chrome和Firefox在 http://jsbin.com/IWoyIDO/2/，似乎可以提高30％-50％.效果不明显，但至少比您最初提到的5-10％改善.
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);
}
Well, since my original "insight" wasn't too helpful, here's another answer, that simply takes your existing functions and reorganizes them to minimize repetitive object constructor calls:
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();
Based on a test in Chrome and Firefox at http://jsbin.com/IWoyIDO/2/ , it appears to yield a 30%-50% improvement. Not phenomenal, but at least better than the 5-10% improvement you were originally mentioning.
这篇关于使用ULP比较双打(最后一个单位)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
