Плаваюча (рухома) крапка, частина 6: Порівняння
Читайте також:
— Плаваюча (рухома) крапка. Частини
— Плаваюча (рухома) крапка. Частина 3: Сучасний стандарт і все навколо — основи.
— Плаваюча (рухома) крапка. Частина 4: Сучасний стандарт — тонкі деталі і проблеми
— Плаваюча (рухома) крапка. Частина 5: Текстовий експорт-імпорт
— Плаваюча (рухома) крапка. Частина 7: десяткова рухома крапка
Четвертий результат порівняння, і як з ним боротись
Як вже згадувалось в частині 4 в розділі про NaN (не-число), вибраний за стандартом шлях визначає, що NaN принципово не дорівнює нічому, в тому числі будь-якому NaN. (Звідси ідіома перевірки на NaN: a != a. Її не можна згорнути до false, як би комусь не хотілось.)
З цілими числами ми мали просте правило, що завжди одно з трьох виконується: A < B, A = B, або ж A > B; тому запереченням для A < B буде A ⩾ B, і навпаки. Але якщо можливий четвертий варіант (позначимо unordered як ⟂), то ці інтуїтивно зрозумілі принципи перестають працювати.
До чого це приводить? Звернімось до математики. «Відношення порядку» визначається як підмножина добутку множини визначення на себе ж; зазвичай позначають «aRb», якщо (a,b) належить до такої підмножини; можна подумки інтерпретувати в стилі «a⩽b», підставляючи потрібний знак замість цього R. Зручніше всього визначати звичний тип порівняння через «антисиметричне» і «транзитивне» відношення, при якому 1) якщо aRb і a≢b, то не bRa; 2) якщо aRb і bRc, то aRc; 3) якщо aRa для будь-якого a, то це «менше або дорівнює», а якщо не aRa для будь-якого a, то це «строго менше». Якщо для будь-яких a, b, a≢b буде або aRb, або bRa, то це лінійне відношення, тобто таке, що дає можливість вишикувати всі значення у лінійний ряд зростаючих (чи неспадаючих) значень. (Я не хочу тут давати посилання на вікіпедію, бо відповідна стаття зараз неповна і невірна. Взагалі, є дуже багато чого доробляти в українському розділі.)
Саме лінійність тут страждатиме з NaN. Скінченні числа і нескінченність будь-якого знаку тут можна вишикати в один ряд (говорячи мовою IT, відсортувати), а це критично для широкого ряду застосувань. Наявність непорівнюваних (unordered) значень збиває з пантелику і ускладнює обробку даних: NaN-и стоять осторонь всього. Формально ми після цього не маємо права сортувати такі обʼєкти плаваючої крапки (або що завгодно, якщо ключ сортування зводиться до такого обʼєкта), створювати структури типа впорядкованого дерева (RB, AVL, B/B⁺/etc.), використовувати їх в індексі для бази даних... 😢
В мовах C, C++ проблему іґнорують: і порівняння не має специфіки, і sort() на floatʼах будь-якої точности дозволений. Кожен може спробувати сортування масиву, в якому рандомно накидана якась частка NaNʼів, не міняючи функцію порівняння: NaN-и будуть більш-менш рівномірно розподілені в вихідному масиві. Що цікаво, всі інші значення будуть коректно упорядковані; я не зміг знайти прикладу з реальним кодом і реальними бібліотеками рантайму, коли присутність NaN доводила б до псування порядку між іншими значеннями.
Але цей підхід таки не зовсім коректний (мʼяко кажучи), коли треба дійсно розділити різні значення ключа так, щоб обʼєкти з одним ключем виявились поряд. Ця вимога критична для ефективного пошуку по масиву або дереву (а інакше взагалі для чого б було потрібне сортування?) Тому краще у випадку, коли NaN може зʼявлятись у таких даних, зробити спеціальну обробку, назначивши їм або щоб були менше будь-якого реального значення, або більше. Функція порівняння у такому випадку може виглядати, наприклад, так (робимо NaN менше ніж -∞):
int cmp(float a, float b) // -1 if a < b, +1 if a > b
{
bool a_is_nan = a != a;
bool b_is_nan = b != b;
if (a_is_nan || b_is_nan) {
return (int)b_is_nan - (int)a_is_nan;
}
return (a > b) ? 1 : -(int)(a < b);
}
Ті, хто знає SQL, може порівняти з опціями «NULLS FIRST», «NULLS LAST» в сортуванні (ORDER BY) в виразах виборки даних; нічого дивного, бо плавучий NaN і SQLʼевський NULL це принципово одне і те ж для відповідної внутрішньої лоґіки.
А ось в Rust ви взагалі не зможете передати масив floatʼів (f32, f64) в sort() без хитрощів, бо останній вимагає, щоб був реалізований типаж (trait) Ord для даних, що сортуються — а він для f32, f64 навмисно пропущений, бо описує вимогу лінійного порядку на множині значень (а для часткового є PartialOrd, саме він імплементований для f32 і f64).
Тобто, такий код не спрацює:
let mut floats = vec![1.0, 2.0, 3.0]; floats.sort();
компілятор вилається:
error[E0277]: the trait bound `{float}: Ord` is not satisfied
--> src/main.rs:3:12
|
3 | floats.sort();
| ^^^^ the trait `Ord` is not implemented for `{float}`
Хочете зробити сортування — викликайте не sort, а sort_by зі своєю функцією, наприклад в стилі, як зроблено вище з виносом всіх NaN окремо — або заміняєте на тополоґічне сортування (значно дорожче):
floats.sort_by(|a, b| a.partial_cmp(b).unwrap());
Або викликайте total_cmp(), але тоді будьте готові, що -NaN менше всіх значень, а +NaN більше; далі буде про цей вид порівняння.
В Java спеціально для float и double стандартний Arrays.sort має функцію порівняння, коли будь-який NaN більше реальних чисел (реально, воно викликає Double.compareTo, в який безваріантно зашили цю лоґіку). Теж крок у цьому напрямі. (Але мені не до вподоби те, що це лоґіка compareTo завмовчки, назва збиває. Мабуть, вони тоді не знайшли кращого рішення в умовах обмеженого ресурсу.)
А ще треба згадати, що заміна a ⩾ b на a — b ⩾ 0 майже всюди коректна, бо при переповненні діапазону значень отримуємо +Inf з потрібним знаком... але якщо обидва вже були Inf, то a == b, але a — b буде NaN. Те, що ми могли робити з цілими числами, знов не збігається з тим, що з float.
Ще про четвертий результат: три види порівняння
Через вказані проблеми, що якщо a = NaN, то всі три a < b, a == b, a > b є false — треба доробляти поняття порівняння. Одним простим вже не обійтись.
IEEE754 для всіх операцій порівнянь вводить три різновиди: несиґналізуючий (non-signaling), сиґналізуючий (signaling) і повний (total).
Ті, що не total, ведуть себе саме як показано в попередньому розділі як дефолтний варіант: відношення не лінійне. Але, крім того, зроблено, що signaling варіант ще підіймає флаґ помилки «Invalid operation», якщо хоча б з одного боку був будь-який NaN. Non-signaling варіант обмежує ці вимоги до signaling NaN; quiet NaN не викликає підняття флаґу помилки. (В деяких джерелах вони відповідно називались ordered і unordered; проте в прикладі нижче для CMPP команд SSE unordered це порівняння з ґенерацією True при хоча б одному NaN. Ці терміни конфліктні і такого вживання треба уникати.)
Якщо у вас нема можливости задавати тип порівняння, то будьте впевнені, що:
- «дорівнює» і «не дорівнює» будуть non-signaling (NaN не підіймає Invalid Operation), а
- "менше"/"більше«, включаючи «або дорівнює» — signaling.
Але є місця, де дозволяється реґулювати тип порівняння за межами цього прокрустова ліжка.
Третій тип порівняння — total — має суттєво іншу лоґіку. Для звичайних чисел (від нуля до нескінченности, з будь-яким знаком) він працює точно так же як перші два, з поправкою, що —0 менше, ніж +0. Всі додатні NaN більші, ніж плюс нескінченність, а відʼємні — менші, ніж мінус нескінченність. NaN одного знаку порівнюються по payload-у, тому може бути, що якщо a, b, c всі три NaN, то a = b, але a ≠ c і b ≠ c.
В багатьох мовах ще немає штатних засобів отримати тотальне порівняння. Його введення, де наявне, це вже нові доробки від тих, хто виріс з розумінням нових особливостей. Для Rust було згадано раніше.
Із дивного але показового — порівняння в x86 SSE ([V]CMPP{S,D}) спочатку мало 8 варіантів, включаючи non-signaling для = і ≠, і signaling для < ⩽ > ⩾, а потім були додані альтернативні варіанти; це видно по дозволеним значенням для першого покоління версій команд, і по розкладу значень константи режима порівняння. Там також варіанти порівняння, які дають True при NaN хоча б з одної сторони, названі ordered. Всього є 32 варіанти з 5 окремих біт (4 на випадки: a < b, a = b, a > b, a ⟂ b; і один на signaling у випадку qNaN). Здається, це максимум, як можна сформувати варіанти операції порівняння без зовсім вже сово-ґлобусових страждань... і що, як ці 32 порівняти з 6 варіантами порівняння (мимовільний каламбур) для цілих?
Перетворення для порівняння не як float-тип
І таке існує, і може використовуватись як для порівняння у реалізаціях, де не можуть втілю+вати саме операції порівняння як типу з рухомою крапкою. Це може бути де завгодно, але головний випадок — як ключ (частина ключа) в базі даних. Про бази даних буде окрема частина, але тут нам достатньо того, що такий ключ у переважній їх більшости формується як рядок байт, де числові типи перетворюються на відрізок фіксованої довжини.
Таке перетворення має відповідати якомусь зі вказаних вище упорядкувань, але різниця між signaling і non-signaling стирається і залишається лише різниця між ними і total упорядкуванням. Може бути додане ущільнення різних NaN в єдине значення.
Для двійкових форматів перетворення дуже просте і описується так:
1) Згідно з місцевими правилами перетворюємо, або ні, різні NaN. Можемо у єдине значення на всіх, можемо залишити як є.
2) Значення —0.0 заміняємо на +0.0.
3) Беремо представлення у конкретному форматі з таких, що відповідають IEEE754. Якщо число невідʼємне (знак плюс), найстарший біт замінюємо на 1. У протилежному випадку (знак мінус) інвертуємо всі біти представлення.
4) Отримане представлення використовуємо як рядок байт (або можна проінтерпретувати як ціле число без знаку). Не забувати про порядок байт: для такої задачі треба big-endian, тому на little-endian платформах треба розвернути порядок на протилежний.
Знаючи принципи представлення стандартних форматів IEEE754, легко зрозуміти, що діапазон значень -∞...-0.0...+0.0...+∞ таким чином перетвориться на послідовність вихідних цілих без знаку, що і було потрібне для формування ключа чи його частини.
Забігаючи вперед: для десяткових форматів так легко не вийде: і перетворення значно більш складні, і зберігти довжину значення для такого сортування не вдасться (треба додати, щонайменше, три біти).
Точні і неточні порівняння
Дуже багато звідки можна чути, що порівняння двох плаваючих значень на рівність некоректне у принципі, і його треба заміняти на порівняння з урахуванням деякого діапазону похибки. Чи це так?
Ідея, що стоїть за цим твердженням, вірна за суттю. Якщо похибки обчислень можливі в принципі, і число для порівняння неминуче буде з похибкою (а може і друге буде з похибкою), то треба не порівнювати з конкретним бажаним числом, а шукати відповідність деякому діапазону навкруги того бажаного числа. Від основи це не залежить, для 2, 10, і інших принцип тут одинаковий (проте, для 10 сам такий тип обчислень дуже нечастий на практиці, тому рідше можна зустріти).
І це стосується не тільки порівняння на рівність; нерівність теж може мати неочікуваний результат. Приклади з одної сторінки:
>>> 0.1 + 0.2 <= 0.3 False >>> 10.4 + 20.8 > 31.2 True >>> 0.8 - 0.1 > 0.7 True
І знову, як хтось уже здогадався, дивимось на деталі.
Точне порівняння можливе, якщо число вийшло з цілого і без реального округлення. Це завжди робиться, наприклад, в JavaScript, де цілі завмовчки представлені тим же number. Значення 2, яке є цілим числом за походженням, чи варіантом enum-а, не вимагає порівнювання на потрапляння в діапазон від 1.999 до 2.001. Для людини це очевидно, здається, можна було б не вказувати — але для проґрамного лінтера це треба розуміти явно. Якщо лінтер для JavaScript не зрозуміє, що в «a == 2» це «a» може бути тільки цілим, то ви отримаєте 100500 хибнопозитивних спрацювань. Що там роблять сучасні лінтери і як вони розрізняють такі ситуації?
Але в прикладі з частини 1 з циклом з кроком 0.1 — якийсь діапазон потрібний. Звісно, якщо зберігати цей підхід у базі (ой не рекомендую). Можемо знову послатись на приклад з 0.1×3. Ви чекаєте, що він дорівнюватиме 0.3, і порівнюєте на рівність (чи на нерівність)... а всьго-навсього 1 ULP робить цю мрію безнадійною. Все так?
Обмежимо з протилежного боку: чи бувають ще випадки, де точна перевірка на рівність не просто дозволена, а ще й єдино вірна?
Якщо це домен, де похибка не дозволена умовами (див. наступну частину 7 про фінанси і десяткову плаваючу кому), то можемо порівнювати без урахування похибки.
Наступний код я отримав з Gemini, коли спитав його (див. частину 4), як в Java зробити округлення до цілого за half-to-even. На жаль, «підкату» тут немає, тому скорочу до максимуму, хоча шкода його коментарів:
public static int roundHalfToEven(float f) {
int rounded = Math.round(f); // half-ceil, маячня якась
if (Math.abs(f - rounded) == 0.5f) {
if (rounded % 2 != 0) {
return rounded - 1;
}
}
return rounded;
}
(Ну тут «%2» можна було б замінити на «&1», хоча JIT, я впевнений, і так це зробить.) Головне, що корекція має застосовуватись тільки при рівно 0.5.
Особливий приклад? Да. Штучний? Ні, я впевнений, що багато проґрам має саме таку функцію.
Або ми міряємо... як раз похибку (буде далі). Встановили, наприклад, що абсолютна похибка до 1e-6 (0.000001) нас влаштовує. Якщо ми порівнюватимемо різницю двох значень знову з можливістю похибки... прийдемо до: «Рекурсія — див. Рекурсія» (стаття зі словника). Тобто і тут вже не можна так чинити. Якщо б була мова з дуже сильною типізацією (і без зайвих витрат на це), можна було б ввести два типи: назвати на зразок «inexact_float» і «exact_float», inexact_float приймати з обчислень, що можуть давати похибку, і забороняти пряме порівняння inexact_float. Але я такого ще не бачив на практиці, поки тільки ручний (зоровий) контроль.
Ще згадаймо тут число як ключ до мапи. Звісно, у нормальних умовах так не роблять. Але якщо треба, і значення коректно канонікалізовані — то, під пильним контролем лікаря, таки можна:))
Ще один варіант — strict CBOR (трохи детальніше буде в частині 10). Для пошуку мінімального представлення числа конвертуємо його з float64 в float32 і далі в float16, а якщо нема доступу до флаґу Inexact, то точність перетворення можна визначити тільки зворотнім розширенням формату і порівнянням на точне рівняння.
Тобто «в усьому потрібні міра, норма і межа» (™).
Коли ми відкинули всі неадекватні випадки, можна почати шукати адекватні. Фактично, в якому випадку потрібне порівняння на приблизну рівність, чи нерівність з запасом; і, якщо потрібно, як саме його виконувати? Вже тут виникає проблема: яке з чисел вважати точним, а яке — ні?
тут і далі — якщо віднімання коректне (нагадую: Inf = Inf, але Inf — Inf дасть NaN); як рахувати eps — буде далі (на жаль, без деталей конкретної ситуації тільки основи).
a = b -> b — eps < a < b + eps, або: a — eps < b < a + eps; можна просто сказати: abs(a — b) < eps.
Порівняння a < b і a ⩽ b становляться одним і тим же, якщо ми вводимо допоміжний eps ґарантованого проміжку (тут уже розділяти випадки <eps і ⩽eps немає ніякого сенсу).
a < b -> a < b — eps, або a + eps < b, тобто нам треба ґарантований вихід за межі околиці числа b? Зазвичай, так. Але подивимось з іншого боку: якщо нема проблеми що a ⟂ b, то це заперечення для a ⩾ b. Тобто, заперечуємо a — eps > b (або a > b + eps)? Оскільки у даному контексті у нас запереченням a > b може бути і a < b, і a ⩽ b, то заперечення заперечення перетворюється на умову a — eps < b. А почали ми з a + eps < b. Так як вірно? ;) А це залежить таки від того, ми хочемо ствердження чи заперечення умови — відповідно ми повинні її підсилити в одному з напрямків.
Наступне питання — це чому має дорівнювати це eps, і це питання не дуже просте. Спочатку про термінолоґію: epsilon, ε — це типовий в математиці знак для похибки. Згадаймо, наприклад, визначення ліміту послідовности: «y» таке, що для кожного (∀) ε > 0 (мається на увазі: довільно мале) існує (∃) таке n, що для довільного k ⩾ n, abs(x[k] — y) < ε. Але, є ще так званий «машинний епсілон», який визначався так: це найменше число таке, що 1⊕ε ≠ 1, де ⊕ — машинна реалізація додавання згідно з наявною точністю і округленням до найближчого. Наприклад, в C++ std::numeric_limits<T>::epsilon це саме він. Цей другий епсілон — треба його відокремити і взагалі забути про нього, він нам не потрібен.
Для прикладу дійсно потрібного візьмемо math.isclose() із Python. Функція приймає параметри — rel_tol (relative tolerance, відносний дозвіл) із замовчуванням 1e-9, і abs_tol (absolute tolerance, абсолютний дозвіл) із замовчуванням 0. Оце 1e-9 вже якийсь натяк. Враховуючи те, що єдиний вбудований там тип це IEEE754 double (щонайменше 15 десяткових цифр), запас в міліон найменших цифр достатній для, можливо, більшости випадків і в той же час він десь як раз на рівні типової вимоги точности фізичних розрахунків, це виглядає здраво. Реалізація перевіряє три випадки (після того, як усякі NaN і Inf відкінуті):
return (((diff <= fabs(rel_tol * b)) || (diff <= fabs(rel_tol * a))) || (diff <= abs_tol));
Цю реалізацію можна брати за основу і для інших мов (перенести легко).
В Google Test є своє порівняння з похибкою. Тут значно суворіші критерії: збігом (ASSERT_{FLOAT,DOUBLE}_EQ) вважається різниця до 4 ULP (порівняємо: 1e-9 для double, як в питонівскому isclose(), це приблизно 90 міліонів ULP). Ну, назви різні (equal vs. close). Нема реґульованої відносної похибки. А є ASSERT_NEAR, який вже ближче: у нього абсолютна похибка є параметром. Але відносної нема. Тут, мені здається, повтор пітоновського isclose() був би доцільним.
Коли відносного дозволу не вистачає? Наприклад, коли a і b мають різні знаки. Ви ніколи не зможете таким чином спіймати близкість 0.0001 і —0.0001. Тут тільки питати абсолютний дозвіл.
Таку isclose() можна взяти за базу... І все одно — дивимось на приклади, коли зовнішній вигляд обманює:
>>> math.isclose(1.01, 1.02, rel_tol=0, abs_tol=0.01) False >>> math.isclose(1.01, 1.02, rel_tol=0, abs_tol=0.01000000000000001) True
Для порівняння на нерівність потрібен свій варіант у стилі того ж isclose, але з іншою операцією; доведеться робити самому за аналоґією. І тут важливо, чи є з двох чисел одне точне, чи оба прийшли як приблизні. Якщо «b» точне, а «a» приблизне, то a < b (як ствердження) замінюється на:
a < b * (1 - rel_tol) || a < b - abs_tol
Якщо оба приблизні, то як найпростіший метод обидва дозволи домножуються на 2. Але у такому випадку треба завжди дивитись на специфіку алґоритму. Наприклад, у мене був випадок, коли нормальним критерієм
зупинки було: fabs(x[n] - x[n-1]) <= eps && fabs(x[n] - x[n-2]) <= eps (ці x[n] це послідовність розвʼязків з поступовим наближенням).
UPDATE[2026-04-22]: Один показовий і цікавий приклад як раз на тонку різницю був тут. Коротко: Half-Life 2, двері не чіпляли охоронця при розрахунках на x87 FPU, але стали чіпляти на SSE. Як писав Станіслав Лем в повісті «Катар», «Множина фронтовиків включає підмножину вбитих і поранених, але вам не вдасться виділити підмножини солдатів, яких куля оминула за волосинку, бо вони нічим не відрізняються від тих, яких кулі минали за кілометр.» Ця проблема не була спіймана в оригінальному рушії, бо як раз «куля» пройшла в волосинці.
Ще один найдивніший приклад, коли виникає нерівність («bug 323»), буде наведений в частині 8. Анонсуємо тут коротко: може бути, що a+b == a+b дасть false 😲
Висновки: майже як всюди тут. Без розуміння того, що стоїть за конкретною операцією, не можна судити про її реалізацію.
Немає коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів