Возможно ли переполнение при вычитании в компараторе?

#javascript #алгоритм #сортировка #любой_язык #переполнение

Рассмотрим сортировку, у которой в компараторе в качестве результата используется
разность сравниваемых элементов

a.sort((x, y) => x-y)


Очевидно, что при целочисленных типах данных этот алгоритм подвержен переполнению,
приводящему к неверному результату. Такой пример довольно лекго составить:



console.log([1<<31, 1].sort((x, y) => x-y|0))




А как насчёт вещественных чисел? Подвержены ли они проблеме переполнения?

Я могу придумать пример, где разность двух Infinity даёт NaN, но не могу придумать
ситуацию, в которой это бы сказалось на сортировке - ведь все бесконечности равны,
а разности с другими значениями поставят их на нужное место.



console.log([Infinity, 1, -Infinity, Infinity].sort((x, y) => x-y))



    

Ответы

Ответ 1

Представление целых чисел со знаком имеет зацикленную структуру за счет использования
"дополнительного кода" для представления отрицательных значений. Это и является причиной
того, что выполняя вроде бы обычное сложение двух целых чисел можно получить отрицательное
число, если нет контроля переполнений, тоже касается сложения двух отрицательных.

В представлении вещественных чисел (IEEE 754) цикличность отсутствует, знак числа
хранится отдельным битом. Зато присутствует два нуля (+0, -0), собственно чтобы их
не было и вводили дополнительный код в представлении целых. Переполнение мантиссы не
возможно, т.к. из мантиссы вытесняются лишние младшие биты после вычисления порядка
результата. Порядок хранится как целое без знака и его максимальное значение обрабатывается
особым образом, поэтому вместо переполнения получаются либо бесконечности, либо NaN.

Таким образом сам формат вещественных чисел (IEEE 754) не допускает ошибки переполнения
при выполнении стандартных арифметических операций.


Ответ 2

Если для сортировки массива чисел с плавающей точкой использовать компаратор наподобие
следующего (здесь и далее все примеры на C++):

bool Compare(const double &a, const double &b)
{
    return a - b > 0.0;
}


то проблемы возникнуть могут.



Во-первых, массив исходных данных может содержать "нечисла" (Not-a-Number, NaN).
NaN является неупорядоченным (unordered) по отношению к любым другим числам с плавающей
точкой, включая самого себя. Это означает, что если по крайней мере один операнд бинарных
операторов <, <=, ==, >=, > — NaN, то результат сравнения false; если по крайней мере
один из операндов бинарного оператора != — NaN, то результат сравнения true (стоит
заметить, что согласно стандарту вычислений с плавающей точкой IEEE 754-2008, операторы
сравнения могут генерировать исключение в случае, если по крайней мере один из операндов —
NaN). 

NaN также характеризуется особой арифметикой. Например, если по крайней мере один
из операндов бинарного - — NaN, то результат NaN.

Такие свойства NaN'ов в совокупности с представленным выше компаратором могут отрицательно
сказаться на результатах сортировки. Для примера рассмотрим сортировку вставками (Пример):

void InsertionSort(vector &vect)
{
    for (size_t i = 1; i < vect.size(); ++i)
        for (size_t j = i; j > 0 && Compare(vect[j], vect[j - 1]); --j)
            swap(vect[j], vect[j - 1]);
}


Ни один элемент массива {1.0, NaN, 2.0, NaN, 1.0} после такой сортировки не будет
перемещён. На каждой итерации цикла i при помощи функции Compare будет сравниваться
пара чисел с плавающей точкой. И каждый раз в этой паре будет присутствовать NaN. И
каждый раз результат сравнения будет false, а значит не будет произведено ни одного
обмена элементов вектора.



Второй пример связан с денормализованными (субнормальными) числами.

Если бы удалось подобрать два таких числа a и b, что a > b, но a - b == 0, то возникли
бы проблемы с сортировкой. Ведь a больше b, но компаратор говорит, что a не больше
b, а значит алгоритм сортировки не обязан менять числа a и b местами.

Википедия говорит, что в формате  IEEE 754-2008 разность двух неравных, но близких
друг к другу чисел, не бывает равна нулю. И обеспечивается это, отчасти, благодаря
денормализованным числам.

Взглянем повнимательнее на числа с плавающей точкой двойной точности. А именно на
минимальное положительное нормализованное число (min), число следующее непосредственно
за предыдущим (в сторону единицы, min_1), разность двух предыдущих (diff = min_1 -
min) и минимальное положительное денормализованное число (denorm_min):

min        == 2.22507385850720138e-308
min_1      == 2.22507385850720188e-308
diff       == 4.94065645841246544e-324
denorm_min == 4.94065645841246544e-324


Можно заметить, что разность двух нормализованных чисел представляет собой денормализованное
значение.

Некоторые процессоры (в частности, с поддержкой SSE2), позволяют сбрасывать до нуля
(flush to zero) результат арифметического выражения, если он денормализованный. Т.е.
в данном конкретном случае, разность двух нормализованных, неравных чисел min и min_1
вполне может получится равной нулю, а значит можно сконструировать пример некорректной
сортировки.

Воспользуемся Visual Studio, функцией _controlfp_s и напишем небольшой пример:

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#pragma fenv_access (on)

bool Compare(const double &a, const double &b)
{
    return a - b > 0.0;
}

int main()
{
    double min = numeric_limits::min();
    double min_1 = nextafter(min, 1.0);

    vector v = {min, min_1, min, 1.0, 2.0};
    _controlfp_s(nullptr, _DN_FLUSH, _MCW_DN);
    sort(v.begin(), v.end(), Compare);
    for (auto val : v)
        cout << val << " ";
    cout << endl;
}


Вектор до сортировки:
2.22507385850720138e-308 2.22507385850720188e-308 2.22507385850720138e-308 1.0 2.0

Вектор после сортировки:
2.0 1.0 2.22507385850720138e-308 2.22507385850720188e-308 2.22507385850720138e-308

Хоть пример довольно таки надуманный, но не невозможный на практике (особенно с учетом
того, что судя по документации, некоторые компиляторы по-умолчанию включают опцию flush
to zero на всех уровнях оптимизации, больших чем -O0).