Быстро определить epsilon для float/double
От: McSeem2 США http://www.antigrain.com
Дата: 04.02.06 15:53
Оценка:
Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. Обычно делается методом деления пополам:

double a = 1e10;
double epsilon = a;
while((a + epsilon/2) != a) epsilon /= 2;


Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: Быстро определить epsilon для float/double
От: WolfHound  
Дата: 04.02.06 18:58
Оценка: 11 (1)
Здравствуйте, 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) А. Эйнштейн
Re[2]: Быстро определить epsilon для float/double
От: McSeem2 США http://www.antigrain.com
Дата: 04.02.06 20:35
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>
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
Я жертва цепи несчастных случайностей. Как и все мы.
Re[3]: Быстро определить epsilon для float/double
От: WolfHound  
Дата: 04.02.06 21:37
Оценка:
Здравствуйте, 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) А. Эйнштейн
Re[4]: Быстро определить epsilon для float/double
От: FedorovStanislav  
Дата: 04.02.06 22:01
Оценка:
Здравствуйте, 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, то не выйдет.
Re[5]: Быстро определить epsilon для float/double
От: McSeem2 США http://www.antigrain.com
Дата: 05.02.06 18:49
Оценка:
Здравствуйте, FedorovStanislav, Вы писали:

FS>Не согласен с обоими в этом вопросе. Так говорят только те, кто не понимает сути дела. Что показывает epsilon?

FS>Вообще epsilon определяется всегда относительно единицы. Если хотите получить его относительно другого числа, то:
FS>1 + epsilon != 1
FS>a + a*epsilon != a

Ну, а я о чем говорил?

MS>Но идея правильная — надо поделить (или умножить) число на некую константу.


Вот эта константа и есть epsilon (ну или 1/epsilon)
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re: Быстро определить epsilon для float/double
От: LelicDsp Россия  
Дата: 06.02.06 16:14
Оценка:
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, или об известном хотя бы, то нужно взять описание формата и посмотреть сколько там бит на мантиссу и как нормализуются числа.
Re: Быстро определить epsilon для float/double
От: korzhik Россия  
Дата: 06.02.06 16:24
Оценка:
Здравствуйте, 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)?
Re[2]: Быстро определить epsilon для float/double
От: McSeem2 США http://www.antigrain.com
Дата: 06.02.06 17:00
Оценка:
Здравствуйте, korzhik, Вы писали:

K>Наверно я сильно туплю, но очень интересно... может кто нибудь объяснить почему не подходит просто FLT_EPSILON (DBL_EPSILON)?


Все уже выяснили. Именно ее и надо брать, но домножать на само число. Значение выражения "(1.0+DBL_EPSILON)>1.0" равно true. А вот "(1000000.0+DBL_EPSILON)>1000000.0" уже будет false. Для значения в миллион надо брать миллион эпсилонов
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[3]: Быстро определить epsilon для float/double
От: LelicDsp Россия  
Дата: 06.02.06 17:02
Оценка:
K>>Наверно я сильно туплю, но очень интересно... может кто нибудь объяснить почему не подходит просто FLT_EPSILON (DBL_EPSILON)?
MS>Все уже выяснили. Именно ее и надо брать, но домножать на само число. Значение выражения "(1.0+DBL_EPSILON)>1.0" равно true. А вот "(1000000.0+DBL_EPSILON)>1000000.0" уже будет false. Для значения в миллион надо брать миллион эпсилонов

Ну если совсем точно, то не на число наверное, а на его экспоненту?
Re[4]: Быстро определить epsilon для float/double
От: FedorovStanislav  
Дата: 06.02.06 20:45
Оценка:
Здравствуйте, 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
Re[5]: Быстро определить epsilon для float/double
От: LelicDsp Россия  
Дата: 07.02.06 08:04
Оценка:
LD>>Ну если совсем точно, то не на число наверное, а на его экспоненту?
FS>Почему: a + a*epsilon <> a

Ну возьмем стандартный флоат, у него мантисса 23 бита. Рассмотрим нормализованное число

1.0000000000000000000000b*exp для него epsilon равен 0.0000000000000000000001b*exp, где exp- экспонента числа.
Но для числа 1.1000000000000000000000b*exp epsilon тоже равен 0.0000000000000000000001b*exp.
Re: Так чем всё закончилось?
От: Шебеко Евгений  
Дата: 09.02.06 08:54
Оценка:
MS>Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. Обычно делается методом деления пополам:

MS>Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?


Самого проблема очень интерисует.
Только не врубился к какому мнению (коду) господа пришли ?
Объясните плиз. дураку
Re[2]: Так чем всё закончилось?
От: nut888 Россия  
Дата: 09.02.06 09:24
Оценка:
Здравствуйте, Шебеко Евгений, Вы писали:

MS>>Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения. Обычно делается методом деления пополам:


MS>>Но это очень долго. Проблема в том, что брать просто константу в моем случае нехорошо — значение epsilon зависит от самого числа. Нет ли какого быстрого хака?


ШЕ> Самого проблема очень интерисует.

ШЕ> Только не врубился к какому мнению (коду) господа пришли ?
ШЕ> Объясните плиз. дураку

В STL все это уже есть
смотри файл limits


#include <limits>
std::numeric_limits<double>::epsilon()
Re[3]: Так чем всё закончилось?
От: Аноним  
Дата: 09.02.06 10:29
Оценка:
MS>>>Требуется быстро определить минимальное значение float или double, прибавление которого к числу все еще меняет его значение. Фактически, это означает погрешность для данного значения.
N>В STL все это уже есть
N>смотри файл limits
N>#include <limits>
N>std::numeric_limits<double>::epsilon()

Если бы. Смотри внимательно постановку задачи и обсуждение.
Re[2]: Так чем всё закончилось?
От: McSeem2 США http://www.antigrain.com
Дата: 09.02.06 15:55
Оценка:
Здравствуйте, Шебеко Евгений, Вы писали:

ШЕ> Самого проблема очень интерисует.

ШЕ> Только не врубился к какому мнению (коду) господа пришли ?
ШЕ> Объясните плиз. дураку

a += a * DBL_EPSILON должно по идее гарантированно изменить значение a на минимально возможную величину.
Просто a += DBL_EPSION — это не правильно, поскольку DBL_EPSILON (ну или FLT_EPSILON) вычислена для единицы. Для doudle она примерно 2.22e-16. Понятно, что для Планковских масштабов она сама по себе не катит — очень грубо. А для величин больше 10 (не говоря уже о космических масштабах) прибавление этой epsilon вообще не повлияет на значение.

Но как как абсолютно достоверно сравнить два числа на равенство, когда шум допустим только в последнем разряде? То есть, когда два числа различаются на минимально возможную величину? По идее надо:
if(fabs(a-b) <= DBL_EPSILON * max(fabs(a), fabs(b)))
{
   ...equal
}


Но это же сколько лишнего! Не проще ли неким хаком занулить последний разряд мантиссы и потом сравнивать на строгое равенство? Что-то мне подсказывает, что так делать категорически нельзя. То есть, в большинстве случаев работать будет, но раз в год выстрелит не туда.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Re[6]: Быстро определить epsilon для float/double
От: Eduard-x Германия www.ruforum.de
Дата: 12.02.06 21:01
Оценка:
Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, FedorovStanislav, Вы писали:


FS>>Не согласен с обоими в этом вопросе. Так говорят только те, кто не понимает сути дела. Что показывает epsilon?

FS>>Вообще epsilon определяется всегда относительно единицы. Если хотите получить его относительно другого числа, то:
FS>>1 + epsilon != 1
FS>>a + a*epsilon != a

MS>Ну, а я о чем говорил?


MS>>Но идея правильная — надо поделить (или умножить) число на некую константу.


MS>Вот эта константа и есть epsilon (ну или 1/epsilon)


можно также заменить операцию деления на операцию умножения

epsilon/2 -> epsilon*0.5
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: Так чем всё закончилось?
От: Шебеко Евгений  
Дата: 19.02.06 19:06
Оценка: 15 (1)
MS>
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>if(fabs(a-b) <= DBL_EPSILON * max(fabs(a), fabs(b)))
MS>{
MS>   ...equal
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



typedef unsigned __int64 uint;
void f(double v)
{
    v=v;
    uint* uv=(uint*)&v;

    double g=v;
    uint* ug=(uint*)&g;
    ++*ug;
    ug=ug;
}

int main(int argc, char** argv)
{
    f(1.0);
    f(std::numeric_limits<double>::epsilon());
    f(16.0);
    f(-16.0);
    f(-std::numeric_limits<double>::infinity());
}




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


Похоже работает.
Интересно другое. Обычно подобную функцию обычно используют тогда, когда результат операции должен быть одним,
а получается немножко другим. Есть ли гарантия что результат различается именно на это значение, а не на большее.
Хотя бы для операций *,+,-,/
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.