Moyenne de 3 entiers longs

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 à une 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 en précision:

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

Si je convertis en decimal , 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: Y a t-il un moyen de calculer la moyenne tronquée de 3 entiers très grands uniquement avec l’utilisation de type long ? Ne considérez pas cette question comme spécifique à C #, mais il est plus facile pour moi de fournir des échantillons en C #.

Ce code fonctionnera, mais n’est-ce pas joli?

Il divise d’abord les trois valeurs (il met les valeurs en ordre, vous «perdez» le rest), puis divise le rest:

 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 avec 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 d’ 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); } 

NB – Pasortingck a déjà donné une excellente réponse . En élargissant cela, vous pouvez faire une version générique pour un nombre quelconque 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; 

Pasortingck Hofman a publié une excellente solution . Mais si nécessaire, il peut encore ê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 divisions multiples des systèmes dotés de diviseurs matériels lents. Il peut être encore optimisé en utilisant la technique de la division par constantes du plaisir des pirates.

 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; sL = L + aL; sH = H + aH + (sL < aL); return b; } private int128_t rshift2() // right shift 2 { int128_t r; rH = H >> 2; rL = (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 = tL; 

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 que d’utiliser la sum.

Disons que x est le max, y la médiane, z le min (comme vous avez). 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)); } 

Comme C utilise la division par étage plutôt que la division euclidienne, il est plus facile de calculer une moyenne correctement arrondie de trois valeurs non signées que trois valeurs 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 un retour non Int64 à Int64 pour obtenir une moyenne signée.

Pour calculer la moyenne non signée, calculez la sum des 32 bits supérieurs des trois valeurs. Ensuite, calculez la sum des 32 bits inférieurs des trois valeurs, plus la sum ci-dessus, plus un [le plus doit produire un résultat arrondi]. La moyenne sera 0x55555555 fois la première sum, plus un tiers de la seconde.

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

Vous pouvez utiliser le fait que vous pouvez écrire chacun des nombres comme 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 rest / modulo de cette division). Si vous choisissez cette constante de manière intelligente, par exemple en choisissant la racine carrée du nombre maximal comme constante, vous pouvez obtenir la moyenne des nombres x sans avoir de problèmes de dépassement.

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 ) 

% dénote modulo et / désigne la partie «entière» de la division.

Le programme ressemblerait à quelque chose comme:

 class Program { static void Main() { List list = new List(); 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 ); } } 

En corrigeant la solution de Pasortingck Hofman avec la correction de supercat , je vous donne les informations suivantes:

 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 de l'élément N:

 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 floor () de la moyenne et élimine tous les cas possibles.

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 

Je l’ai également essayé et trouver une solution plus rapide (mais seulement d’un facteur d’environ 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; } 

smallDiv3 est la division par 3 en utilisant la multiplication et en travaillant uniquement pour de petits arguments

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

Voici le code complet incluant un test et un benchmark, les résultats ne sont pas si impressionnants.

Cette fonction calcule le résultat en deux divisions. Il devrait généraliser aux autres diviseurs et tailles de mots.

Cela fonctionne en calculant le résultat de l’addition de deux mots, puis en travaillant sur 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=UInt64(b)); lo += c; hi += c>=0 ? 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);