Что может быть проще (сложнее), чем упорядочивание чисел?

в 5:24, , рубрики: Программирование
Что может быть проще (сложнее), чем упорядочивание чисел? - 1

Предположим, вы программист и у вас есть два числа. Вы хотите узнать, какое из чисел больше. Если оба числа имеют одинаковый тип, то почти в любом языке программирования решение будет тривиальным. Для этой операции обычно даже есть специальный оператор <=. Вот пример на Python:

>>> "120" <= "1132"
False

Сравнение двух чисел на Brainfuck оставим в качестве упражнения для читателя.

Ой. Ну, строго говоря, это строки, а не числа, а строки обычно сортируются лексикографически. Но это всё-таки числа, хотя и представленные в виде строк. Это может показаться глупым, но такая проблема очень распространена в интерфейсах пользователя, например, в списках файлов. Именно поэтому нужно отбивать числовые имена файлов нулями (frame-00001.png) или использовать описания, сохраняющие лексикографический порядок, например, ISO 8601 для дат.

Впрочем, я отклонился от темы. Предположим, числа действительно представлены числовыми типами. Тогда всё просто и <= отлично работает:

>>> 120 <= 1132
True

Но так ли это?

Сравнения разных целочисленных типов

Что если два сравниваемых числа не имеют одного типа? Первым делом мы можем всё равно попробовать использовать <=. Вот пример на C++:

std::cout << ((-1) <= 1u) << "n";  // Выводит 0.

Ой. C++ автоматически преобразовал -1 в unsigned int, из-за чего значение превратилось в максимальное значение типа (которое очевидно больше 1). Но, по крайней мере, современный компилятор по умолчанию ведь предупреждает о таких вещах?

$ g++ -std=c++20 main.cpp && ./a.out
0

Любопытно было бы прочитать исследование о том, сколько багов возникло из-за сравнения разных целочисленных типов. Не удивился бы, что их довольно много, особенно на C.

Отлично. Ещё одна причина не забывать включать предупреждения (-Wall -pedantic).

Попробуем Rust:

let x: i32 = -1; let y: u32 = 1;
println!("{:?}", x <= y);

error[E0308]: mismatched types
 --> src/main.rs:4:22
  |
4 | println!("{:?}", x <= y);
  |                      ^ expected `i32`, found `u32`
  |
help: you can convert a `u32` to an `i32` and panic if the converted value doesn't fit

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

println!("{:?}", (x as i64) <= (y as i64)); // Выводит true.

Но что если типа, являющегося надмножеством обоих, не существует? По крайней мере, для типов integer это не проблема. Например, в Rust нет типа, являющегося надмножеством i128 и u128. Но мы знаем, что i128 при неотрицательности соответствует u128, а если он отрицателен, то всегда меньше: 

fn less_eq(x: i128, y: u128) -> bool {
    if x <= 0 { true } else { x as u128 <= y }
}

Всё это может вызывать ошибки, да и попросту раздражает. Сравнения между разными типами integer всегда малозатратны, поэтому я не вижу веских причин того, что компилятор не генерирует показанный выше код автоматически. Например, на Apple ARM показанное выше для i64 <= u64 компилируется в три команды:

example::less_eq:
        cmp     x0, #1
        ccmp    x0, x1, #0, ge
        cset    w0, ls
        ret

Компилятор должен сам делать всё правильно, а не заставлять людей выполнять вручную преобразования, которые могут быть и ошибочными, или, хуже того, втихомолку генерировать неверный код. По крайней мере, в C++20 появились новые функции сравнения integer для сравнений между разными типами integer, но обычные операторы сравнения по-прежнему столь же опасны.

Числа с плавающей запятой точны

Прежде чем углубляться в сравнения разных типов с плавающей запятой, надо вкратце вспомнить, что же такое плавающая запятая. Когда я говорю о плавающей запятой, то подразумеваю двоичные числа с плавающей запятой, определяемые стандартом IEEE 754, в частности, binary32 (также известный как f32 или float) и binary64 (также известный как f64 или double). Последняя версия стандарта имеет DOI 10.1109/IEEESTD.2019.8766229.

А вы знали о существовании Sci-Hub? Это важный проект, устраняющий преграды и paywall перед человеческим знанием. Обычно, если у вас есть DOI-ссылка, то документ можно найти всего за пару кликов! (В некоторых юрисдикциях это может быть незаконным.)

Вспомним IEEE 754

Этот формат чисел с плавающей запятой имеет множество странностей, но с большой вероятностью машина, на которой вы читаете мою статью, использует его в качестве нативной реализации floating point. В этом формате число состоит из одного бита знака, $w$ битов экспоненты и $t$ завершающих битов мантиссы. Для f32 $w=8$, а $t=23$, для f64 $w=11, t=52$. Также есть смещение экспоненты $b$, которое равно $127$ для f32 и $1023$ для f64; оно используется для получения отрицательных экспонент.

Чтобы расшифровать число с плавающей запятой (пока забудем о разных NaN и бесконечностях), мы сначала смотрим на $1 + w + t$ битов и декодируем три беззнаковых двоичных целых числа $s$, $e$ и $m$:

Что может быть проще (сложнее), чем упорядочивание чисел? - 14

Тогда если $e=0$, значение числа будет равно

$begin{equation}f={(-1)}^s times 2^{e - b + 1} times (0 + m / 2^t),end{equation}$

а в противном случае

$begin{equation}f={(-1)}^s times 2^{e - b} times (1 + m / 2^t).end{equation}$

Именно поэтому это называется завершающими битами мантиссы: первая цифра мантиссы определяется экспонентой. Когда поле экспоненты равно нулю (до применения смещения), мантисса начинается с $0$, в противном случае она начинается с $1$. Когда мантисса начинается с $0$, это называется денормализованным числом. Они важны, потому что закрывают пробел между нулём и первым числом с плавающей запятой. Хорошенько понять всё это вам помогут эксперименты с приложением Float Toy.

Неточность

После того, как мы с этим разобрались, нужно сказать следующее: типы с плавающей запятой стандарта IEEE 754 определяют множество точных чисел. В них нет никакой двусмысленности (за исключением двух видов нуля, $+0$ и $-0$), как нет и потери точности, нечёткости, интервальных представлений и так далее. Например, $1.0$ точно представлено в f32 значением 0x3f800000, а следующее по величине число f32 — это 0x3f800001 со значением ${(-1)}^0 times 2^0 times (1 + 1 / 2^{23})=1.00000011920928955078125$.

Пример на Rust:

println!("{}", f32::from_bits(0x3f800001));
1.0000001

Ой. Я что, соврал? Нет, лжёт именно Rust:

let full = format!("{:.1000}", f32::from_bits(0x3f800001));
println!("{}", full.trim_end_matches('0'));
1.00000011920928955078125

Это не баг и не случайность. Rust (и, на самом деле, большинство языков программирования) пытается выводить как можно меньше цифр, чтобы гарантировать корректность round-trip. И в самом деле:

println!("0x{:x}", "1.0000001".parse::<f32>().unwrap().to_bits());
0x3f800001

Однако это имеет неприятные последствия, если вы затем парсите число как тип с более высокой точностью:

"1.0000001".parse::<f64>().unwrap() == 1.00000011920928955078125
false

Помните, что значение $1.00000011920928955078125$ точно представимо и в f32, и в f64 (потому что f32 является строгим подмножеством f64), однако мы теряем точность, выводя число как f32 и выполняя его парсинг как f64. Причина в том, что хотя 1.0000001 — это самое короткое десятичное число, которое округляется до $1.00000011920928955078125$ в формате чисел с плавающей запятой f32, в формате f64 оно округляется до $1.0000001000000000583867176828789524734020233154296875$.

Иронично то, что в данном случае было бы точнее выполнить парсинг как f32 и преобразовать значение в f64, потому что Rust гарантирует корректность round-trip:

"1.0000001".parse::<f32>().unwrap() as f64 == 1.00000011920928955078125
true

То есть f32 -> f64 выполняется без потерь, как и f32 -> String -> f32 -> f64. Однако при f32 -> String -> f64 точность теряется.

Для выявления и отладки проблем с плавающей запятой критически важно понять вышеизложенное. При вводе числа в исходном коде языки программирования втихомолку округляют число с плавающей запятой до ближайшего числа, которое можно представить, втихомолку округляют его при парсинге и втихомолку округляют его при выводе. Способы округления в разных языках отличаются, они могут отличаться даже в зависимости от типа.
На каждом этапе пути вам потенциально могут врать.

Учитывая объёмы незаметного округления, я не буду винить вас, если у вас сложилось впечатление о числах с плавающей запятой как о «нечётких». Они создают иллюзию существования типа «вещественного числа». Однако в реальности внутри языка значения являются точным конечным множеством чисел.

Сравнения разных типов с плавающей запятой

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

Прежде чем вы продолжите чтение, предлагаю вам задачу: попробуйте написать корректную реализацию следующей функции:

/// x <= y
fn is_less_eq(x: i64, y: f64) -> bool {
    todo!()
}

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

let x: i64 = 1 << 58;
let y: f64 = x as f64; // 2^58, можно представить в точном виде.
println!("{x} <= {y}: {}", x as f64 <= y);
288230376151711744 <= 288230376151711740: true

Это может показаться плохим сравнением или преобразованием из i64 в f64, но на самом деле это не так. Проблема целиком связана с округлением при форматировании.

Основная сложность заключается в том, что для многих сочетаний типов (например, i64 и f64) в языке программирования не существует нативного типа, являющегося надмножеством обоих. Например, $2^{1000}$ можно точно представить как f64, но не как i64. А $2^{53} + 1$ точно представимо в i64, но не в f64. Поэтому мы не можем просто преобразовать одно в другое и закончить на этом, однако так поступают очень многие люди. На самом деле, это настолько распространено, что даже ChatGPT научился это делать:

Что может быть проще (сложнее), чем упорядочивание чисел? - 30

Бесполезно просить ChatGPT устранить баг с явным контрпримером, он будет болтать какую-то чушь об f64::EPSILON и сравнивать разницу с ним.

Приведённая выше тестовая среда показывает, что проверка x as f64 <= y не проходит, поскольку мы выяснили, что 

9007199254740993 as f64 <= 9007199254740992.0

а это очевидно ошибочно. Проблема в том, что значение 9007199254740993 (то есть $2^{53}+1$) нельзя представить в f64 и оно округляется до $2^{53}$, после чего сравнение выполняется успешно.

Корректная реализация i64 <= f64

Чтобы реализовать $i leq f$ корректно, нужно выполнить операцию в целочисленной области определения после округления числа с плавающей запятой до ближайшего целочисленного, поскольку для целочисленного $i$ мы имеем

$i leq f iff i leq lfloor f rfloor$

Нам не нужно беспокоиться о том, что округление числа с плавающей запятой вверх или вниз до ближайшего целого произойдёт неверно и мы пропустим целое число, поскольку для IEEE 754 функции floor / ceil точны. Так происходит потому, что в части числовой прямой, где числа с плавающей запятой IEEE 754 являются дробными, целые числа тоже расположены плотно.

Но нам всё равно стоит беспокоиться о том, что значение с плавающей запятой не соответствует целочисленному типу. К счастью, когда такое происходит, сравнение выполняется тривиально. К несчастью, целочисленные типы имеют другой интервал в положительной и отрицательной областях определения, поэтому всё равно нужно быть немного осмотрительными, особенно потому что мы не можем сравнивать с $2^{63} - 1$ (максимальное значение i64) в области определения с плавающей запятой.

fn is_less_eq(x: i64, y: f64) -> bool {
    if y.is_nan() { return false; }
    if y >= 9223372036854775808.0 { // 2^63
        true // y всегда больше.
    } else if y >= -9223372036854775808.0 { // -2^63
        x <= y.floor() as i64  // y находится в [-2^63, 2^63)
    } else {
        false // y всегда меньше.
    }
}

Возможно, вы подумаете, что можно обойтись без floor, поскольку сразу после него мы выполняем преобразование в целое число. Увы, as i64 выполняет округление в сторону нуля, но нам нужно выполнять в сторону отрицательной бесконечности, в противном случае мы заявим, что -1 <= -1.5.

Обобщение

Отлично, мы можем выполнять сравнение $i leq f$. А как насчёт $i geq f$? Мы не можем снова использовать ту же реализацию, поменяв порядок аргументов, поскольку их типы различаются. Однако мы можем создать новую реализацию с нуля, применив тот же принцип; при этом придётся использовать ceil вместо floor:

$i geq f iff i geq lceil f rceil$

fn is_greater_eq(x: i64, y: f64) -> bool {
    if y.is_nan() { return false; }
    if y >= 9223372036854775808.0 { // 2^63
        false // y всегда больше.
    } else if y >= -9223372036854775808.0 { // -2^63
        x >= y.ceil() as i64  // y находится в [-2^63, 2^63)
    } else {
        true // y всегда меньше.
    }
}

Но что если мы хотим строгого неравенства? Теперь наш трюк с floor/ceil добавляет проблемы, связанные с равенством. Решить их можно отдельной проверкой на равенство в области определения целых чисел, а затем проверкой на неравенство в области определения чисел с плавающей запятой:

fn is_less(x: i64, y: f64) -> bool {
    if y.is_nan() { return false; }
    if y >= 9223372036854775808.0 { // 2^63
        true
    } else if y >= -9223372036854775808.0 { // -2^63
        let yf = y.floor(); // y находится в [-2^63, 2^63)
        let yfi = yf as i64;
        x < yfi || x == yfi && yf < y
    } else {
        false
    }
}

Принцип понятен. Возможно, есть более умные и/или эффективные способы решения задачи, но, по крайней мере, этот работает.

Заключение

Итак, насколько сложным может быть упорядочивание чисел? Я бы сказал, что довольно-таки сложным, если язык, с которым вы работаете, не поддерживает его нативно. Судя по тому, как разные люди решали задачу корректной реализации is_less_eq, никто не может сделать это правильно с первой попытки. И это после того, как им чётко сказали, что сложность в том, чтобы сделать это корректно для всех входных данных. Цитата из стандартной библиотеки Python: «сравнение — это настоящий кошмар».

Из всех рассмотренных мной языков с чётким разделением на типы целых чисел и чисел с плавающей запятой это правильно реализовано в Python, Julia, Ruby и Go. Отличная работа! Некоторые языки по умолчанию предупреждают или просто не разрешают выполнять сравнения между разными типами, однако, например, Kotlin просто говорит, что 9007199254740993 <= 9007199254740992.0 является true.

Я создал для Rust крейт num-ord, позволяющий корректно сравнивать два любых встроенных числовых типа. Но мне бы хотелось, чтобы в этом и других языках всё делалось правильно нативно. Потому что если этого не будет, то людям придётся решать такую задачу самостоятельно, на что они чаще всего неспособны.

Автор:
PatientZero

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js