javascript — Сравнение двойников с использованием ULPs (единицы на последнем месте)
Мне удалось написать функцию на основе Ulps, которая сравнивает два двойных на равенство. В соответствии с эта страница, сравнение может быть сделано с использованием комбинации абсолютного и относительного эпсилона или целых чисел (Ulps).
Я сделал функции как на основе эпсилон, так и на основе ульпса. Это функция на основе эпсилона:
var IsAlmostEqual_Epsilon = function (a, b)
{
if (a == b) вернет true;
var diff = Math.abs (a - b);
if (diff < 4.94065645841247E-320) вернуть true;
a = Math.abs (a);
b = Math.abs (b);
var smalllest = (б < а) б: а;
обратная разница < самый маленький * 1e-12;
}
И это на основе Ульпов (DoubleToInt64Bits, subtract, negate а также lessthan функции находятся в указанном ниже JSBIN):
var IsAlmostEqual_Ulps = function (A, B)
{
if (A == B) вернуть true;
DoubleToInt64Bits (A, aInt);
если (aInt.hi < 0) aInt = вычитать (Int64_MinValue, aInt);
DoubleToInt64Bits (B, bInt);
если (bInt.hi < 0) bInt = вычитать (Int64_MinValue, bInt);
var sub = вычитать (aInt, bInt);
если (sub.hi < 0) sub = отрицание (sub);
if (lessthan (sub, maxUlps)) возвращает true;
вернуть ложь;
}
В соответствии с Брюс Доусон основанный на Ulps является предпочтительным. IsAlmostEqual_Ulps работает нормально в соответствии с тестовой базой в 83 случаях, но функция довольно медленная. Требуется около 700-900 мс для завершения тестовой базы (JSBIN) при выполнении в виде отдельного html (вне JSBIN). На основе эпсилон IsAlmostEqual_Epsilon занимает всего около 100 мс.
Есть ли что-нибудь, что можно сделать, чтобы ускорить IsAlmostEqual_Ulps функционировать? Вы можете предложить также совершенно другое решение или некоторые исправления для моего кода.
Я уже проверил встраивание всего, но это сокращает время только приблизительно на 5-10%. Я ищу что-то вроде 50-80% улучшения времени выполнения. Улучшение на 100-500% было бы хорошо, но это может быть только мечтой.
right_answers в коде JSBIN получены с использованием 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%, о котором вы изначально упоминали.
Другие решения
Есть один способ, который наверняка будет быстрее (в настоящее время он в 1,5 раза быстрее, чем собственный код), который можно использовать asm.js, высоко оптимизируемое подмножество Javascript.
Это нереальный игровой движок на нем, чтобы иметь представление о типе производительности (загрузка занимает немного времени, но работает очень гладко, используйте Firefox или Chrome).
Это работает так, что вы берете свой код и пишете на статически типизированном языке: C или C ++. Затем скомпилируйте его в байт-код виртуальной машины C ++ LLVM. Затем используйте emscripten компилятор для генерации asm.js кода Javascript.
Если браузер не обнаруживает и не оптимизирует asm.js, он запускается как Javascript. Если браузер (например, последние версии Chrome / Firefox) обнаружит asm.js, у вас будет почти собственная производительность.
Проверить Сообщение блога об этом Джона Ресига (создателя jQuery). В наши дни вы не можете работать быстрее, чем в браузере, и он становится все быстрее (см. Сообщение в блоге команды Mozilla) Вот).
Вот основная суть того, как повысить производительность, используя новые функции браузера типизированных массивов. Обратите внимание, что поскольку не предусмотрено собственное 64-битное представление int, вам придется самостоятельно перерабатывать логику, основываясь на 2 32-битных целочисленных значениях, и обеспечить, чтобы порядковый номер не влиял на вычисления в разных системах. Я просто пытаюсь решить часть проблемы со скоростью 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]
Это должно принести вам наибольшее повышение производительности. Если вы хотите сделать это еще быстрее, вы должны повторно использовать существующие буферы (из глобальной области видимости или замыкания) между вызовами функций, чтобы не вызывать накладные расходы конструктора и сборку мусора.