[Высокая производительность, Ненормальное программирование, C] Быстрое сравнение double
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Вчера здесь вышла статья о быстром парсинге double, я зашёл во блог к её автору, и нашёл там ещё один интересный трюк. При сравнении чисел с плавающей точкой особое внимание приходится уделять NaN (восемь лет назад я писал про них подробнее); но если сравниваемые числа заведомо не NaN, то сравнить их можно быстрее, чем это делает процессор!
Положительные double сравнивать очень просто: нормализация гарантирует нам, что из чисел с разной экспонентой больше то, чья экспонента больше, а из чисел с равной экспонентой больше то, чья мантисса больше. Стандарт IEEE 754 заботливо поместил экспоненту в старшие биты, так что положительные double можно сравнивать просто как int64_t.
оригинал
С отрицательными числами немного сложнее: они хранятся в прямом коде, тогда как int64_t — в дополнительном. Это значит, что для использования целочисленного сравнения младшие 63 бита double необходимо инвертировать (при этом получится -0. < +0., что не соответствует стандарту, но на практике не представляет проблемы). Явная проверка старшего бита и условный переход уничтожили бы всю выгоду от перехода к целочисленному сравнению; но есть способ проще!
inline int64_t to_int64(double x) {
int64_t a = *(int64_t*)&x;
uint64_t mask = (uint64_t)(a >> 63) >> 1;
return a ^ mask;
}
inline bool is_smaller(double x1, double x2) {
return to_int64(x1) < to_int64(x2);
}
a>>63 заполняет все 64 бита копиями знакового бита, и затем >>1 обнуляет старший бит.
Во блоге у Daniel Lemire несколько другой код (той же вычислительной сложности), но мой вариант сохраняет то полезное свойство, что to_int64(0.) == 0
===========
Источник:
habr.com
===========
Похожие новости:
- [Системное администрирование, Системное программирование, DevOps] Первый взгляд на Tekton Pipelines (перевод)
- [Разработка под iOS, Разработка под Android, Монетизация мобильных приложений, Законодательство в IT, Игры и игровые приставки] Epic Games попыталась ограничить работу магазинов приложений в Северной Дакоте
- [JavaScript, Системы сборки] Анонс Vite 2.0 (перевод)
- [IT-инфраструктура, Резервное копирование, Облачные сервисы] Вебинар DataLine «Как получить рабочий бэкап: выбираем инструменты резервного копирования» 25 февраля
- [Java, API] Partial Update library. Частичное обновление сущности в Java Web Services
- [Производство и разработка электроники, История IT, Старое железо] Легенда на ладони: создаём крошечный компьютер PDP11 (перевод)
- [Информационная безопасность, WordPress, Open source, Администрирование доменных имен] Новый плагин CrowdSec для защиты сайтов на WordPress
- [Машинное обучение, Искусственный интеллект, Здоровье] МТИ представил модель машинного обучения для поисков вариантов лечения Covid-19
- [Беспроводные технологии, Разработка систем связи, Научно-популярное, Физика] Оптика свободного пространства: плазмонный метаматериал, флюоресценция и красители
- [Информационная безопасность, Сетевые технологии, IT-компании] От локального ПО до всероссийских инсталляций: как изменился ИКС за 17 лет
Теги для поиска: #_vysokaja_proizvoditelnost (Высокая производительность), #_nenormalnoe_programmirovanie (Ненормальное программирование), #_c, #_ieee_754, #_0x5f3759df, #_vysokaja_proizvoditelnost (
Высокая производительность
), #_nenormalnoe_programmirovanie (
Ненормальное программирование
), #_c
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 15:22
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Вчера здесь вышла статья о быстром парсинге double, я зашёл во блог к её автору, и нашёл там ещё один интересный трюк. При сравнении чисел с плавающей точкой особое внимание приходится уделять NaN (восемь лет назад я писал про них подробнее); но если сравниваемые числа заведомо не NaN, то сравнить их можно быстрее, чем это делает процессор! Положительные double сравнивать очень просто: нормализация гарантирует нам, что из чисел с разной экспонентой больше то, чья экспонента больше, а из чисел с равной экспонентой больше то, чья мантисса больше. Стандарт IEEE 754 заботливо поместил экспоненту в старшие биты, так что положительные double можно сравнивать просто как int64_t.  оригинал С отрицательными числами немного сложнее: они хранятся в прямом коде, тогда как int64_t — в дополнительном. Это значит, что для использования целочисленного сравнения младшие 63 бита double необходимо инвертировать (при этом получится -0. < +0., что не соответствует стандарту, но на практике не представляет проблемы). Явная проверка старшего бита и условный переход уничтожили бы всю выгоду от перехода к целочисленному сравнению; но есть способ проще! inline int64_t to_int64(double x) {
int64_t a = *(int64_t*)&x; uint64_t mask = (uint64_t)(a >> 63) >> 1; return a ^ mask; } inline bool is_smaller(double x1, double x2) { return to_int64(x1) < to_int64(x2); } a>>63 заполняет все 64 бита копиями знакового бита, и затем >>1 обнуляет старший бит. Во блоге у Daniel Lemire несколько другой код (той же вычислительной сложности), но мой вариант сохраняет то полезное свойство, что to_int64(0.) == 0 =========== Источник: habr.com =========== Похожие новости:
Высокая производительность ), #_nenormalnoe_programmirovanie ( Ненормальное программирование ), #_c |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 15:22
Часовой пояс: UTC + 5