Promedio de 3 enteros largos

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: Leí todas esas preguntas sobre el promedio de 2 números, pero no veo cómo se puede aplicar esa técnica al 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 me convierto a 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 de longtipo? No considere esa pregunta como específica de C #, solo que es más fácil para mí proporcionar ejemplos en C #.

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

Primero divide los tres valores (reduce 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 el ejemplo anterior no siempre funciona correctamente cuando tiene uno o más valores negativos.

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

Gracias a las respuestas y comentarios de Ulugbek Umirov , 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);
}

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

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 ha publicado una gran solución . Pero si es necesario, aún se puede implementar de varias otras formas. Usando el algoritmo aquí 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 de los piratas informáticos.

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;

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 tienes). Los llamaremos max, median y min.

Verificador condicional agregado 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));
}

Debido a que C usa la división en suelo en lugar de la división euclidiana, puede ser más fácil calcular un promedio correctamente redondeado de tres valores sin signo que con tres valores con signo. Simplemente agregue 0x8000000000000000UL a cada número antes de tomar el promedio sin firmar, réstelo después de tomar el resultado y use una conversión sin marcar para Int64obtener un promedio con signo.

Para calcular el promedio sin signo, calcule la suma de los 32 bits superiores 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 obtener un resultado redondeado]. El promedio será 0x55555555 veces la primera suma, más un tercio de la segunda.

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

Parcheando la solución de Patrick Hofman con la corrección de supercat , les doy lo siguiente:

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.

Podrías usar el hecho de que puedes escribir cada uno de los números como y = ax + b, donde xes una constante. Cada uno aserí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 manera inteligente, por ejemplo, eligiendo la raíz cuadrada del número máximo como constante, puede obtener el promedio de xnúmeros sin tener problemas de desbordamiento.

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

( ( 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 así:

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 sabe que tiene N valores, ¿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);
}

También lo probé y se me ocurrió 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 smallDiv3es la división por 3 usando la multiplicació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á el código completo, incluida una prueba y un punto de referencia, los resultados no son tan impresionantes.

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

Funciona calculando el resultado de la suma de dos palabras y luego calculando 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;
}

Matemáticas

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

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