Умножение с плавающей запятой по сравнению с несколькими сложениями

Обозначения и предпосылки

a обозначает математическое число. a обозначает значение с плавающей запятой. 3a обозначает математическое выражение (с использованием арифметики действительных чисел). a+a+a и 3*a обозначают выражения, использующие арифметику с плавающей запятой.

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

Конечные, нормальные значения

В двоичном формате с плавающей запятой, если a является представимым, а 2a находится в пределах конечного диапазона, то 2a является представимым, поскольку единственный разница в их представлениях заключается в показателе степени. Следовательно, если задано число с плавающей запятой a, представляющее число a, результатом a+a будет ровно 2a. Тогда результат с плавающей запятой a+a+a (то есть (a+a)+a) является математическим результатом 3a (поскольку математический результат равен 2a+a ) округляется до ближайшего представимого значения. И результат с плавающей запятой 3*a также является математическим результатом 3a, округленным до ближайшего представимого значения. Следовательно, a+a+a и 3*a имеют одинаковый результат с плавающей запятой, и равенство сохраняется.

Особые случаи

Осталось рассмотреть частные случаи.

Если a, представляющее a, конечно, но 2a превышает диапазон, для которого результат с плавающей запятой конечен, то a+a дает бесконечность, а a+a+a дает то же самое. бесконечность, как и 3*a, так что равенство выполняется.

Если a — бесконечность, то a+a, a+a+a и 3*a дают одну и ту же бесконечность, и равенство выполняется.

Если a — это NaN, то a+a+a и 3*a оба являются NaN, и они не равны при сравнении, потому что два NaN никогда не бывают числами с одинаковыми значениями.

Сноска

¹ В вопросе не указана используемая система с плавающей запятой. Конечно, можно определить систему с плавающей запятой, в которой 1+1 дает 0, а 0+1 дает 0, а 3*1 дает 5. Однако для целей этого ответа мы предполагаем типичную систему с плавающей запятой.

Вы не указали формат, IEEE 754 популярен, но не единственный зверь.

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

Так что, как правило, не думайте, что это сработает, но в этом конкретном случае давайте начнем с формата 1.fraction в стиле IEEE, нам не нужно очень много битов мантиссы, чтобы увидеть, как это работает.

1.abc (a,b,c — одиночные биты)

Как указывает Эрик, начните с 2*a

  1abc
+ 1abc
========
 1xxx0

независимо от того, что такое c, 1 или 0, lsbit равен 0. фиксированная точка 1abc+1abc = 2*1abc, пока мы не переполняем экспоненту:

  1abc
+ 1abc
========
 1abc0

вы можете просмотреть комбинации и количество битов мантиссы, если хотите.

добавление a+a+a подходит к этому моменту

 1abc0
+ 1abc
=======

для случая умножения

    1abc
    1100
  ====== 
    0000
   0000
  1abc
+1abc
===========

что приходит к этому моменту

   1abc
+ 1abc0
========

так что они заканчиваются там же, где и равны, да?

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

Отрицательные числа в IEEE, например, также используют положительный формат 1.f, а знак обрабатывается отдельно. В этом случае путь умножения p * p положительный p * n отрицательный, поэтому оба пути работают, вы сохраняете знак (3 здесь всегда положительный). Для пути сложения результаты либо становятся более отрицательными, либо более положительными, они сохраняют свой знак.

Первое добавление может привести к переполнению экспоненты, что может привести, например, к NAN в IEEE. Второе дополнение, та же история. Умножение также может привести к NAN, и лучше всего предположить, что по двум путям два результата NAN не равны в двоичном виде, поэтому сравнение не будет работать. Если я правильно помню, один будет сигнальным, а другой тихим, да?

Другие форматы. Все еще работая над этим, должно быть так же легко продемонстрировать, как формат(ы) типа 1.f. положительная 01.фракция, отрицательная 10.фракция, например.

Ключевым моментом здесь является то, что реализация умножения должна быть такой, чтобы поддерживать 2n необходимых битов (для фиксированной точки n битов * n битов = 2n битов будет охватывать все случаи 32-битного числа, умноженного на Для хранения 32-битного числа требуется 64 бита.) Форматы, стремящиеся поставить единицу вверху значения, означают, что вы умножаете 1xxxxx... * 1xxxxx.... из начальной школы

a.bcd
e.fgh
======

Мы бы сделали математику как фиксированную точку abcd * efgh, а затем автоматически переместили бы десятичную точку 6 в результате. Затем двоичную плавающую точку нужно будет нормализовать и переместить наиболее значащую 1 или 0 в зависимости от формата сразу слева от двоичной точки, регулируя показатель степени, подобно тому, как мы использовали бы степени 10 в экспоненциальном представлении для дальнейшей корректировки результата. . В идеале логика будет использовать достаточно битов, чтобы математика с фиксированной точкой работала правильно, затем нормализовать ее, затем обрезать и, возможно, округлить.

Итак, в конце дня вы увидите что-то вроде

     abcd
    abcd
   abcd
  abcd
+ ...

И для случая 3*a vs a+a+a

в лучшем случае держите c как липкий бит

 1abc0
+ 1abc
=======
 xxxxx

в худшем случае обрезать

 1abc0
+ 1abc
=======
 xxxx  

для умножения

лучший случай

    0000
   0000
  1abc
+1abc
===========
 xxxxxxx`

отсечение в худшем случае

    0 
   00 
  1ab 
+1abc
===========
 xxxx`

В обоих случаях мы сохраняем/теряем один бит, который по обоим путям дает один и тот же результат, если и сложение, и умножение делают одинаковые оптимизации. Это относится только к 3*a против a+a+a, пришлось бы перебирать возможности для любого другого уравнения.

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

Предположите один из способов, а затем будьте счастливы, если это не так, даже лучше, если вы можете доказать, что это не так (для вашего конкретного целевого оборудования или формата в целом), а затем помнить и документировать ограничения этого доказательства. Если вы забудете доказательство или не задокументируете правила, позже кто-то придет и напортачит, и математика может быть неправильной, и программа не будет работать. Так что будьте очень-очень осторожны, выполняя математические оптимизации, не задумываясь о них. В частности, если вы ожидаете, что сравнение на равенство будет работать.

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