Является ли IEEE умножение на степень двойки ассоциативным?
Пожалуйста, подтвердите мое понимание плавающих чисел IEEE.
Я считаю, что если у меня есть два числа:
a= 2ea × ma ← «математический ×»b= 2eb× мb
Тогда их произведение a * b побитно идентично ((a * p) * b) / p, где p — степень двойки (предостережение: промежуточные значения не переполняются до бесконечности и не теряют точности в районе показателя -308; то есть это p, удовлетворяющее (a * p) / p = a) .
Насколько я понимаю, a * b (IEEE *) определяется как «ближайшее число с плавающей запятой к математическому значению 2ea+eb × ma × mb» (ближайшее или независимо от того, какой метод округления делает). Это включает в себя умножение мантиссы, а затем сдвиг мантиссы по мере необходимости (например, 1,11111×1,11111 = 11.что-то, чтобы окончательный результат имел показатель ea+eb+1, а мантисса округлялась до количества бит в вещественном числе). .
Все это в основном не зависит от значений ea и eb; мы можем увеличить/уменьшить их как захотим, а затем отменить это, и это не повлияет на конечный продукт.
Следствие:
- Учитывая вектор двойных значений, произведение которых я хочу вычислить, я могу сделать это, установив все их показатели степени на 1023 (путем побитового преобразования) и добавив извлеченные показатели степени с помощью
int. Затем я могу произвести двойные значения, уменьшенные до диапазона ±[1,2), и, наконец, снова повернуть экспоненту (и получить ошибку, если она выходит за пределы диапазона ±1024). Это могло бы помочь в таких случаях, как [1E300, 1E300, 1E-200, 1E-200], когда простой продукт терпит неудачу. А в тех случаях, когда простой продукт будет работать, версия с битовой манипуляцией дает идентичные результаты.
Эээ, что? Умножение IEEE не является ассоциативным. Вам не придется усердно искать контрпримеры. Подумайте об этом немного...
Re: "непонятно, о чем вы спрашиваете". Я спрашиваю, идентичен ли продукт a * b((a * p) * b) / p. Или, говоря иначе, «для операций округления, определенных IEEE, таких как округление до ближайшего, при применении к процедуре определения мантиссы a * b, зависит ли результирующая мантисса от величины показателей степени?» Есть ли случаи, когда (например) aSmall и aBig имеют одинаковую мантиссу, разные показатели степени; и аналогично bSmall, bBig. Всегда ли у aSmall*bSmall и aBig*bBig одна и та же мантисса?
Я почти уверен, что вы правы, за двумя исключениями: денормализованные числа и бесконечности. Бесконечности должны быть ясными. Для денормализованных чисел мантисса изменяется и точность теряется.
Спасибо @Homer512. Я тоже почти уверен... но не на 100%! Вы можете сделать это ответом, если вы более уверены в себе, чем я.
@user207421: user207421: Арифметика с плавающей запятой не является ассоциативной. Арифметика с плавающей запятой не является арифметикой вещественных чисел, и свойства арифметики вещественных чисел к ней обычно не применимы. И IEEE 754 не является языком программирования.
Ответы 1
TLDR: Вы правы
Некоторые предположения
- Мы игнорируем NaN и бесконечности.
- Мы игнорируем денормализованные числа
- Мы предполагаем, что реализация IEEE-754 использует степень 2, а не степень 10.
Тогда каждое нормализованное число с плавающей запятой кодируется как 1.x * 2^y с двоичной мантиссой 1.x и целочисленным показателем y. Таким образом, целая степень 2 кодируется как 1.0 * 2^p. Если мы пренебрегаем битовыми сдвигами для нормализации, умножение реализуется как
(1.x * 2^y) * (1.u * 2^w) == (1.x * 1.u) * 2^(y+w)
И наоборот, деление — это (1.x / 1.u) * 2^(y-w). Следуя этому шаблону, умножение со степенью двойки содержит умножение 1.x * 1.0, которое является тождественной функцией и не может создавать проблемы с ассоциативностью. Сложение y + p для показателя степени является целочисленным сложением, которое является ассоциативным. Следовательно, умножение и деление на степень двойки ассоциативны.
Это неверно, если какой-либо промежуточный результат выходит за пределы целочисленного диапазона показателя степени. Затем результат денормализуется и биты мантиссы округляются.
Где это может быть полезно?
Это означает, что вы можете заменить любое (относительно дорогое) деление на степень 2 умножением на обратное без потери точности. Для констант времени компиляции компиляторы сделают это автоматически.
Часто бывает полезно нормализовать числа. Например, при вычислении нормы вектора L2 (sqrt(x^2 + y^2 + …)) полезно определить коэффициент масштабирования s = max(abs({x, y, …})) и вычислить s * sqrt((x/s)^2 + (y/s)^2 + …), чтобы избежать чрезмерного или недостаточного значения промежуточного возведения в квадрат.
Если вместо этого мы округлим s до степени, близкой к 2, ошибок округления не будет, и деление можно будет превратить в умножение. Для выбора коэффициента можно использовать стандартные математические функции frexp и ldexp.
дальнейшее чтение
Книга Голдберга Что должен знать каждый ученый-компьютерщик об арифметике с плавающей запятой содержит теорему 7, которая связана с ней. Он также содержит простое примечание: «Масштабирование в степени 2 является безвреден, поскольку меняет только показатель степени, а не значимость», что подтверждает нашу оценку.
Умножение ассоциативно. Если IEEE 754 или любой другой язык программирования считает иначе, это неправильно по определению. Непонятно, что вы на самом деле здесь спрашиваете.