Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. Обычно делается методом деления пополам:
double a = 1e10;
double epsilon = a;
while((a + epsilon/2) != a) epsilon /= 2;
Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
MS>Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?
double a = 1e10;
double epsilon = a;
int i = 0;
while ((a + epsilon / 2) != a)
{
epsilon /= 2;
++i;
}
Console.WriteLine("{0}, {1}, {2}, {3}", a, epsilon, a / Math.Pow(2, 53), i);
Я проверил для разных чисел... это цикл всегда выполняется 53 раза те нужно разделить на 2^53... работает и для double и для float...
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
WH> double a = 1e10;
WH> double epsilon = a;
WH> int i = 0;
WH> while ((a + epsilon / 2) != a)
WH> {
WH> epsilon /= 2;
WH> ++i;
WH> }
WH> Console.WriteLine("{0}, {1}, {2}, {3}", a, epsilon, a / Math.Pow(2, 53), i);
WH>
WH>Я проверил для разных чисел... это цикл всегда выполняется 53 раза те нужно разделить на 2^53... работает и для double и для float...
Оптимизатор все запихивает в регистры и оперирует длинными числами. Ну не может быть одинаково для double и float. Но идея правильная — надо поделить (или умножить) число на некую константу.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
MS>Оптимизатор все запихивает в регистры и оперирует длинными числами. Ну не может быть одинаково для double и float. Но идея правильная — надо поделить (или умножить) число на некую константу.
float
Single Precision
The IEEE single precision floating point standard representation requires a 32 bit word, which may be represented as numbered from 0 to 31, left to right. The first bit is the sign bit, S, the next eight bits are the exponent bits, 'E', and the final 23 bits are the fraction 'F':
double
Double Precision The IEEE double precision floating point standard representation requires a 64 bit word, which may be represented as numbered from 0 to 63, left to right. The first bit is the sign bit, S, the next eleven bits are the exponent bits, 'E', and the final 52 bits are the fraction 'F':
2^53 вытекает из представления double тк мантиса у нас состоит из 52х двоичных знаков то для того чтобы число не отражалось на этой мантисе оно должно быть меньше в 2^53 раз. Для float'а должно быть 2^24 но и C# и VC++8 даже без оптимизации всеравно дают один и тотже результат.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Для float'а должно быть 2^24 но и C# и VC++8 даже без оптимизации всеравно дают один и тотже результат.
Не согласен с обоими в этом вопросе. Так говорят только те, кто не понимает сути дела. Что показывает epsilon?
Вообще epsilon определяется всегда относительно единицы. Если хотите получить его относительно другого числа, то:
1 + epsilon != 1
a + a*epsilon != a
Рекомендую определять epsilon для любого числа как a*epsilon. Не уверен на все 100%, что это будет верным всегда.
Вот подробный код с исследованием этого вопроса. Разберитесь, пожалуйста. Любые незначительные модификации джля произвольных чисел могут приводить к неверным результатам.
using System;
namespace Epsilon
{
/// <summary>
/// Summary description for Class1.
/// </summary>class Class1
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
// Неверный способ для float.float epsilon = 1.0f;
float one = 1.0f;
int i = 0;
while( one + epsilon/2 != one )
{
epsilon /= 2.0f;
i ++;
}
one = one + epsilon;
one = one - 1.0f;
Console.WriteLine( "Неверный способ для float" );
Console.WriteLine( "{0} {1}", one, i );
Console.WriteLine();
// epsilon для float.
epsilon = 1.0f;
one = 1.0f;
float tmp = one;
i = 0;
while( (float)(one + epsilon/2.0f) != (float)one )
{
epsilon /= 2.0f;
i ++;
}
Console.WriteLine( "epsilon для float" );
tmp = tmp + epsilon;
epsilon = tmp - one;
Console.WriteLine( "{0} {1}", epsilon, i );
Console.WriteLine();
// epsilon для double.double epsilonD = 1.0;
double oneD = 1.0;
double tmpD = oneD;
i = 0;
while( oneD + epsilonD/2.0 != oneD )
{
epsilonD /= 2.0;
i ++;
}
Console.WriteLine( "epsilon для double" );
tmpD = tmpD + epsilonD;
epsilonD = tmpD - oneD;
Console.WriteLine( "{0} {1}", epsilonD, i );
Console.WriteLine();
// epsilon для заданного числа a типа float.float a = 0.01234567f;
tmp = a;
epsilon = a * 1.192093E-07f;
i = 0;
while( (float)(a + epsilon/2.0f) != (float)a )
{
epsilon /= 2.0f;
i ++;
}
Console.WriteLine( "epsilon для заданного числа " + a.ToString() + " типа float" );
tmp = tmp + epsilon;
epsilon = tmp - a;
Console.WriteLine( "{0} {1}", epsilon, i );
Console.WriteLine();
// epsilon для заданного числа a типа double.double aD = 0.0123456789112345;
tmpD = aD;
epsilonD = aD * 2.22044604925031E-16;
i = 0;
while( aD + epsilonD/2.0 != aD )
{
epsilonD /= 2.0;
i ++;
}
Console.WriteLine( "epsilon для заданного числа " + aD.ToString() + " типа double" );
tmpD = tmpD + epsilonD;
epsilonD = tmpD - aD;
Console.WriteLine( "{0} {1}", epsilonD, i );
Console.WriteLine();
// epsilon для числа 1 типа float.
a = 1.0f;
tmp = a;
epsilon = a * 1.192093E-07f;
i = 0;
while( (float)(a + epsilon/2.0f) != (float)a )
{
epsilon /= 2.0f;
i ++;
}
Console.WriteLine( "epsilon для числа 1 типа float" );
tmp = tmp + epsilon;
epsilon = tmp - a;
Console.WriteLine( "{0} {1}", epsilon, i );
Console.WriteLine();
// epsilon для заданного числа 1 типа double.
aD = 1.0;
tmpD = aD;
epsilonD = aD * 2.22044604925031E-16;
i = 0;
while( aD + epsilonD/2.0 != aD )
{
epsilonD /= 2.0;
i ++;
}
Console.WriteLine( "epsilon для числа 1 типа double" );
tmpD = tmpD + epsilonD;
epsilonD = tmpD - aD;
Console.WriteLine( "{0} {1}", epsilonD, i );
Console.ReadLine();
}
}
}
Результат:
Неверный способ для float
0 52
epsilon для float
1,192093E-07 23
epsilon для double
2,22044604925031E-16 52
epsilon для заданного числа 0,01234567 типа float
9,313226E-10 1
epsilon для заданного числа 0,0123456789112345 типа double
1,73472347597681E-18 1
epsilon для числа 1 типа float
1,192093E-07 1
epsilon для числа 1 типа double
2,22044604925031E-16 0
Заметьте, что единица в общем случае сразу определяется для double, для float этого не происходит, потому что, вообще говоря, умножение в компьютере не обладает всеми своими свойствами.
Еще раз, рекомендую определять за ноль итераций epsilon для любого числа a как a*epsilon, где epsilon -- epsilon для типа a, которая на одинаковых процессорах (семействах) одна и та же.
Если хотите 100%, то используйте приведенные алгоритмы "epsilon для заданного числа a типа float/double".
Для упражнения, попробуйте убрать tmp. Истинной проверкой считайте результат, когда epsilon стартует с 1. Если сразу после цикла выводить epsilon, то не выйдет.
Здравствуйте, FedorovStanislav, Вы писали:
FS>Не согласен с обоими в этом вопросе. Так говорят только те, кто не понимает сути дела. Что показывает epsilon? FS>Вообще epsilon определяется всегда относительно единицы. Если хотите получить его относительно другого числа, то: FS>1 + epsilon != 1 FS>a + a*epsilon != a
Ну, а я о чем говорил?
MS>Но идея правильная — надо поделить (или умножить) число на некую константу.
Вот эта константа и есть epsilon (ну или 1/epsilon)
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
MS>Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. Обычно делается методом деления пополам:
MS>
MS>double a = 1e10;
MS>double epsilon = a;
MS>while((a + epsilon/2) != a) epsilon /= 2;
MS>
MS>Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?
Ну если речь идет о стандартном floating point, или об известном хотя бы, то нужно взять описание формата и посмотреть сколько там бит на мантиссу и как нормализуются числа.
Здравствуйте, McSeem2, Вы писали:
MS>Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. Обычно делается методом деления пополам:
MS>
MS>double a = 1e10;
MS>double epsilon = a;
MS>while((a + epsilon/2) != a) epsilon /= 2;
MS>
MS>Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?
Наверно я сильно туплю, но очень интересно... может кто нибудь объяснить почему не подходит просто FLT_EPSILON (DBL_EPSILON)?
Здравствуйте, korzhik, Вы писали:
K>Наверно я сильно туплю, но очень интересно... может кто нибудь объяснить почему не подходит просто FLT_EPSILON (DBL_EPSILON)?
Все уже выяснили. Именно ее и надо брать, но домножать на само число. Значение выражения "(1.0+DBL_EPSILON)>1.0" равно true. А вот "(1000000.0+DBL_EPSILON)>1000000.0" уже будет false. Для значения в миллион надо брать миллион эпсилонов
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
K>>Наверно я сильно туплю, но очень интересно... может кто нибудь объяснить почему не подходит просто FLT_EPSILON (DBL_EPSILON)? MS>Все уже выяснили. Именно ее и надо брать, но домножать на само число. Значение выражения "(1.0+DBL_EPSILON)>1.0" равно true. А вот "(1000000.0+DBL_EPSILON)>1000000.0" уже будет false. Для значения в миллион надо брать миллион эпсилонов
Ну если совсем точно, то не на число наверное, а на его экспоненту?
Здравствуйте, LelicDsp, Вы писали:
K>>>Наверно я сильно туплю, но очень интересно... может кто нибудь объяснить почему не подходит просто FLT_EPSILON (DBL_EPSILON)? MS>>Все уже выяснили. Именно ее и надо брать, но домножать на само число. Значение выражения "(1.0+DBL_EPSILON)>1.0" равно true. А вот "(1000000.0+DBL_EPSILON)>1000000.0" уже будет false. Для значения в миллион надо брать миллион эпсилонов
LD>Ну если совсем точно, то не на число наверное, а на его экспоненту?
Почему: a + a*epsilon <> a
LD>>Ну если совсем точно, то не на число наверное, а на его экспоненту? FS>Почему: a + a*epsilon <> a
Ну возьмем стандартный флоат, у него мантисса 23 бита. Рассмотрим нормализованное число
1.0000000000000000000000b*exp для него epsilon равен 0.0000000000000000000001b*exp, где exp- экспонента числа.
Но для числа 1.1000000000000000000000b*exp epsilon тоже равен 0.0000000000000000000001b*exp.
MS>Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. Обычно делается методом деления пополам:
MS>Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?
Самого проблема очень интерисует.
Только не врубился к какому мнению (коду) господа пришли ?
Объясните плиз. дураку
Здравствуйте, Шебеко Евгений, Вы писали:
MS>>Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. Обычно делается методом деления пополам:
MS>>Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?
ШЕ> Самого проблема очень интерисует. ШЕ> Только не врубился к какому мнению (коду) господа пришли ? ШЕ> Объясните плиз. дураку
MS>>>Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. N>В STL все это уже есть N>смотри файл limits N>#include <limits> N>std::numeric_limits<double>::epsilon()
Если бы. Смотри внимательно постановку задачи и обсуждение.
Здравствуйте, Шебеко Евгений, Вы писали:
ШЕ> Самого проблема очень интерисует. ШЕ> Только не врубился к какому мнению (коду) господа пришли ? ШЕ> Объясните плиз. дураку
a += a * DBL_EPSILON должно по идее гарантированно изменить значение a на минимально возможную величину.
Просто a += DBL_EPSION — это не правильно, поскольку DBL_EPSILON (ну или FLT_EPSILON) вычислена для единицы. Для doudle она примерно 2.22e-16. Понятно, что для Планковских масштабов она сама по себе не катит — очень грубо. А для величин больше 10 (не говоря уже о космических масштабах) прибавление этой epsilon вообще не повлияет на значение.
Но как как абсолютно достоверно сравнить два числа на равенство, когда шум допустим только в последнем разряде? То есть, когда два числа различаются на минимально возможную величину? По идее надо:
Но это же сколько лишнего! Не проще ли неким хаком занулить последний разряд мантиссы и потом сравнивать на строгое равенство? Что-то мне подсказывает, что так делать категорически нельзя. То есть, в большинстве случаев работать будет, но раз в год выстрелит не туда.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, FedorovStanislav, Вы писали:
FS>>Не согласен с обоими в этом вопросе. Так говорят только те, кто не понимает сути дела. Что показывает epsilon? FS>>Вообще epsilon определяется всегда относительно единицы. Если хотите получить его относительно другого числа, то: FS>>1 + epsilon != 1 FS>>a + a*epsilon != a
MS>Ну, а я о чем говорил?
MS>>Но идея правильная — надо поделить (или умножить) число на некую константу.
MS>Вот эта константа и есть epsilon (ну или 1/epsilon)
можно также заменить операцию деления на операцию умножения
MS>double a = 1e10;
MS>double epsilon = a;
MS>while((a + epsilon/2) != a) epsilon /= 2;
MS>
Этот код даёт неправильные результаты.
Можете запустить его для 1.0
std::numeric_limits<double>::epsilon()
не получите.
MS>Но как как абсолютно достоверно сравнить два числа на равенство, когда шум допустим только в последнем разряде? То есть, когда два числа различаются на минимально возможную величину? По идее надо: MS>
Этот код тоже похоже неправильный. У него почему-то срывает крышу на отрицательных числах.
MS>Но это же сколько лишнего! Не проще ли неким хаком занулить последний разряд мантиссы и потом сравнивать на строгое равенство? Что-то мне подсказывает, что так делать категорически нельзя. То есть, в большинстве случаев работать будет, но раз в год выстрелит не туда.
А хак есть.
Трудно без полной практической проверки утверждать что он 100% работоспособный.
Но всё же.
Double Precision
The IEEE double precision floating point standard representation requires a 64 bit word, which may be represented as numbered from 0 to 63, left to right. The first bit is the sign bit, S, the next eleven bits are the exponent bits, 'E', and the final 52 bits are the fraction 'F':
S EEEEEEEEEEE FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
0 1 11 12 63
The value V represented by the word may be determined as follows:
If E=2047 and F is nonzero, then V=NaN ("Not a number")
If E=2047 and F is zero and S is 1, then V=-Infinity
If E=2047 and F is zero and S is 0, then V=Infinity
If 0<E<2047 then V=(-1)**S * 2 ** (E-1023) * (1.F) where "1.F" is intended to represent the binary number created by prefixing F with an implicit leading 1 and a binary point.
If E=0 and F is nonzero, then V=(-1)**S * 2 ** (-1022) * (0.F) These are "unnormalized" values.
If E=0 and F is zero and S is 1, then V=-0
If E=0 and F is zero and S is 0, then V=0
v 1.0000000000000000 double
*uv 0x3ff0000000000000 unsigned __int64
g 1.0000000000000002 double
*ug 0x3ff0000000000001 unsigned __int64
v 2.2204460492503131e-016 double
*uv 0x3cb0000000000000 unsigned __int64
g 2.2204460492503136e-016 double
*ug 0x3cb0000000000001 unsigned __int64
v 16.000000000000000 double
*uv 0x4030000000000000 unsigned __int64
g 16.000000000000004 double
*ug 0x4030000000000001 unsigned __int64
v -16.000000000000000 double
*uv 0xc030000000000000 unsigned __int64
g -16.000000000000004 double
*ug 0xc030000000000001 unsigned __int64
Из этого кода видно. Что достаточно представить double числа как unsigned __int64 и сравнить их разницу с единицой.
Есть конечно и исключения, но все они ведут к сравнению с NAN
Вот моя версия функции equal()
typedef unsigned __int64 uint;
bool fast_is_same(double a,double b)
{
switch(*reinterpret_cast<uint*>(&a)-*reinterpret_cast<uint*>(&b))
{
case 1:
case (uint)-1:
return true;
}
return false;
}
Похоже работает.
Интересно другое. Обычно подобную функцию обычно используют тогда, когда результат операции должен быть одним,
а получается немножко другим. Есть ли гарантия что результат различается именно на это значение, а не на большее.
Хотя бы для операций *,+,-,/