Moyenne de 3 entiers longs

Question

J'ai 3 très grands nombres entiers signés.

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

Je veux calculer leur moyenne tronquée. La valeur moyenne attendue est long.MaxValue - 1 qui est 9223372036854775806 .

Il est impossible de le calculer comme :

long avg = (x + y + z) / 3; // 3074457345618258600

Note : J'ai lu toutes ces questions sur la moyenne de 2 nombres, mais je ne vois pas comment cette technique peut être appliquée à la moyenne de 3 nombres.

Ce serait très facile avec l'utilisation de BigInteger mais supposons que je ne puisse pas l'utiliser.

BigInteger bx = new BigInteger(x);
BigInteger by = new BigInteger(y);
BigInteger bz = new BigInteger(z);
BigInteger bavg = (bx + by + bz) / 3; // 9223372036854775806

Si je convertis en double alors, bien sûr, je perds la précision :

double dx = x;
double dy = y;
double dz = z;
double davg = (dx + dy + dz) / 3; // 9223372036854780000

Si je convertis en decimal supposons que cela fonctionne, mais supposons aussi que je ne puisse pas l'utiliser.

decimal mx = x;
decimal my = y;
decimal mz = z;
decimal mavg = (mx + my + mz) / 3; // 9223372036854775806

Question : Existe-t-il un moyen de calculer la moyenne tronquée de 3 très grands nombres entiers uniquement avec l'utilisation de long type ? Ne considérez pas cette question comme spécifique à C#, mais il est plus facile pour moi de fournir des exemples en C#.

Answer 1

Ce code fonctionnera, mais il n'est pas très joli.

Il divise d'abord les trois valeurs (il les met à plat, ce qui fait que vous "perdez" le reste), puis il divise le reste :

long n = x / 3
         + y / 3
         + z / 3
         + ( x % 3
             + y % 3
             + z % 3
           ) / 3

Notez que l'exemple ci-dessus ne fonctionne pas toujours correctement lorsqu'il y a une ou plusieurs valeurs négatives.

Comme discuté avec Ulugbek, puisque le nombre de commentaires explose ci-dessous, voici la MEILLEURE solution actuelle pour les valeurs positives et négatives.

Merci aux réponses et commentaires de Ulugbek Umirov , James S , KevinZ , Marc van Leeuwen , gnasher729 c'est la solution actuelle :

static long CalculateAverage(long x, long y, long z)
{
    return (x % 3 + y % 3 + z % 3 + 6) / 3 - 2
            + x / 3 + y / 3 + z / 3;
}

static long CalculateAverage(params long[] arr)
{
    int count = arr.Length;
    return (arr.Sum(n => n % count) + count * (count - 1)) / count - (count - 1)
           + arr.Sum(n => n / count);
}

Answer 2

NB - Patrick a déjà donné une grande réponse . En développant ceci, vous pourriez faire une version générique pour n'importe quel nombre d'entiers comme ceci :

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

long[] arr = { x, y, z };
var avg = arr.Select(i => i / arr.Length).Sum() 
        + arr.Select(i => i % arr.Length).Sum() / arr.Length;

Answer 3

Vous pouvez calculer la moyenne de nombres en vous basant sur les différences entre les nombres plutôt qu'en utilisant la somme.

Disons que x est le maximum, y est la médiane, z est le minimum (comme vous l'avez fait). Nous les appellerons max, médiane et min.

Vérificateur conditionnel ajouté selon le commentaire de @UlugbekUmirov :

long tmp = median + ((min - median) / 2);            //Average of min 2 values
if (median > 0) tmp = median + ((max - median) / 2); //Average of max 2 values
long mean;
if (min > 0) {
    mean = min + ((tmp - min) * (2.0 / 3)); //Average of all 3 values
} else if (median > 0) {
    mean = min;
    while (mean != tmp) {
        mean += 2;
        tmp--;
    }
} else if (max > 0) {
    mean = max;
    while (mean != tmp) {
        mean--;
        tmp += 2;
    }
} else {
    mean = max + ((tmp - max) * (2.0 / 3));
}

Answer 4

Patrick Hofman a a posté une excellente solution . Mais si nécessaire, il peut encore être mis en œuvre de plusieurs autres façons. Utilisation de l'algorithme ici J'ai une autre solution. Si elle est mise en œuvre avec soin, elle peut être plus rapide que les divisions multiples dans les systèmes avec des diviseurs matériels lents. Elle peut être encore optimisée en utilisant diviser par des constantes technique du hacker's delight

public class int128_t {
    private int H;
    private long L;

    public int128_t(int h, long l)
    {
        H = h;
        L = l;
    }

    public int128_t add(int128_t a)
    {
        int128_t s;
        s.L = L + a.L;
        s.H = H + a.H + (s.L < a.L);
        return b;
    }

    private int128_t rshift2()  // right shift 2
    {
        int128_t r;
        r.H = H >> 2;
        r.L = (L >> 2) | ((H & 0x03) << 62);
        return r;
    }

    public int128_t divideby3()
    {
        int128_t sum = {0, 0}, num = new int128_t(H, L);
        while (num.H || num.L > 3)
        {
            int128_t n_sar2 = num.rshift2();
            sum = add(n_sar2, sum);
            num = add(n_sar2, new int128_t(0, num.L & 3));
        }

        if (num.H == 0 && num.L == 3)
        {
            // sum = add(sum, 1);
            sum.L++;
            if (sum.L == 0) sum.H++;
        }
        return sum; 
    }
};

int128_t t = new int128_t(0, x);
t = t.add(new int128_t(0, y));
t = t.add(new int128_t(0, z));
t = t.divideby3();
long average = t.L;

En C/C++ sur les plateformes 64 bits, c'est beaucoup plus facile avec __int128

int64_t average = ((__int128)x + y + z)/3;

Answer 5

Tu pourrais utiliser le fait que tu peux écrire chacun des nombres sous forme de y = ax + b où x est une constante. Chaque a serait y / x (la partie entière de cette division). Chaque b serait y % x (le reste/modulo de cette division). Si vous choisissez cette constante de manière intelligente, par exemple en choisissant la racine carrée du nombre maximum comme constante, vous pouvez obtenir la moyenne de x sans avoir de problèmes de débordement.

La moyenne d'une liste arbitraire de nombres peut être trouvée en trouvant :

( ( sum( all A's ) / length ) * constant ) + 
( ( sum( all A's ) % length ) * constant / length) +
( ( sum( all B's ) / length )

où % désigne un modulo et / désigne la partie "entière" de la division.

Le programme ressemblerait à quelque chose comme :

class Program
{
    static void Main()
    {
        List<long> list = new List<long>();
        list.Add( long.MaxValue );
        list.Add( long.MaxValue - 1 );
        list.Add( long.MaxValue - 2 );

        long sumA = 0, sumB = 0;
        long res1, res2, res3;
        //You should calculate the following dynamically
        long constant = 1753413056;

        foreach (long num in list)
        {
            sumA += num / constant;
            sumB += num % constant;
        }

        res1 = (sumA / list.Count) * constant;
        res2 = ((sumA % list.Count) * constant) / list.Count;
        res3 = sumB / list.Count;

        Console.WriteLine( res1 + res2 + res3 );
    }
}