Недавно я проходил через старый пост в блоге Эрика Липперта
в которой при написании об ассоциативности он упоминает, что в С# (a + b) + c не эквивалентен a + (b + c) для определенных значений a, b, c.
Я не могу понять для , какие типы и диапазон арифметических значений могут быть истинными и почему.
В диапазоне типа double:
double dbl1 = (double.MinValue + double.MaxValue) + double.MaxValue;
double dbl2 = double.MinValue + (double.MaxValue + double.MaxValue);
Первый - double.MaxValue, второй - double.Infinity
О точности типа double:
double dbl1 = (double.MinValue + double.MaxValue) + double.Epsilon;
double dbl2 = double.MinValue + (double.MaxValue + double.Epsilon);
Теперь dbl1 == double.Epsilon, а dbl2 == 0.
И буквально прочитав вопрос: -)
В режиме checked:
checked
{
int i1 = (int.MinValue + int.MaxValue) + int.MaxValue;
}
i1 int.MaxValue
checked
{
int temp = int.MaxValue;
int i2 = int.MinValue + (temp + temp);
}
(обратите внимание на использование переменной temp, иначе компилятор даст ошибку напрямую... Технически даже это будет другим результатом:-) Компиляция правильно vs не компилируется)
это выбрасывает OverflowException... Результаты разные:-) (int.MaxValue vs Exception)
один пример
a = 1e-30
b = 1e+30
c = -1e+30
Распространяясь на другие ответы, которые показывают, как с экстремальными значениями малых и больших чисел вы получаете другой результат, вот пример, где плавающая точка с реалистичными нормальными числами дает вам другой ответ.
В этом случае вместо использования чисел в предельных пределах точности я просто делаю много дополнений. Разница заключается в выполнении (((...(((a+b)+c)+d)+e)... или ...(((a+b)+(c+d))+((e+f)+(g+h)))+...
Я использую python здесь, но вы, вероятно, получите те же результаты, если вы напишете это на С#. Сначала создайте список из миллиона значений, каждый из которых равен 0,1. Добавьте их слева, и вы увидите, что ошибки округления становятся значительными:
>>> numbers = [0.1]*1000000
>>> sum(numbers)
100000.00000133288
Теперь добавьте их снова, но на этот раз добавьте их парами (есть гораздо более эффективные способы сделать это, которые используют меньшее промежуточное хранилище, но я сохранил реализацию здесь просто):
>>> def pair_sum(numbers):
if len(numbers)==1:
return numbers[0]
if len(numbers)%2:
numbers.append(0)
return pair_sum([a+b for a,b in zip(numbers[::2], numbers[1::2])])
>>> pair_sum(numbers)
100000.0
В этот раз любые ошибки округления минимизируются.
Изменить полноту, здесь более эффективная, но менее простая в использовании реализация попарной суммы. Он дает тот же ответ, что и pair_sum() выше:
def pair_sum(seq):
tmp = []
for i,v in enumerate(seq):
if i&1:
tmp[-1] = tmp[-1] + v
i = i + 1
n = i & -i
while n > 2:
t = tmp.pop(-1)
tmp[-1] = tmp[-1] + t
n >>= 1
else:
tmp.append(v)
while len(tmp) > 1:
t = tmp.pop(-1)
tmp[-1] = tmp[-1] + t
return tmp[0]
И вот простая пара_сум, написанная на С#:
using System;
using System.Linq;
namespace ConsoleApplication1
{
class Program
{
static double pair_sum(double[] numbers)
{
if (numbers.Length==1)
{
return numbers[0];
}
var new_numbers = new double[(numbers.Length + 1) / 2];
for (var i = 0; i < numbers.Length - 1; i += 2) {
new_numbers[i / 2] = numbers[i] + numbers[i + 1];
}
if (numbers.Length%2 != 0)
{
new_numbers[new_numbers.Length - 1] = numbers[numbers.Length-1];
}
return pair_sum(new_numbers);
}
static void Main(string[] args)
{
var numbers = new double[1000000];
for (var i = 0; i < numbers.Length; i++) numbers[i] = 0.1;
Console.WriteLine(numbers.Sum());
Console.WriteLine(pair_sum(numbers));
}
}
}
с выходом:
100000.000001333
100000
Это связано с тем, что обычные значения типов (int, long и т.д.) хранятся с использованием фиксированного количества байтов. Таким образом, возможно переполнение, когда сумма двух значений превышает емкость хранилища байтов.
В С# можно использовать BigInteger, чтобы избежать такого рода проблем. BigInteger произвольны по размеру и поэтому не создают переполнения.
BigInteger доступен только с .NET 4.0 и выше (VS 2010 +).
Короткий ответ (a + b) + c == a + (b + c) математически, но не обязательно вычисляется.
Помня, что компьютеры действительно работают в двоичном формате, даже простые десятичные знаки могут приводить к ошибкам округления при преобразовании во внутренний формат.
В зависимости от языка даже добавление может приводить к ошибкам округления, и в приведенном выше примере ошибка округления в a+b может отличаться от ошибки в b+c.
Одним неожиданным нарушителем является JavaScript: 0.1 + 0.2 != 0.3. Ошибка округления - это долгий путь вниз по десятичной, но реальной и проблематичной.
Его общий принцип, что вы уменьшаете ошибку округления, сначала добавляя мелкие части. Таким образом, они могут накапливаться до того, как будут перегружены большим числом.
Несколько подобных примеров:
static void A(string s, int i, int j)
{
var test1 = (s + i) + j;
var test2 = s + (i + j);
var testX = s + i + j;
}
Здесь A("Hello", 3, 5) приводит к test1 и testX, равному "Hello35", а test2 будет "Hello8".
и
static void B(int i, int j, long k)
{
var test1 = (i + j) + k;
var test2 = i + (j + k);
var testX = i + j + k;
}
Здесь B(2000000000, 2000000000, 42L) приводит к test1 и testX, равному -294967254L в обычном режиме unchecked, тогда как test2 становится 4000000042L.