Вычислительная машина должна вычислять

[spamsink]

Загадка для программистов (не для математиков, потому что числа с плавающей точкой выше их понимания):

Пусть T - некий тип чисел с плавающей точкой, и a, b, s, t, z - переменные типа Т.

Дана последовательность операторов

s := a + b
z := s - a
t := b - z


Чему равно t?

Познавательная статья о том, как делаются вычисления с плавающей точкой с двойной точностью, включая формальные оценки.

Comments

[sab123]

Видимо, где-то между 0 и старшим разрядом a?

[spamsink]

Можно точнее. :)

[sab123]

Вроде если b > a, причем как раз настолько, чтобы старший разряд a был младшим разрядом b, то в z может оказаться +-1 из старшего разряда a. Или не может?

[spamsink]

Идея в том, чтобы (s+t) было математически равно (a+b), т. е. в t находится ошибка округления s по отношению к a+b. Последовательность операций верна для |a| >= |b|, иначе t может быть само округлено - или к нулю (пример очевиден), или к следующей степени двойки по абсолютной величине (что ты и имеешь в виду, но живой пример хотелось бы увидеть, если он найдется).

От компилятора зависит

[malobukov]

Оптимизирующий компилятор вполне может выполнить роль математика и упростить всё до нуля.

Re: От компилятора зависит

[spamsink]

Вроде нет. Например, GCC 7.3.0 с -O5 из

double f(double a, double b) {
    double s = a + b;
    double z = s - a;
    return b - z;
}

делает

	movapd	%xmm0, %xmm2
	addsd	%xmm1, %xmm2
	subsd	%xmm0, %xmm2
	subsd	%xmm2, %xmm1
	movapd	%xmm1, %xmm0
        ret

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

Re: От компилятора зависит

[malobukov]

Я поэтому и сказал «может». Если ему ключик -Ofast дать.

Re: От компилятора зависит

[spamsink]

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

Как зачем?

[malobukov]

Чтоб быстрее было. Само название ключика намекает.

Re: Как зачем?

[spamsink]

Когда подобную последовательность вычислений пишут, то обычно знают, что поспешишь - людей насмешишь. :)

Возможны варианты

[malobukov]

Такая последовательность может получиться после раскрытия темплейтов, инлайн функций или даже макросов, не к ночи будь помянуты. И ноль вполне правильный ответ, хоть и не соответствует стандарту.

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

Re: Возможны варианты

[spamsink]

В вопросе речь не идет ни о каком языке программирования.

[juan_gandhi]

Предполагая, что нету NaN, +=Infinity.

Между 0 и b (ну или между -b и 0)?

Эх... Ведь не сделать же число больше по модулю, чем b?

[spamsink]

Не сделать. А если |a| >= |b|, то ответ формулируется более точно.

[juan_gandhi]

Кстати, зависит же от вида округления (их же четыре)

[spamsink]

Строго говоря, зависит, но по умолчанию у нас округление - округление.

Кстати, знаменитая в свое время в определенных кругах программа PARANOIA правильно определяет основание и точность плавающей точки при трёх из четырех видов округления, а при округлении вверх (fesetround(FE_UPWARD)) с ума сходит.

[yurikhan]

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

Крайние случаи:

• Если a ≪ b, то s = b, z = b и t = 0.
• Если b ≪ a, то s = a, z = 0 и t = b. Вроде бы.

В промежуточных случаях, если порядки a и b отличаются менее чем на ширину мантиссы:

 Aaaaaaaaaaaa                   Aaaaaaaaaaaa
+      Bbbbbbbbbbbb      +Bbbbbbbbbbbb
=AaaaaaSsssss            =BbbbbbSsssss
-Aaaaaaaaaaaa            -      Aaaaaaaaaaaa
=      Bbbbbb            =Bbbbbbbbbbbb
-      Bbbbbbbbbbbb      -Bbbbbbbbbbbb
=            bbbbbb      =           0±ε

[spamsink]

Отсюда недалеко и до правильного ответа, что если порядок a не меньше порядка b, то t равно разнице между математическим результатом и s.

[pappadeux]

kahan summation?