Сравнение удвоений с использованием ULP (единицы в последнем месте)

Question

Мне удалось написать функцию на основе Ulps, которая сравнивает два двойника для равенства. Согласно this page, сравнение может быть выполнено с использованием комбинации абсолютного и относительного эпсилона или с использованием целых чисел (Ulps).

У меня есть функции на основе эпсилона и ульпа. Эта функция основана эпсилон:

 
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 основе является предпочтительным. IsAlmostEqual_Ulps работает нормально в соответствии с тестовой базой из 83 случаев, но функция довольно медленная. Для завершения тестовой базы (JSBIN) требуется около 700-900 мс при выполнении как автономный html (вне JSBIN). На основе Epsilon IsAlmostEqual_Epsilon занимает всего около 100 мс.

Есть ли что-либо, что можно сделать для ускорения IsAlmostEqual_Ulps функция? Вы можете предложить также совершенно другое решение или некоторые исправления для моего кода.

Я уже тестировал все, но он сокращает время только на 5-10%. Я ищу что-то вроде 50-80% -ного улучшения времени выполнения. Улучшение 100-500% будет прекрасным, но это может быть только сон.

right_answers в коде JSBIN получены с использованием функции C# IsAlmostEqual (см. Вверху кода JSBIN). Обе вышеприведенные функции дают одинаковые результаты во всех 83 случаях.

---

EDIT:

C++ версии от 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

Ну, так как мое оригинальное «понимание» было не слишком полезно, вот еще один ответ, который просто принимает ваши существующие функции и реорганизует их свести к минимуму повторяющихся вызовов конструктора объекта:

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%, о котором вы изначально говорили.

Answer 2

Существует один способ, который будет быстрее, наверняка (в настоящее время так быстро, как в 1,5 раза превышает скорость нативного кода), который было бы использовать asm.js, высоко оптимизируемое подмножество Javascript.

Это unreal gaming engine, работающий на нем, чтобы иметь представление о типе производительности (требуется немного загрузки, но работает очень плавно, используйте firefox или chrome).

Способ, которым он работает, заключается в том, что вы берете свой код и записываете на статически типизированном языке: C или C++. Затем скомпилируйте его в байт-код виртуальной машины LLVM C++. Затем используйте компилятор emscripten для генерации кода JavaScript asm.js.

Если браузер не обнаруживает и оптимизирует asm.js, он запускает его как Javascript. Если браузер (например, последние версии Chrome/Firefox) обнаруживает asm.js, вы получите почти собственную производительность.

Прокомментируйте blog post пользователя John Resig (создатель jQuery). В наши дни вы не можете ускориться быстрее, чем в браузере, и он становится все быстрее (см. Сообщение в блоге Mozilla here).

Answer 3

Вот основные сведения о том, как улучшить производительность, используя новые функции браузера типизированных массивов.Обратите внимание, что, поскольку нет встроенного 64-битного представления int, вам придется переработать логику самостоятельно на основе 2 32-битных ints и обеспечить, чтобы endianness не влияло на вычисления в разных системах. Я просто пытаюсь обратиться к части скорости 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] 

Что вы должны получить самый большой прирост производительности. Если вы хотите сделать это еще быстрее, вы должны повторно использовать существующие буферы (из глобальной области видимости или закрытия) между вызовами функций, чтобы не нанести накладные расходы конструктора и сборку мусора.