сравнение плавающих чисел
Dec. 22nd, 2014 10:27 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sab123Навеяло: как известно, плавающие числа нельзя сравнивать на точное равенство. Вместо того их надо сравнивать на различие в пределах погрешности. Спрашивается:
(1) Какого хрена в процессорах нет инструкции сравнения на равенство с погрешностью? которая брала бы три операнда - два числа и размер погрешности. Кстати, ту же фигню можно использовать и для сравнения на больше-меньше, чтобы разница в пределах погрешности считалась равенством.
(2) Какого хрена в языках высокого уровня нет операции сравнения на равенство с погрешностью? Погрешность можно было бы даже задавать один раз в начале блока, и потом обычно равенство делалось бы этой операцией.
(1) Какого хрена в процессорах нет инструкции сравнения на равенство с погрешностью? которая брала бы три операнда - два числа и размер погрешности. Кстати, ту же фигню можно использовать и для сравнения на больше-меньше, чтобы разница в пределах погрешности считалась равенством.
(2) Какого хрена в языках высокого уровня нет операции сравнения на равенство с погрешностью? Погрешность можно было бы даже задавать один раз в начале блока, и потом обычно равенство делалось бы этой операцией.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-12-22 06:42 pm (UTC)(2) Это называется "подпрограмма", и существует во всех языках высокого уровня.
no subject
Date: 2014-12-22 07:01 pm (UTC)no subject
Date: 2014-12-22 07:19 pm (UTC)no subject
Date: 2014-12-22 07:45 pm (UTC)Операция сравнения на равенство с погрешностью на уровне языка - ненужный "синтаксический сахар", и в языках с мощностью, сравнимой с С++, реализуется самостоятельно с тем же успехом.
no subject
Date: 2014-12-22 07:46 pm (UTC)no subject
Date: 2014-12-22 07:48 pm (UTC)no subject
Date: 2014-12-22 07:50 pm (UTC)(2) Подпрограммой - неудобно. Не говоря уже о том, как неудобно ее увязывать со значением, задаваемым в начале блока. Ну и вообще, в любом случае не подпрограмма, а хотя бы макро.
no subject
Date: 2014-12-22 07:56 pm (UTC)no subject
Date: 2014-12-22 08:04 pm (UTC)no subject
Date: 2014-12-22 08:06 pm (UTC)2. Польза из транзисторов извлекается путем их использования в как можно большем числе команд. Редко используемые команды с уникальной функциональностью - dead weight.
3. Делать программно ровно так же быстро, как и аппаратно. Если процессор в принципе умеет делать операцию, описываемую как "вычесть, abs, сравнить" быстрее, чем за 3 такта, то он это сможет сделать и путем instruction fusion. А если не умеет, то выгоды на копеечной экономии размера кода практически никакой.
Пишешь класс со статическим стеком значений точности и переопределенной операцией сравнения (== подпрограммой). Значение, задаваемое в начале блока, кладется на верхушку стека, в конце блока - убирается оттуда. И все дела.
no subject
Date: 2014-12-22 08:08 pm (UTC)no subject
Date: 2014-12-22 08:28 pm (UTC)Если каждый текст про программирование с плавающей точкой начинается с "их нельзя сравнивать", то почему оно не отражено в языках? А потом люди < a href="http://vit-r.livejournal.com/782219.html">предъявляют претензии. Кстати, в SQL и вовсе нет определяемых пользователем подпрограмм.
no subject
Date: 2014-12-22 08:35 pm (UTC)набор операций, отражающих концепции предметной области
В универсальных языках высокого уровня это делается путем введения пользовательских типов, отражающих концепции предметной области, а претензии к специализированным, наподобие SQL, следует предъявлять явно.
no subject
Date: 2014-12-22 08:41 pm (UTC)Не могли бы вы уточнить, какие именно числа с плавающей точкой нельзя сравнивать на точное равенство: двоичные или десятичные. И ещё меня смущает понятие погрешности. Думаю что это про грех, грех точного сравнения чисел, какому мы все предаемся.
Извините )
no subject
Date: 2014-12-22 08:41 pm (UTC)2. Ну так это не редко используемые, а часто используемые команды. Вот точное сравнение - это будут редко используемые, если писать правильно, а не срезать углы.
3. Процессору необязательно выполнять как "вычесть, abs, сравнить", а можно например параллельно выполнить два вычитания и два сравнения. Про instruction fusion - это совершенно та же фигня, по сути одна инструкция, записывающаяся магической последовательностью кодов. Кстати, наверное интересная и разновидность - это брать точность не как константу, а как зависящую от порядка участвующих значений.
4. Это коряво, медленно, и непонятно как реализовать если блоком является класс или файл. Кстати, обрати внимание на то, что генерить правильную магическую последовательность инструкций для instruction fusion без поддержки компилятора не получится. Ну ладно, положим, Си - это не язык, заточенный под плавающую математику, в нем можно обойтись ручными костылями и даже плюнуть на эффективность. Но в языках-то, заточенных под математику, типа Фортрана или SQL - почему нет?
no subject
Date: 2014-12-22 08:52 pm (UTC)Ничего не мешает в компиляторе генерить разный код для случая погрешности, равной 0 и не равной 0.
> В универсальных языках высокого уровня это делается путем введения пользовательских типов, отражающих концепции предметной области
Если так рассуждать, то и вообще плавающая точка не нужна, пусть реализуют ее в виде подпрограмм на целых числах. (И таки да, есть исторические примеры таких рассуждений на уровне языков, а на уровне железа вообще только относительно недавно плавающая точка стала массовой).
Мир совершенно не сводится к Си, вот например в языках с виртуальной машиной тоже не очень-то получится написать такое расширение, не вылезая за пределы виртуальной машины. Ну, то есть, написать можно, но оно при этом потащит за собой много оверхеда.
no subject
Date: 2014-12-22 08:57 pm (UTC)no subject
Date: 2014-12-22 09:03 pm (UTC)2. Как часто, вообще, используется в реальных алгоритмах сравнение плавающих чисел на (приближенное) равенство? Конкретные значения есть?
В итеративных алгоритмах epsilon - параметр для условия завершения итераций, поэтому записывать эту единственную проверку и удобнее, и математичнее как abs(x-y) < epsilon.
3. Instruction reordering разберется, точно так же, как разбирается со сложением четырех чисел. И операция должна быть коммутативной, иначе вообще бардак будет.
4. В фортране есть встроенные функции epsilon и tiny, позволяющие более гибко выразить, что хочется. За SQL я не отвечаю. :)
no subject
Date: 2014-12-22 09:08 pm (UTC)Если сейчас ввести пользовательский тип, то именно так и будет, разве что умолчание окажется другим.
вообще плавающая точка не нужна
Не "нужна", но "полезна на практике", поскольку дает выигрыш во времени выполнения программ на порядки по сравнению с soft-float. Много ли корысти будет от команды сравнения с погрешностью?
в языках с виртуальной машиной тоже не очень-то получится написать такое расширение, не вылезая за пределы виртуальной машины
На уровне виртуальной машины можно извращаться как угодно, это на хардвер не влияет.
no subject
Date: 2014-12-22 09:21 pm (UTC)no subject
Date: 2014-12-22 09:24 pm (UTC)Ну так использовать фиксированный регистр (какой-нибудь %f0 или в этом роде), он сохранится вместе с остальными регистрами плавающей точки. И так же полно инструкций, которые требуют, чтобы один из операндов был в фиксированном регистре.
> Как часто, вообще, используется в реальных алгоритмах сравнение плавающих чисел на (приближенное) равенство? Конкретные значения есть?
Мои лично использования сводятся к аналогу SQL, и там оно нужно просто постоянно. Если делать правильно.
> В итеративных алгоритмах epsilon - параметр для условия завершения итераций, поэтому записывать эту единственную проверку и удобнее, и математичнее как abs(x-y) < epsilon.
А в терминах равенства с погрешностью можно было бы записывать еще проще: x != y.
> В фортране есть встроенные функции epsilon и tiny, позволяющие более гибко выразить, что хочется.
Почитал. Это на самом деле не функции, а константы типа как в limits.h. С которыми надо все равно вручную сравнивать.
no subject
Date: 2014-12-22 09:30 pm (UTC)no subject
Date: 2014-12-22 09:35 pm (UTC)Зачем в SQL плавающая точка? Значения каких типов предметной области нужно хранить в этом формате?
можно было бы записывать еще проще: x != y
Предварительно выполнив где-то далеко в коде setprecision(epsilon). Текстуальная локальность ухудшается, а с ней и читаемость-поддерживаемость кода.
С которыми надо все равно вручную сравнивать.
Так о том и речь, что иногда надо с epsilon, иногда - c tiny. Чем переключать режимы туда-сюда, проще написать сравнение явно.
no subject
Date: 2014-12-22 09:35 pm (UTC)Затрудняюсь сказать, оно будет определяться тем, насколько часто произодится сравнение, то есть насколько короткие тела циклов. А сколько корысти нужно для того, чтобы добавить команду? Чего-нибудь типа 1% хватит? 5%?
Ну хорошо, положим фиг с ней, с командой. Но вот заметим, что в языках-то плавающая точка все равно присутствовала в качестве родного типа, даже если реализовалась как soft-float. А ведь могли бы сказать, что ну нафиг, пусть она будет в библиотеке.
> На уровне виртуальной машины можно извращаться как угодно, это на хардвер не влияет.
Фиг с ним с хардвером (хотя надо сказать, что хардверщики обладают специальным талантом создавать кривизну, чтобы их хардвер было трудно использовать в софтвере). Я про то, что если делать библиотеку в терминах виртуальной машины, то на каждое использование наложится во-первых оверхед интерпретации отдельных команд над плавающими числами, во-вторых вызовов функций в виртуальной машине. А вот если добавить специальную инструкцию к системе команд виртуальной машины, то весь этот оверхед пропадет.
no subject
Date: 2014-12-22 09:36 pm (UTC)Все сложно. Тут есть хитрая комонада, и традиция такова, что мы не вполне понимаем, что вообще за зверь такой, вещественные числа.