Согласна ли математика с плавающей точкой в ​​C #? Может ли так быть?

Question

Нет, это не другой "Почему (1 / 3.0) * 3! = 1" вопрос.

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

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

Это происходит даже среди процессоров, которые «следуют» IEEE-754 , главным образом потому, что некоторые процессоры (а именно x86) используют удвоенную расширенную точность . То есть они используют 80-битные регистры для выполнения всех вычислений, а затем усекаются до 64- или 32-битных, что приводит к результатам округления, отличным от тех, которые используют 64- или 32-битные для расчетов.

Я видел несколько решений этой проблемы в Интернете, но все для C ++, а не для C #:

• Отключить режим двойной расширенной точности (чтобы все вычисления double использовали 64-битный IEEE-754), используя _controlfp_s (Windows), _FPU_SETCW (Linux?) Или fpsetprec (BSD).
• Всегда запускайте один и тот же компилятор с одинаковыми настройками оптимизации и требуйте, чтобы все пользователи имели одинаковую архитектуру ЦП (без кроссплатформенного воспроизведения). Поскольку мой «компилятор» на самом деле является JIT, который может оптимизироваться по-разному при каждом запуске программы , я не думаю, что это возможно.
• Используйте арифметику с фиксированной точкой и избегайте float и double в целом. decimal будет работать для этой цели, но будет намного медленнее, и ни одна из библиотечных функций System.Math не поддерживает его.

---

Итак, это вообще проблема в C #? Что если я собираюсь поддерживать только Windows (не Mono)?

Если это так, Есть ли способ заставить мою программу работать с обычной двойной точностью?

Если нет, Существуют ли библиотеки, которые помогли бы поддерживать согласованность вычислений с плавающей запятой?

Answer 1

Я не знаю способа сделать нормальные плавающие точки детерминированными в .net. JITter разрешено создавать код, который ведет себя по-разному на разных платформах (или между разными версиями .net). Поэтому использование нормальных float s в детерминированном .net-коде невозможно.

Обходные пути, которые я рассмотрел:

1. Реализация FixedPoint32 в C #. Хотя это не так сложно (у меня есть половина готовой реализации), очень маленький диапазон значений делает его раздражающим в использовании. Вы должны быть осторожны все время, чтобы не переполнить и не потерять слишком много точности. В конце концов я обнаружил, что это не проще, чем использовать целые числа напрямую.
2. Реализация FixedPoint64 в C #. Я нашел это довольно сложно сделать. Для некоторых операций были бы полезны промежуточные целые числа из 128 бит. Но .net не предлагает такого типа.
3. Реализация пользовательской 32-битной плавающей запятой. Отсутствие встроенного BitScanReverse вызывает некоторые неудобства при реализации этого. Но в настоящее время я считаю, что это самый перспективный путь.
4. Использовать собственный код для математических операций. Затраты на делегатский вызов в каждой математической операции.

Я только что начал программную реализацию 32-битной математики с плавающей запятой. Он может делать около 70 миллионов операций добавления / умножения в секунду на моем 2,66 ГГц i3. https://github.com/CodesInChaos/SoftFloat. Очевидно, это все еще очень неполно и глючит.

Answer 2

Спецификация C # (§4.1.6 типы с плавающей запятой) специально позволяет выполнять вычисления с плавающей запятой, используя точность, превышающую точность результата. Так что нет, я не думаю, что вы можете сделать эти расчеты детерминированными непосредственно в .Net. Другие предлагали различные обходные пути, чтобы вы могли их попробовать.

Answer 3

Следующая страница может быть полезна в случае, когда вам нужна абсолютная переносимость таких операций. В нем обсуждается программное обеспечение для тестирования реализаций стандарта IEEE 754, включая программное обеспечение для эмуляции операций с плавающей запятой. Однако большая часть информации, вероятно, относится к C или C ++.

http://www.math.utah.edu/~beebe/software/ieee/

Примечание о фиксированной точке

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

• Сложение и вычитание тривиальны. Они работают так же, как целые числа. Просто сложите или вычтите!
• Чтобы умножить два числа с фиксированной запятой, умножьте два числа, затем сдвиньте вправо на определенное количество дробных битов.
• Чтобы разделить два числа с фиксированной запятой, сдвиньте делимое влево на определенное количество дробных битов, а затем разделите на делитель.
• Глава четвертая из этого документа содержит дополнительные указания по реализации двоичных чисел с фиксированной запятой.

Двоичные числа с фиксированной запятой могут быть реализованы для любого целочисленного типа данных, такого как int, long и BigInteger, а также для несовместимых с CLS типов uint и ulong.

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

// Assume each number has a 12 bit fractional part. (1/4096)
// Each entry in the lookup table corresponds to a fixed point number
//  with an 8-bit fractional part (1/256)
input+=(1<<3); // Add 2^3 for rounding purposes
input>>=4; // Shift right by 4 (to get 8-bit fractional part)
// --- clamp or restrict input here --
// Look up value.
return lookupTable[input];

Answer 4

Это проблема для C #?

Да. Разные архитектуры - это наименьшее количество ваших забот, разные частоты кадров и т. Д. Могут привести к отклонениям из-за неточностей в представлениях с плавающей точкой - даже если они являются одинаковыми неточностями (например, одинаковая архитектура, за исключением более медленного GPU на одной машине) .

Могу ли я использовать System.Decimal?

Нет причин, по которым ты не можешь, однако это медленная собака.

Есть ли способ заставить мою программу работать с двойной точностью?

Да. Хостинг среды CLR самостоятельно ; и скомпилировать все необходимые вызовы / флаги (которые изменяют поведение арифметики с плавающей запятой) в приложение C ++ перед вызовом CorBindToRuntimeEx.

Существуют ли библиотеки, которые помогли бы поддерживать согласованность вычислений с плавающей точкой?

Не то, что я знаю.

Есть ли другой способ решить эту проблему?

Я занимался этой проблемой раньше, идея в том, чтобы использовать QNumbers . Они являются формой реальных событий с фиксированной точкой; но не фиксированная точка в base-10 (десятичная) - скорее base-2 (двоичная); из-за этого математические примитивы на них (add, sub, mul, div) намного быстрее, чем наивные фиксированные точки base-10; особенно если n одинаково для обоих значений (что в вашем случае будет). Кроме того, поскольку они являются интегральными, они имеют четко определенные результаты на каждой платформе.

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

Могу ли я использовать больше математических функций с QNumbers?

Да, туда и обратно десятичное число, чтобы сделать это. Кроме того, вы действительно должны использовать справочные таблицы для функций trig (sin, cos); поскольку они могут действительно давать разные результаты на разных платформах - и если вы правильно их кодируете, они могут напрямую использовать QNumbers.

Answer 5

Согласно этой немного старой записи в блоге MSDN JIT не будет использовать SSE / SSE2 для плавающей запятой, это все x87. Из-за этого, как вы упоминали, вам нужно беспокоиться о режимах и флагах, а в C # это невозможно контролировать. Поэтому использование обычных операций с плавающей запятой не гарантирует одинаковый результат на каждой машине для вашей программы.

Чтобы получить точную воспроизводимость двойной точности, вам придется выполнить программную эмуляцию с плавающей запятой (или с фиксированной запятой). Я не знаю библиотек C # для этого.

В зависимости от операций, которые вам нужны, вы можете уйти с единой точностью. Вот идея:

• храните все значения, которые вам нужны, с одинарной точностью
• для выполнения операции:
  • расширение входов до двойной точности
  • сделать операцию с двойной точностью
  • преобразовать результат обратно с одинарной точностью

Большая проблема с x87 заключается в том, что вычисления могут выполняться с 53-битной или 64-битной точностью в зависимости от флага точности и от того, был ли регистр передан в память. Но для многих операций выполнение операции с высокой точностью и округление до более низкой точности гарантирует правильный ответ, что означает, что ответ будет гарантированно одинаковым во всех системах. Получите ли вы дополнительную точность, не имеет значения, поскольку у вас достаточно точности, чтобы гарантировать правильный ответ в любом случае.

Операции, которые должны работать в этой схеме: сложение, вычитание, умножение, деление, sqrt. Такие вещи, как грех, опыт и т. Д. Не сработают (результаты обычно совпадают, но нет гарантии). "Когда двойное округление безвредно?" Справочник ACM (платный рег.)

Надеюсь, это поможет!

Answer 6

Как уже говорилось другими ответами: Да, это проблема в C # - даже при использовании чистой Windows.

Что касается решения: Вы можете уменьшить (и с некоторым усилием / ударом по производительности) полностью избежать этой проблемы, если вы используете встроенный класс BigInteger и масштабируете все вычисления с определенной точностью, используя общий знаменатель для любого вычисления / хранения таких чисел.

По требованию OP - в отношении производительности:

System.Decimal представляет число с 1 битом для знака и 96-битным целым числом и «шкалой» (представляющей, где находится десятичная точка). Для всех вычислений, которые вы делаете, он должен работать с этой структурой данных и не может использовать никакие инструкции с плавающей запятой, встроенные в ЦП.

«1011» «решение» делает нечто похожее - только то, что вы можете определить, сколько цифр вам нужно / нужно ... возможно, вы хотите только 80 бит или 240 бит точности.

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

Чтобы уменьшить удар по производительности, есть несколько стратегий - например, QNumbers (см. Ответ Джонатана Дикинсона - Согласна ли математика с плавающей запятой в C #? Это может быть? ) и / или кеширование (например, trig расчеты ...) и т. д.

Answer 7

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

Стратегия, которую я бы выбрал, по сути состоит в следующем:

• Используйте более медленный (если необходимо; если есть более быстрый способ, отличный!), Но предсказуемый метод для получения воспроизводимых результатов
• Используйте double для всего остального (например, рендеринга)

Суть в том, что вам нужно найти баланс.Если вы тратите 30 мс на рендеринг (~ 33 к / с) и только 1 мс на обнаружение коллизий (или вставляете какую-то другую высокочувствительную операцию) - даже если вы утраиваете время, необходимое для выполнения критической арифметики, влияние, которое она оказывает на частоту кадров, составляетВы снижаете скорость с 33,3 до 30,3 кадра / с.

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

Answer 8

Ну, вот моя первая попытка на как это сделать :

1. Создайте проект ATL.dll, в котором есть простой объект, который будет использоваться для ваших критических операций с плавающей запятой. не забудьте скомпилировать его с флагами, которые отключают использование любого оборудования, отличного от xx87, для выполнения операций с плавающей запятой.
2. Создание функций, которые вызывают операции с плавающей запятой и возвращают результаты; начните с простого, а затем, если он работает на вас, вы всегда можете увеличить сложность, чтобы при необходимости удовлетворить ваши требования к производительности позже.
3. Разместите вызовы control_fp вокруг фактической математики, чтобы убедиться, что она выполняется одинаково на всех машинах.
4. Ссылка на вашу новую библиотеку и тестирование, чтобы убедиться, что она работает, как ожидалось.

(Я полагаю, что вы можете просто скомпилировать 32-битный файл .dll и затем использовать его с x86 или AnyCpu [или, скорее всего, только для x86 в 64-битной системе; см. Комментарий ниже].)

Тогда, предполагая, что это работает, если вы захотите использовать Mono, я полагаю, вы сможете реплицировать библиотеку на другие платформы x86 аналогичным образом (конечно, не COM; хотя, возможно, с помощью Wine? мой район, как только мы пойдем туда, хотя ...).

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

Answer 9

Проверка ссылок в других ответах дает понять, что у вас никогда не будет гарантии того, «правильно» ли реализована плавающая точка, или вы всегда будете получать определенную точность для данного вычисления, но, возможно, вы могли бы сделать наилучшее усилие за счет (1) усечения всех вычислений до общего минимума (например, если разные реализации дадут вам точность от 32 до 80 бит, всегда обрезая каждую операцию до 30 или 31 бита), (2) иметь таблицу из нескольких тестов случаи при запуске (пограничные случаи сложения, вычитания, умножения, деления, sqrt, косинуса и т. д.), и если реализация вычисляет значения, соответствующие таблице, то не стоит вносить какие-либо корректировки.

Answer 10

Ваш вопрос в довольно сложных и технических вещах О_о. Однако у меня может быть идея.

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

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

«Ошибки», допущенные при корректировке округления, будут увеличиваться при каждой дальнейшей инструкции.

В качестве примера можно сказать, что на уровне сборки: a * b * c не эквивалентен a * c * b.

Я не совсем уверен в этом, вам нужно будет попросить кого-то, кто знает архитектуру процессора намного больше меня: p

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

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

Надеюсь, я достаточно ясно, я не совершенен в английском (... вообще: s)