c# - tipos - Promedio de 3 enteros largos

tipos de datos y su tamaño en bytes

Question

Tengo 3 enteros con signo muy grandes.

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

Quiero calcular su promedio truncado. El valor promedio esperado es long.MaxValue - 1 , que es 9223372036854775806 .

Es imposible calcularlo como:

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

Nota: leo todas esas preguntas sobre el promedio de 2 números, pero no veo cómo se puede aplicar esa técnica a un promedio de 3 números.

Sería muy fácil con el uso de BigInteger , pero supongamos que no puedo usarlo.

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

Si cambio al double , entonces, por supuesto, pierdo precisión:

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

Si convierto a decimal , funciona, pero también supongamos que no puedo usarlo.

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

Pregunta: ¿Hay alguna manera de calcular el promedio truncado de 3 enteros muy grandes solo con el uso del tipo long ? No considere esa pregunta como específica de C #, solo que es más fácil para mí proporcionar muestras en C #.

Answer 1

Como C usa la división con piso en lugar de la división euclidiana, es más fácil calcular un promedio redondeado de tres valores sin firmar que tres firmados. Simplemente agregue 0x8000000000000000UL a cada número antes de tomar el promedio sin firmar, restelo después de tomar el resultado, y use un lanzamiento desactivado de nuevo a Int64 para obtener un promedio firmado.

Para calcular el promedio sin signo, calcule la suma de los 32 mejores bits de los tres valores. Luego calcule la suma de los 32 bits inferiores de los tres valores, más la suma de arriba, más uno [el más uno es para dar un resultado redondeado]. El promedio será 0x55555555 veces la primera suma, más un tercio del segundo.

El rendimiento en procesadores de 32 bits podría mejorarse produciendo tres valores de "suma", cada uno de los cuales tiene 32 bits de longitud, de modo que el resultado final sea ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3 ; posiblemente podría mejorarse aún más reemplazando sumL/3 con ((sumL * 0x55555556UL) >> 32) , aunque esto último dependería del optimizador JIT [podría saber cómo reemplazar una división por 3 con un multiplicador, y su código en realidad podría ser más eficiente que una operación de multiplicación explícita].

Answer 2

Esta función calcula el resultado en dos divisiones. Debería generalizarse muy bien a otros divisores y tamaños de palabra.

Funciona al calcular el resultado de la adición de doble palabra y luego calcular la división.

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

Answer 3

Este código funcionará, pero no es tan bonito.

En primer lugar, divide los tres valores (limita los valores, por lo que ''pierde'' el resto), y luego divide el resto:

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

Tenga en cuenta que la muestra anterior no siempre funciona correctamente cuando tiene uno o más valores negativos.

Como se discutió con Ulugbek, dado que el número de comentarios está explotando a continuación, aquí está la solución MEJOR actual para los valores positivos y negativos.

Gracias a las respuestas y comentarios de , James S , KevinZ , Marc van Leeuwen , gnasher729 esta es la solución actual:

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 4

NB - Patrick ya ha dado una gran respuesta . Ampliando esto, podría hacer una versión genérica para cualquier número de enteros como ese:

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 5

Patrick Hofman ha publicado una gran solución . Pero si es necesario, todavía se puede implementar de varias otras maneras. Usando el algoritmo here tengo otra solución. Si se implementa con cuidado, puede ser más rápido que las divisiones múltiples en sistemas con divisores de hardware lentos. Se puede optimizar aún más utilizando la técnica de dividir por constantes del deleite del hacker

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 ++ en plataformas de 64 bits es mucho más fácil con __int128

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

Answer 6

Podría usar el hecho de que puede escribir cada uno de los números como y = ax + b , donde x es una constante. Cada a sería y / x (la parte entera de esa división). Cada b sería y % x (el resto / módulo de esa división). Si elige esta constante de forma inteligente, por ejemplo, eligiendo la raíz cuadrada del número máximo como una constante, puede obtener el promedio de x números sin tener problemas con el desbordamiento.

El promedio de una lista arbitraria de números se puede encontrar al encontrar:

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

donde % denota módulo y / denota la parte "completa" de la división.

El programa se vería algo así como:

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

Answer 7

Prueba esto:

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

Answer 8

Puede calcular la media de los números basándose en las diferencias entre los números en lugar de usar la suma.

Digamos que x es el máximo, y es la mediana, z es el mínimo (como lo has hecho). Los llamaremos max, mediana y min.

Se agregó un verificador condicional según el comentario 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 9

Revisando la solución de con la corrección de supercat , le doy la siguiente información:

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

Y el caso del elemento 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 ) );
}

Esto siempre da el piso () de la media, y elimina todos los casos de borde posibles.

Answer 10

Si sabe que tiene valores N, ¿puede simplemente dividir cada valor entre N y sumarlos?

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

Answer 11

También probé y presenté una solución más rápida (aunque solo por un factor de aproximadamente 3/4). Utiliza una sola división

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

donde smallDiv3 es división por 3 usando multipliación y trabajando solo para pequeños argumentos

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

Aquí está todo el código que incluye una prueba y un punto de referencia, los results no son tan impresionantes.

Answer 12

Mates

(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

Código

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