ассоциативности математика: (а + Ь) + с = а + (Ь + с)

Question

Недавно я шел через old blog post by Eric Lippert , в котором, в то время писал о ассоциативности он упоминает, что в C#, (a + b) + c не эквивалентен a + (b + c) для некоторые значения a, b, c.

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

Answer 1

В диапазоне типа 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, в противном случае компилятор даст ошибку напрямую ... Технически даже это будет другим результатом :-) Compiles cor rectly против не компилируется)

это бросает OverflowException ... Результаты разные :-) (int.MaxValue против Exception)

Answer 2

один пример

a = 1e-30 
b = 1e+30 
c = -1e+30 

Answer 3

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

В этом случае вместо чисел с предельными пределами точности я просто делаю много дополнений. Разница между (((...(((a+b)+c)+d)+e)... или ...(((a+b)+(c+d))+((e+f)+(g+h)))+...

Я использую python здесь, но вы, вероятно, получите те же результаты, если вы напишете это на C#. Сначала создайте список из миллиона значений, каждый из которых равен 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] 

А вот простой pair_sum написанный на C#:

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 

Answer 4

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

В C# можно использовать BigInteger, чтобы избежать такого рода проблем. BigInteger произвольны по размеру и поэтому не создают переполнения.

BigInteger доступен только для .NET 4.0 и выше (VS 2010+).

Answer 5

Короткий ответ (a + b) + c == a + (b + c) математически, но не обязательно вычислительно.

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

В зависимости от языка даже добавление может привести к ошибкам округления, и в приведенном выше примере ошибка округления в a+b может отличаться от ошибки в b+c.

Одним из удивительных правонарушителей является JavaScript: 0.1 + 0.2 != 0.3. Ошибка округления - это долгий путь вниз по десятичной, но реальной и проблематичной.

Это общая рекомендация, что вы уменьшаете ошибку округления, добавляя сначала мелкие детали. Таким образом, они могут накапливаться до того, как их перегрузит большее количество.

Answer 6

Несколько подобных примеров:

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.