logo标签列表

结合律数学：(a + b) + c != a + (b + c)

c#.netmathnumeric
53

最近我在阅读Eric Lippert的旧博客文章时，他在写关于结合律时提到，在C#中，对于某些a、b和c的值，(a + b) + c并不等同于a + (b + c)。

我无法确定这是否适用于哪些类型和算术值的范围，以及为什么会这样。

32
可能是浮点数值... - xanatos
7
这个问题与C#无关。硬件实现的浮点数运算不完全符合结合律，这不仅限于硬件实现，还包括符合IEEE 754标准的任何浮点数实现。如果需要对类似实数的数字进行结合律运算，您需要发明自己的数据格式（可能需要聘请一位数学家来协助）。 - slebetman
7
任何使用固定有效数字的系统都不具结合律。例如，如果我们只使用一个有效数字，在每次运算后进行四舍五入，则有：(1 + 0.5) + 0.5 == 1.5（四舍五入为2）+ 0.5 == 2.5（四舍五入为3）== 3，而1 + (0.5 + 0.5) == 1 + 1 == 2。IEEE 754标准只是使用了二进制位代替了十进制位，并采用了固定数量的有效二进制位（即尾数）。 - xanatos
3
一条 C# 的问题怎么会是一条 C 语言问题的重复呢？ - user541686
4
@LưuVĩnhPhúc: ...什么？仅仅因为答案（和原因）恰好相同，并不意味着问题是一个重复的问题！实际上，楼主甚至没有提到浮点数。他的问题怎么可能成为与浮点数有关的问题的重复？我希望我可以给评论点个踩... - user541686
显示剩余15条评论
7个回答
78

在 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变量，否则编译器会直接报错...从技术上讲，这甚至会产生不同的结果 :-) 编译正确与无法编译）

这会抛出一个OverflowException...结果是不同的 :-) (int.MaxValue vs Exception)

5
一个非常好的答案；但它谈到了数据类型的范围限制，而问题更多地与数据类型在其范围内的准确性有关。 - Codor
3
@Codor在精度方面添加了一个示例。 - xanatos
也许这个理解起来很困难的原因在于数字的关联和其他属性是理论性的。它们仅适用于范围无限的情况，无论是整数还是实数。因此，如果我们使用宇宙中的每一个原子来表示一个十进制数字，那么我们将使用一个有界的数字系统，其中关联和类似的属性将不适用。 - Fred Mitchell
14

一个例子

a = 1e-30
b = 1e+30
c = -1e+30
10
另一个更令人惊讶的例子是(0.1+0.2)+0.3和0.1+(0.2+0.3)。详情请见http://www.walkingrandomly.com/?p=5380。 - phuclv
3
这种基于精度的错误取决于实现。例如，在运行VS的Win7和运行Mono的Linux上可能会得到不同的结果。甚至可能会没有错误。 - legrojan
@legrojan，除非在内部使用更高精度进行双精度数学计算。 - phuclv
严格来说，我所提供的示例也是实现定义的。在某些实现中，例如使用有理数作为类型，该示例可能会生效。 - Luka Rahne
8

在其他回答中已经展示了极小和极大数字时会得到不同的结果，这里提供一个例子，使用实际正常数字的浮点数也会得到不同的答案。

在这种情况下，我没有使用精度极限的数字，而是进行了很多加法操作。区别在于使用 (((...(((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]

这里是用C#编写的简单pair_sum代码:

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
4
这是因为普通值类型（int、long等）使用固定数量的字节进行存储。当两个值的总和超过字节存储容量时，就可能发生溢出。
在C#中，可以使用BigInteger来避免这种问题。BigInteger的大小是任意的，因此不会造成溢出。
BigInteger仅在.NET 4.0及以上版本（VS 2010+）可用。
2
在有限域中（例如32位算术运算），整数加法是可交换的。 - Luka Rahne
1
@LukaRahne 如果至少有一个单独的总和超过了32位（根据您的示例），那么就会出现问题。在这种情况下，正如xanatos上面所展示的那样，会遇到麻烦。 - legrojan
4
如果进行了“checked”操作，则会发生这种情况。默认情况下，操作不会受到溢出的检查，并且在这种情况下，结合律成立。 - Luka Rahne
0

几个类似的例子：

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;
}

在通常的unchecked模式下，B(2000000000, 2000000000, 42L)导致test1和testX等于-294967254L，而test2变成了4000000042L。

0

简短回答是在数学上(a+b)+c=a+(b+c)，但在计算上不一定成立。

请记住，电脑实际工作的是二进制，甚至一个简单的小数在转换为内部格式时也会导致舍入误差。

根据编程语言的不同，即使加法也可能会产生舍入误差，在上面的示例中，a+b 中的舍入误差可能与b+c 中的误差不同。

令人惊讶的是，JavaScript 就是这个罪魁祸首：0.1+0.2!=0.3。这种舍入误差虽然在小数点后很长时间才出现，但确实存在并且带来问题。

通常我们可以通过先添加小数点后面的小数来减少舍入误差。这样它们就可以在被大数淹没之前累积。

0
在同一博客的评论中，我发现了这个问题：“^”符号在C#中是什么意思？
a = 10 ^ x
b = -a
c = 5
(a+b) + c == 5
a + (b+c) == 0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接