Нахождение максимума счетчика с плавающей точкой - PullRequest
Новая
       58

Нахождение максимума счетчика с плавающей точкой

0 голосов
/ 07 ноября 2018

Приношу свои извинения, если об этом уже спрашивали, но я не могу его найти.

Мне было интересно, есть ли способ вычислить точку, в которой число с плавающей запятой одинарной точности, которое используется в качестве счетчика, достигнет «максимума» (точки, в которой оно больше не может добавлять другое значение из-за к потере точности).

Например, если я постоянно добавляю 0.1f к float, я в конечном итоге достигну точки, где значение не изменится: 

const float INCREMENT = 0.1f;
float value = INCREMENT;
float prevVal = 0.0f;

do {
  prevVal = value;
  value += INCREMENT;
} while (value != prevVal);

cout << value << endl;

На GCC это выводит 2.09715e+06

Есть ли способ вычислить это математически для различных значений INCREMENT? Я полагаю, что теоретически это должно быть, когда экспоненциальная часть float требует сдвига за пределы 23 бит, что приводит к потере мантиссы и простому добавлению 0.

Ответы [ 3 ]

0 голосов
/ 07 ноября 2018

С учетом некоторого положительного значения y, используемого в качестве приращения, наименьшее значение X, для которого добавление y не приводит к результату, большему X, является наименьшей степенью 2, равной y, деленной на половину «эпсилон» формата с плавающей точкой. Его можно рассчитать по: 

Float Y = y*2/std::numeric_limits<Float>::epsilon();
int e;
std::frexp(Y, &e);
Float X = std::ldexp(.5, e);
if (X < Y) X *= 2;

Доказательство следует. Я предполагаю, что двоичная арифметика IEEE-754 с плавающей запятой использует округление до ближайшего числа, связанного с четностью.

Когда в арифметике IEEE-754 добавляются два числа, результатом является точный математический результат, округленный до ближайшего представимого значения в выбранном направлении.

Примечание к записи: текст в source code format представляет значения и операции с плавающей точкой. Другой текст математический. Таким образом, x + y является точной математической суммой x и y , x составляет x в Формат с плавающей точкой, и x+y является результатом добавления x и y в операции с плавающей точкой. Также я буду использовать Float для типа с плавающей точкой в ​​C ++.

Учитывая число с плавающей точкой x , рассмотрите возможность добавления положительного значения y , используя арифметику с плавающей точкой, x+y. При каких условиях результат будет превышать x ?

Пусть x 1 будет следующим значением, большим, чем x , представляемым в формате с плавающей запятой, и пусть x m будет средней точкой между x и x 1 . Если математическое значение x + y меньше, чем x m , тогда вычисление с плавающей запятой x+y округляется в меньшую сторону, поэтому он производит x . Если x + y больше, чем x m , либо оно округляется и выдает x 1 , или выдает большее число, потому что y достаточно велико, чтобы переместить сумму за пределы x 1 . Если x + y равно x m , результат будет равен x или x 1 имеет четную младшую цифру. По причинам, которые мы увидим, это всегда x в ситуациях, имеющих отношение к этому вопросу, поэтому расчет округляется вниз.

Следовательно, x+y дает результат, больший чем x тогда и только тогда, когда x + y превышает x m , что означает, что y превышает половину расстояния от x до x 1 . Обратите внимание, что расстояние от x до x 1 - это значение 1 в младшем разряде значенияи x.

В двоичном формате с плавающей точкой с p цифрами в его значении, значение позиции младшей цифры в 2 1− p раз больше позиции значение старшей цифры. Например, если x равно 2 e , старший бит в его значении представляет 2 e , и младший бит представляет 2 e + 1− p .

Вопрос задает, учитывая y , что является наименьшим x , для которого x+y не дает результат, больший чем x ? Это наименьшее значение x , для которого y не превышает половины значения младшего разряда значимого и x.

Пусть 2 e будет значением позиции старшего бита значения и x . Тогда y ≤ ½ • 2 e + 1− p = 2 e - p , т. е. y • 2 p ≤ 2 e .

Поэтому дайn некоторое положительное значение y , наименьшее значение x , для которого x+y не дает результат, больший чем x , имеет старший бит, 2 e , равный или превышающий y • 2 p . И на самом деле это должно быть ровно 2 e , потому что все остальные числа с плавающей запятой, чей старший бит имеет значение позиции 2 e , имеют другие биты установлены в их значениях, поэтому они больше. 2 e - это наименьшее число, для которого старший бит представляет 2 e .

Следовательно, x является наименьшей степенью двойки, равной или превышающей y • 2 p .

В C ++ std::numeric_limits<Float>::epsilon() (из заголовка <limits>) - это шаг от 1 до следующего представимого значения, то есть это 2 1− p . То есть y • 2 p равно y*2/std::numeric_limits<Float>::epsilon(). (Эта операция является точной, если она не переполняется до ∞.)

Давайте присвоим это переменной: 

Float Y = y*2/std::numeric_limits<Float>::epsilon();

Мы можем найти значение позиции, представленное старшим битом значения Y , используя frexp (из заголовка <cmath>), чтобы извлечь показатель степени из представления * с плавающей запятой Y и ldexp (также <cmath>), чтобы применить этот показатель к новому значению и (.5 из-за шкалы, которую frexp и ldexp используют): 

int e;
std::frexp(Y, &e);
Float X = std::ldexp(.5, e);

Тогда X - это степень двойки, и она меньше или равна Y . Это на самом деле наибольшая сила двух, не превышающая Y , поскольку следующая большая сила 2, 2 X , больше Y . Тем не менее, мы хотим наименьшую мощность двух не менее Y . Мы можем найти это с: 

if (X < Y) X *= 2;

Результирующее X - это число, которое ищет вопрос.

0 голосов
/ 07 ноября 2018

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

Из того, что я могу сказать, ответ сводится к показателю степени использованной дельты и количеству битов мантиссы. Нам нужно округлить до ближайшей степени 2, что довольно сложно. В основном, если мантисса равна 0, мы ничего не делаем, в противном случае мы добавляем 1 к показателю степени. Итак, предполагая, что теперь у нас есть дельта как степень 2, представленная как 1.0 x 2<sup>exp</sup>, и мантисса из N битов, максимальное значение равно 1.0 x 2<sup>(N + exp)</sup>. Обратите внимание, что FLT_EPSILON в C равно 1.0 x 2<sup>-N</sup>. Таким образом, мы также можем найти это, разделив ближайшую степень 2 на FLT_EPSILON.

Для дельты 0,1 ближайшая степень 2 равна 0,125 или 1.0 x 2<sup>-3</sup>. Поэтому мы хотим 1.0 x 2<sup>(23 + (-3))</sup> или 1.0 x 2<sup>21</sup>, что равно 2097152.

0 голосов
/ 07 ноября 2018

Да, это возможно. std :: numeric_limits :: epsilon () определяет наименьшее значение, которое может увеличить значение 1.0.

Используя это, вы можете рассчитать этот предел для любого числа.

В C есть DBL_EPSILON

Итак, в вашем случае это выглядит так: 

template<class T>
auto maximumWhenAdding(T delta) -> T
{
    static_assert(std::is_floating_point_v<T>, "Works only for floating points.");
    int power2= std::ilogb(delta);
    float roudedDelta = ldexp(T { 1.0 }, power2);
    if (roudedDelta != delta) {
        roudedDelta *= 2;
    }

    return 2 * roudedDelta / std::numeric_limits<T>::epsilon();
}

живой пример C ++

Примечание в примерах живого теста delta не может увеличиться maxForDelta, но вычитание прошло успешно, так что это именно то, что вам нужно.

...