сравнение плавающих чисел

[sab123]

Навеяло: как известно, плавающие числа нельзя сравнивать на точное равенство. Вместо того их надо сравнивать на различие в пределах погрешности. Спрашивается:

(1) Какого хрена в процессорах нет инструкции сравнения на равенство с погрешностью? которая брала бы три операнда - два числа и размер погрешности. Кстати, ту же фигню можно использовать и для сравнения на больше-меньше, чтобы разница в пределах погрешности считалась равенством.

(2) Какого хрена в языках высокого уровня нет операции сравнения на равенство с погрешностью? Погрешность можно было бы даже задавать один раз в начале блока, и потом обычно равенство делалось бы этой операцией.

Comments

[spamsink]

(1) В процессорах нет инструкции сравнения на равенство с погрешностью ровно потому же, почему нет, скажем, инструкции сложения трех чисел: потому что и то, и другое легко реализуется программно, и экономия времени не будет оправдывать расходы на дополнительные транзисторы, тем более что городить дополнительный data path для третьего операнда гораздо дороже, чем реализовать какую-нибудь команду с двумя операндами.

(2) Это называется "подпрограмма", и существует во всех языках высокого уровня.

[orleanz.livejournal.com]

Жестоко слово сие

[spamsink]

Но справедливо. Желание иметь инструкцию с тремя операндами свидетельствует о принципиальном непонимании процессорной архитектуры. Абсолютная погрешность реализуется вычитанием и взятием абсолютной величины - это две очень дешевые операции.

Операция сравнения на равенство с погрешностью на уровне языка - ненужный "синтаксический сахар", и в языках с мощностью, сравнимой с С++, реализуется самостоятельно с тем же успехом.

[sab123.livejournal.com]

(1) Делать программно - сложно и медленно. Это как минимум 3 инструкции - вычесть, abs, сравнить. Ну, и если очень хотеть, то ничего не мешает установить третий операнд отдельной командой в регистр состояния, откуда его потом и брать (он скорее всего не будет меняться для многих сравнений). А что касается дополнительных транзисторов, то они нынче фигня, проблема не в том. чтобы наштамповать транзисторов, а в том, чтобы из них извлечь пользу.

(2) Подпрограммой - неудобно. Не говоря уже о том, как неудобно ее увязывать со значением, задаваемым в начале блока. Ну и вообще, в любом случае не подпрограмма, а хотя бы макро.

[spamsink]

1. Чем больше у процессора состояния, тем сложнее переключать контексты.

2. Польза из транзисторов извлекается путем их использования в как можно большем числе команд. Редко используемые команды с уникальной функциональностью - dead weight.

3. Делать программно ровно так же быстро, как и аппаратно. Если процессор в принципе умеет делать операцию, описываемую как "вычесть, abs, сравнить" быстрее, чем за 3 такта, то он это сможет сделать и путем instruction fusion. А если не умеет, то выгоды на копеечной экономии размера кода практически никакой.

Пишешь класс со статическим стеком значений точности и переопределенной операцией сравнения (== подпрограммой). Значение, задаваемое в начале блока, кладется на верхушку стека, в конце блока - убирается оттуда. И все дела.

[sab123.livejournal.com]

1. А вот для этого у нас есть компилятор. Можно не сохранять контекст, а просто пусть следит за тем, чтобы заново загрузить контекст между вызовом функции и следующим использованием.

2. Ну так это не редко используемые, а часто используемые команды. Вот точное сравнение - это будут редко используемые, если писать правильно, а не срезать углы.

3. Процессору необязательно выполнять как "вычесть, abs, сравнить", а можно например параллельно выполнить два вычитания и два сравнения. Про instruction fusion - это совершенно та же фигня, по сути одна инструкция, записывающаяся магической последовательностью кодов. Кстати, наверное интересная и разновидность - это брать точность не как константу, а как зависящую от порядка участвующих значений.

4. Это коряво, медленно, и непонятно как реализовать если блоком является класс или файл. Кстати, обрати внимание на то, что генерить правильную магическую последовательность инструкций для instruction fusion без поддержки компилятора не получится. Ну ладно, положим, Си - это не язык, заточенный под плавающую математику, в нем можно обойтись ручными костылями и даже плюнуть на эффективность. Но в языках-то, заточенных под математику, типа Фортрана или SQL - почему нет?

[spamsink]

1. Речь о переключении контекстов между независимым процессами.

2. Как часто, вообще, используется в реальных алгоритмах сравнение плавающих чисел на (приближенное) равенство? Конкретные значения есть?
В итеративных алгоритмах epsilon - параметр для условия завершения итераций, поэтому записывать эту единственную проверку и удобнее, и математичнее как abs(x-y) < epsilon.

3. Instruction reordering разберется, точно так же, как разбирается со сложением четырех чисел. И операция должна быть коммутативной, иначе вообще бардак будет.

4. В фортране есть встроенные функции epsilon и tiny, позволяющие более гибко выразить, что хочется. За SQL я не отвечаю. :)

[sab123.livejournal.com]

> Речь о переключении контекстов между независимым процессами.
Ну так использовать фиксированный регистр (какой-нибудь %f0 или в этом роде), он сохранится вместе с остальными регистрами плавающей точки. И так же полно инструкций, которые требуют, чтобы один из операндов был в фиксированном регистре.

> Как часто, вообще, используется в реальных алгоритмах сравнение плавающих чисел на (приближенное) равенство? Конкретные значения есть?

Мои лично использования сводятся к аналогу SQL, и там оно нужно просто постоянно. Если делать правильно.

> В итеративных алгоритмах epsilon - параметр для условия завершения итераций, поэтому записывать эту единственную проверку и удобнее, и математичнее как abs(x-y) < epsilon.

А в терминах равенства с погрешностью можно было бы записывать еще проще: x != y.

> В фортране есть встроенные функции epsilon и tiny, позволяющие более гибко выразить, что хочется.

Почитал. Это на самом деле не функции, а константы типа как в limits.h. С которыми надо все равно вручную сравнивать.

[spamsink]

Неортогональные ISAs ужасны.

Зачем в SQL плавающая точка? Значения каких типов предметной области нужно хранить в этом формате?

можно было бы записывать еще проще: x != y

Предварительно выполнив где-то далеко в коде setprecision(epsilon). Текстуальная локальность ухудшается, а с ней и читаемость-поддерживаемость кода.

С которыми надо все равно вручную сравнивать.

Так о том и речь, что иногда надо с epsilon, иногда - c tiny. Чем переключать режимы туда-сюда, проще написать сравнение явно.

[sab123.livejournal.com]

> Значения каких типов предметной области нужно хранить в этом формате?

Например, финансовые. Когда речь идет не о точных значениях денег, а о вероятностных оценках и тому подобном.

> Предварительно выполнив где-то далеко в коде setprecision(epsilon). Текстуальная локальность ухудшается, а с ней и читаемость-поддерживаемость кода.

Наборот, читаемость и поддерживаемость увеличивается от того, что код не засоряется повторениями epsilon.

> Так о том и речь, что иногда надо с epsilon, иногда - c tiny. Чем переключать режимы туда-сюда, проще написать сравнение явно.

Гм, а когда с кем из них?

[juan-gandhi.livejournal.com]

Очень справедливо.

[spamsink]

Ты серьезно, что ли?

[juan-gandhi.livejournal.com]

Да. Если на самом деле равенство не определено, то зачем это расширение алгебры?

[spamsink]

Вот и я говорю, что незачем. Ты на что хотел ответить "справедливо" - на пост или на мой комментарий?

[sab123.livejournal.com]

Вот сравнение на точное равенство можно выбросить за бессмыссленностью.

[spamsink]

Не собачье дело языка решать, как и для чего я использую числа с плавающей точкой.

[sab123.livejournal.com]

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

Если каждый текст про программирование с плавающей точкой начинается с "их нельзя сравнивать", то почему оно не отражено в языках? А потом люди < a href="http://vit-r.livejournal.com/782219.html">предъявляют претензии. Кстати, в SQL и вовсе нет определяемых пользователем подпрограмм.

[spamsink]

Эквивалентными, но более дорогими, чем сейчас. Зачем нам эта головная боль?

набор операций, отражающих концепции предметной области

В универсальных языках высокого уровня это делается путем введения пользовательских типов, отражающих концепции предметной области, а претензии к специализированным, наподобие SQL, следует предъявлять явно.

[juan-gandhi.livejournal.com]

На пост. Заявление правильное; правильного ответа как-то нету зато.

[spamsink]

Ну так дай его. :)

[juan-gandhi.livejournal.com]

Его вообще нету. У меня тоже.
Все сложно. Тут есть хитрая комонада, и традиция такова, что мы не вполне понимаем, что вообще за зверь такой, вещественные числа.

[sab123.livejournal.com]

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

[enternet.livejournal.com]

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

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

Извините )

[sab123.livejournal.com]

Если я правильно помню (я не настоящий сварщик по преданию греху с плавающими числами, а только по верхушкам нахватался), в общем случае никакие нельзя. Но, конечно, от переводов из десятичных в двоичные и назад добавляется пикантности.

[sappa.livejournal.com]

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