Mathématiques de l'associativité : (a + b) + c != a + (b + c)

Question

Récemment, j'ai traversé une ancien article de blog d'Eric Lippert dans lequel, tout en écrivant sur l'associativité, il mentionne qu'en C#, (a + b) + c n'est pas équivalent à a + (b + c) pour certaines valeurs de a, b, c.

Je n'arrive pas à comprendre pour les types et la gamme de valeurs arithmétiques Cela pourrait-il être vrai et pourquoi ?

Answer 1

Sur la portée de la double type :

double dbl1 = (double.MinValue + double.MaxValue) + double.MaxValue;
double dbl2 = double.MinValue + (double.MaxValue + double.MaxValue);

Le premier est double.MaxValue le second est double.Infinity

Sur la précision de la double type :

double dbl1 = (double.MinValue + double.MaxValue) + double.Epsilon;
double dbl2 = double.MinValue + (double.MaxValue + double.Epsilon);

Maintenant dbl1 == double.Epsilon , tandis que dbl2 == 0 .

Et en lisant littéralement la question :-)

En checked mode :

checked
{
    int i1 = (int.MinValue + int.MaxValue) + int.MaxValue;
}

i1 es int.MaxValue

checked
{
    int temp = int.MaxValue;
    int i2 = int.MinValue + (temp + temp);
}

(noter l'utilisation de l'abréviation temp sinon le compilateur donnera directement une erreur... Techniquement, ce serait même un résultat différent :-) Compile correctement vs ne compile pas)

ce qui provoque l'apparition d'un OverflowException ... Les résultats sont différents :-) ( int.MaxValue vs Exception )

Answer 2

Un exemple

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

Answer 3

Dans le prolongement des autres réponses qui montrent comment on obtient un résultat différent avec les extrêmes des petits et des grands nombres, voici un exemple où la virgule flottante avec des nombres normaux réalistes donne une réponse différente.

Dans ce cas, au lieu d'utiliser des nombres aux limites extrêmes de la précision, je fais simplement beaucoup d'additions. La différence se situe entre (((...(((a+b)+c)+d)+e)... o ...(((a+b)+(c+d))+((e+f)+(g+h)))+...

J'utilise ici python, mais vous obtiendrez probablement les mêmes résultats si vous écrivez en C#. Créez d'abord une liste d'un million de valeurs, toutes égales à 0,1. Additionnez-les en partant de la gauche et vous verrez que les erreurs d'arrondi deviennent significatives :

>>> numbers = [0.1]*1000000
>>> sum(numbers)
100000.00000133288

Ajoutez-les à nouveau, mais cette fois-ci par paires (il existe des méthodes beaucoup plus efficaces qui utilisent moins de stockage intermédiaire, mais je me suis contenté d'une mise en œuvre simple) :

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

Cette fois, les erreurs d'arrondi sont minimisées.

Editer pour être complet, voici une implémentation plus efficace mais moins facile à suivre d'une somme par paire. Elle donne la même réponse que la méthode pair_sum() ci-dessus :

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]

Et voici le simple pair_sum écrit en 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));
        }
    }
}

avec sortie :

100000.000001333
100000

Answer 4

Cela s'explique par le fait que les types de valeurs ordinaires (int, long, etc.) sont stockés en utilisant un nombre fixe d'octets. Un débordement est donc possible lorsque la somme de deux valeurs dépasse la capacité de stockage en octets.

En C#, on peut utiliser BigInteger pour éviter ce genre de problème. Les BigInteger ont une taille arbitraire et ne créent donc pas de débordements.

BigInteger n'est disponible qu'à partir de .NET 4.0 (VS 2010+).

Answer 5

La réponse courte est (a + b) + c == a + (b + c) sur le plan mathématique, mais pas nécessairement sur le plan informatique.

Si l'on se souvient que les ordinateurs fonctionnent réellement en binaire, même les décimales simples peuvent entraîner des erreurs d'arrondi lorsqu'elles sont converties en format interne.

Selon la langue, même l'addition peut entraîner des erreurs d'arrondi, et dans l'exemple ci-dessus, l'erreur d'arrondi en a+b peut être différente de celle de la b+c .

L'un des contrevenants les plus surprenants est JavaScript : 0.1 + 0.2 != 0.3 . L'erreur d'arrondi est très éloignée de la décimale, mais elle est réelle et problématique.

Un principe général veut que l'on réduise l'erreur d'arrondi en ajoutant d'abord les petites parties. Elles peuvent ainsi s'accumuler avant d'être submergées par le plus grand nombre.