Moyenne de 3 longs entiers

J'ai 3 très grands 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, ce qui est 9223372036854775806.

Il est impossible de le calculer comme:

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

Remarque: 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 me 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 me convertis en decimal, cela fonctionne, mais supposons également 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 entiers uniquement avec l'utilisation de longtype? Ne considérez pas cette question comme spécifique à C #, mais il m'est plus facile de fournir des exemples en C #.

Ce code fonctionnera, mais n'est pas si joli.

Il divise d'abord les trois valeurs (il nivelle les valeurs, vous «perdez» donc le reste), puis 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 a une ou plusieurs valeurs négatives.

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

Grâce aux réponses et aux commentaires d' Ulugbek Umirov , James S , KevinZ , Marc van Leeuwen , gnasher729 , voici 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);
}

NB - Patrick a déjà donné une excellente réponse . En développant là-dessus, vous pouvez créer 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;

Patrick Hofman a publié une excellente solution . Mais si nécessaire, il peut toujours être mis en œuvre de plusieurs autres manières. En utilisant l'algorithme ici, j'ai une autre solution. S'il est mis en œuvre avec soin, il peut être plus rapide que les multiples divisions dans les systèmes avec des diviseurs matériels lents. Il peut être encore optimisé en utilisant la technique de division par constantes du plaisir des hackers

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 plates-formes 64 bits, c'est beaucoup plus facile avec __int128

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

Vous pouvez calculer la moyenne des nombres en fonction des 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édian 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));
}

Étant donné que C utilise la division par étage plutôt que la division euclidienne, il peut être plus facile de calculer une moyenne correctement arrondie de trois valeurs non signées que de trois signées. Ajoutez simplement 0x8000000000000000UL à chaque nombre avant de prendre la moyenne non signée, soustrayez-la après avoir pris le résultat et utilisez une conversion non cochée vers Int64pour obtenir une moyenne signée.

Pour calculer la moyenne non signée, calculez la somme des 32 premiers bits des trois valeurs. Ensuite, calculez la somme des 32 bits inférieurs des trois valeurs, plus la somme d'en haut, plus un [le plus un donne un résultat arrondi]. La moyenne sera 0x55555555 fois la première somme, plus un tiers de la seconde.

Les performances sur les processeurs 32 bits peuvent être améliorées en produisant trois valeurs "somme" dont chacune est longue de 32 bits, de sorte que le résultat final est ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; il pourrait éventuellement être amélioré en remplaçant sumL/3par ((sumL * 0x55555556UL) >> 32), bien que ce dernier dépende de l'optimiseur JIT [il pourrait savoir comment remplacer une division par 3 par une multiplication, et son code pourrait en fait être plus efficace qu'une opération de multiplication explicite].

Patcher Patrick Hofman 'solution s avec supercat ' correction de, je vous donne les éléments suivants:

static Int64 Avg3 ( Int64 x, Int64 y, Int64 z )
{
    UInt64 flag = 1ul << 63;
    UInt64 x_ = flag ^ (UInt64) x;
    UInt64 y_ = flag ^ (UInt64) y;
    UInt64 z_ = flag ^ (UInt64) z;
    UInt64 quotient = x_ / 3ul + y_ / 3ul + z_ / 3ul
        + ( x_ % 3ul + y_ % 3ul + z_ % 3ul ) / 3ul;
    return (Int64) (quotient ^ flag);
}

Et le cas des N éléments:

static Int64 AvgN ( params Int64 [ ] args )
{
    UInt64 length = (UInt64) args.Length;
    UInt64 flag = 1ul << 63;
    UInt64 quotient_sum = 0;
    UInt64 remainder_sum = 0;
    foreach ( Int64 item in args )
    {
        UInt64 uitem = flag ^ (UInt64) item;
        quotient_sum += uitem / length;
        remainder_sum += uitem % length;
    }

    return (Int64) ( flag ^ ( quotient_sum + remainder_sum / length ) );
}

Cela donne toujours le plancher () de la moyenne et élimine tous les cas de bord possibles.

Vous pouvez utiliser le fait que vous pouvez écrire chacun des nombres comme y = ax + b, où xest une constante. Chacun aserait 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 des xnombres 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 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 );
    }
}

Si vous savez que vous avez N valeurs, pouvez-vous simplement diviser chaque valeur par N et les additionner?

long GetAverage(long* arrayVals, int n)
{
    long avg = 0;
    long rem = 0;

    for(int i=0; i<n; ++i)
    {
        avg += arrayVals[i] / n;
        rem += arrayVals[i] % n;
    }

    return avg + (rem / n);
}

Je l'ai également essayé et j'ai trouvé une solution plus rapide (bien que seulement d'un facteur 3/4). Il utilise une seule division

public static long avg(long a, long b, long c) {
    final long quarterSum = (a>>2) + (b>>2) + (c>>2);
    final long lowSum = (a&3) + (b&3) + (c&3);
    final long twelfth = quarterSum / 3;
    final long quarterRemainder = quarterSum - 3*twelfth;
    final long adjustment = smallDiv3(lowSum + 4*quarterRemainder);
    return 4*twelfth + adjustment;
}

où smallDiv3est la division par 3 en utilisant la multiplication et en travaillant uniquement pour les petits arguments

private static long smallDiv3(long n) {
    assert -30 <= n && n <= 30;
    // Constants found rather experimentally.
    return (64/3*n + 10) >> 6;
}

Voici l' ensemble du code comprenant un test et un benchmark, les résultats ne sont pas si impressionnants.

Cette fonction calcule le résultat en deux divisions. Il devrait bien se généraliser à d'autres diviseurs et tailles de mots.

Il fonctionne en calculant le résultat de l'addition de deux mots, puis en élaborant la division.

Int64 average(Int64 a, Int64 b, Int64 c) {
    // constants: 0x10000000000000000 div/mod 3
    const Int64 hdiv3 = UInt64(-3) / 3 + 1;
    const Int64 hmod3 = UInt64(-3) % 3;

    // compute the signed double-word addition result in hi:lo
    UInt64 lo = a; Int64 hi = a>=0 ? 0 : -1;
    lo += b; hi += b>=0 ? lo<b : -(lo>=UInt64(b));
    lo += c; hi += c>=0 ? lo<c : -(lo>=UInt64(c));

    // divide, do a correction when high/low modulos add up
    return hi>=0 ? lo/3 + hi*hdiv3 + (lo%3 + hi*hmod3)/3
                 : lo/3+1 + hi*hdiv3 + Int64(lo%3-3 + hi*hmod3)/3;
}

Math

(x + y + z) / 3 = x/3 + y/3 + z/3

(a[1] + a[2] + .. + a[k]) / k = a[1]/k + a[2]/k + .. + a[k]/k

Code

long calculateAverage (long a [])
{
    double average = 0;

    foreach (long x in a)
        average += (Convert.ToDouble(x)/Convert.ToDouble(a.Length));

    return Convert.ToInt64(Math.Round(average));
}

long calculateAverage_Safe (long a [])
{
    double average = 0;
    double b = 0;

    foreach (long x in a)
    {
        b = (Convert.ToDouble(x)/Convert.ToDouble(a.Length));

        if (b >= (Convert.ToDouble(long.MaxValue)-average))
            throw new OverflowException ();

        average += b;
    }

    return Convert.ToInt64(Math.Round(average));
}

Essaye ça:

long n = Array.ConvertAll(new[]{x,y,z},v=>v/3).Sum()
     +  (Array.ConvertAll(new[]{x,y,z},v=>v%3).Sum() / 3);