Média de 3 inteiros longos

Tenho 3 inteiros com sinal muito grandes.

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

Quero calcular sua média truncada. O valor médio esperado é long.MaxValue - 1, que é 9223372036854775806.

É impossível calculá-lo como:

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

Nota: eu li todas aquelas questões sobre a média de 2 números, mas não vejo como essa técnica pode ser aplicada à média de 3 números.

Seria muito fácil com o uso de BigInteger, mas vamos assumir que não posso usá-lo.

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

Se eu converter para double, é claro, perco a precisão:

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

Se eu converter para decimal, funcionará, mas também vamos supor que não posso usá-lo.

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

Pergunta: Existe uma maneira de calcular a média truncada de 3 inteiros muito grandes apenas com o uso de longtipo? Não considere essa pergunta como específica do C #, apenas é mais fácil para mim fornecer exemplos em C #.

Este código funcionará, mas não é tão bonito.

Ele primeiro divide todos os três valores (reduz os valores, então você 'perde' o restante) e, em seguida, divide o restante:

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

Observe que o exemplo acima nem sempre funciona corretamente quando tem um ou mais valores negativos.

Conforme discutido com Ulugbek, como o número de comentários está explodindo abaixo, aqui está a MELHOR solução atual para valores positivos e negativos.

Graças às respostas e comentários de Ulugbek Umirov , James S , KevinZ , Marc van Leeuwen , gnasher729 , esta é a solução atual:

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 - O Patrick já deu uma ótima resposta . Expandindo isso, você poderia fazer uma versão genérica para qualquer número de inteiros, como:

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 postou uma ótima solução . Mas, se necessário, ainda pode ser implementado de várias outras maneiras. Usando o algoritmo aqui , tenho outra solução. Se implementado com cuidado, pode ser mais rápido do que as várias divisões em sistemas com divisores de hardware lentos. Ele pode ser otimizado ainda mais usando a técnica de divisão por constantes , para o deleite do 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;

Em C / C ++ em plataformas de 64 bits é muito mais fácil com __int128

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

Você pode calcular a média dos números com base nas diferenças entre os números, em vez de usar a soma.

Digamos que x é o máximo, y é a mediana, z é o mínimo (como você fez). Vamos chamá-los de máx., Mediana e mín.

Verificador condicional adicionado de acordo com o comentário 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));
}

Como C usa a divisão com base em vez da divisão euclidiana, pode ser mais fácil calcular uma média corretamente arredondada de três valores sem sinal do que de três valores com sinal. Basta adicionar 0x8000000000000000UL a cada número antes Int64de calcular a média não sinalizada , subtraí-la após obter o resultado e usar um elenco não verificado de volta para obter uma média sinalizada.

Para calcular a média sem sinal, calcule a soma dos 32 bits principais dos três valores. Em seguida, calcule a soma dos 32 bits inferiores dos três valores, mais a soma de cima, mais um [o mais um produzirá um resultado arredondado]. A média será 0x55555555 vezes a primeira soma, mais um terço da segunda.

O desempenho em processadores de 32 bits pode ser aprimorado produzindo três valores de "soma", cada um dos quais com 32 bits de comprimento, de modo que o resultado final seja ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; possivelmente, pode ser aprimorado substituindo sumL/3com ((sumL * 0x55555556UL) >> 32), embora o último dependa do otimizador JIT [ele pode saber como substituir uma divisão por 3 por uma multiplicação, e seu código pode realmente ser mais eficiente do que uma operação de multiplicação explícita].

Remendando a solução de Patrick Hofman com a correção do supercat , eu lhe dou o seguinte:

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

E o caso do 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 ) );
}

Isso sempre fornece o piso () da média e elimina todos os casos extremos possíveis.

Você poderia usar o fato de que pode escrever cada um dos números como y = ax + b, onde xé uma constante. Cada um aseria y / x(a parte inteira dessa divisão). Cada b seria y % x(o resto / módulo dessa divisão). Se você escolher essa constante de forma inteligente, por exemplo, escolhendo a raiz quadrada do número máximo como uma constante, você pode obter a média dos xnúmeros sem ter problemas com estouro.

A média de uma lista arbitrária de números pode ser encontrada encontrando:

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

onde %denota módulo e /denota a parte 'inteira' da divisão.

O programa seria algo 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 );
    }
}

Se você sabe que tem N valores, pode simplesmente dividir cada valor por N e somá-los?

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

Eu também tentei e encontrei uma solução mais rápida (embora apenas por um fator de cerca de 3/4). Ele usa uma única divisão

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

onde smallDiv3é a divisão por 3 usando multiplicação e trabalhando apenas para pequenos argumentos

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

Aqui está todo o código, incluindo um teste e um benchmark, os resultados não são tão impressionantes.

Esta função calcula o resultado em duas divisões. Deve generalizar bem para outros divisores e tamanhos de palavras.

Ele funciona calculando o resultado da adição de palavras duplas e, em seguida, calculando a divisão.

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ática

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

Experimente isto:

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