3 개의 긴 정수 평균

3 개의 긴 정수 평균

---

3 개의 매우 큰 부호있는 정수가 있습니다.

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

잘린 평균을 계산하고 싶습니다. 예상 평균 값은 long.MaxValue - 1입니다 9223372036854775806.

다음과 같이 계산하는 것은 불가능합니다.

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

참고 : 평균 2 개의 숫자에 대한 모든 질문을 읽었지만 그 기술이 평균 3 개의 숫자에 어떻게 적용될 수 있는지 모르겠습니다.

를 사용하면 매우 쉬울 BigInteger수 있지만 사용할 수 없다고 가정합시다.

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

로 변환하면 double물론 정밀도가 떨어집니다.

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

로 변환 decimal하면 작동하지만 사용할 수 없다고 가정합시다.

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

질문 :long 유형을 사용하는 경우에만 3 개의 매우 큰 정수의 잘린 평균을 계산하는 방법이 있습니까? 이 질문을 C # 관련 질문으로 간주하지 마십시오. C #으로 샘플을 제공하는 것이 더 쉽습니다.

---

이 코드는 작동하지만 그렇게 예쁘지는 않습니다.

먼저 세 값을 모두 나눈 다음 (값을 내림으로 인해 나머지는 '잃어 버립니다') 나머지를 나눕니다.

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

위의 샘플은 하나 이상의 음수 값이있을 때 항상 제대로 작동하지 않습니다.

Ulugbek과 논의한 바와 같이 댓글 수가 아래에서 폭발적으로 증가하고 있으므로 양수 및 음수 값 모두에 대한 현재 BEST 솔루션이 있습니다.

Ulugbek Umirov , James S , KevinZ , Marc van Leeuwen , gnasher729 의 답변과 의견 덕분에 이것이 현재 솔루션입니다.

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은 이미 훌륭한 대답을했습니다 . 이를 확장하면 다음과 같이 정수의 수에 대한 일반 버전을 수행 할 수 있습니다.

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은 훌륭한 솔루션 을 게시했습니다 . 그러나 필요한 경우 여러 다른 방법으로 구현할 수 있습니다. 여기 알고리즘을 사용하면 또 다른 해결책이 있습니다. 신중하게 구현하면 하드웨어 제수가 느린 시스템의 여러 부서보다 ​​빠를 수 있습니다. 해커의 기쁨에서 상수로 나누기 기술을 사용하여 더욱 최적화 할 수 있습니다.

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;

64 비트 플랫폼의 C / C ++에서는 __int128

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

---

합계를 사용하는 대신 숫자 간의 차이를 기반으로 숫자의 평균을 계산할 수 있습니다.

x가 최대, y가 중앙값, z가 최소라고 가정 해 보겠습니다. 우리는 그것들을 max, median 및 min이라고 부를 것입니다.

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

---

C는 유클리드 나눗셈이 아닌 내림 나눗셈을 사용하기 때문에 세 개의 부호있는 값보다 세 개의 부호없는 값의 적절하게 반올림 된 평균을 계산하는 것이 더 쉬울 수 있습니다. 부호없는 평균을 취하기 전에 각 숫자에 0x8000000000000000UL을 더하고 결과를 취한 후 빼고 확인되지 않은 캐스트 백을 사용하여 Int64부호있는 평균을 얻습니다.

To compute the unsigned average, compute the sum of the top 32 bits of the three values. Then compute the sum of the bottom 32 bits of the three values, plus the sum from above, plus one [the plus one is to yield a rounded result]. The average will be 0x55555555 times the first sum, plus one third of the second.

Performance on 32-bit processors might be enhanced by producing three "sum" values each of which is 32 bits long, so that the final result is ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; it might possibly be further enhanced by replacing sumL/3 with ((sumL * 0x55555556UL) >> 32), though the latter would depend upon the JIT optimizer [it might know how to replace a division by 3 with a multiply, and its code might actually be more efficient than an explicit multiply operation].

---

You could use the fact that you can write each of the numbers as y = ax + b, where x is a constant. Each a would be y / x (the integer part of that division). Each b would be y % x (the rest/modulo of that division). If you choose this constant in an intelligent way, for example by choosing the square root of the maximum number as a constant, you can get the average of x numbers without having problems with overflow.

The average of an arbitrary list of numbers can be found by finding:

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

where % denotes modulo and / denotes the 'whole' part of division.

The program would look something like:

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

---

Patching Patrick Hofman's solution with supercat's correction, I give you the following:

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

And the N element case:

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

This always gives the floor() of the mean, and eliminates every possible edge case.

---

If you know you have N values, can you just divide each value by N and sum them together?

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

---

I also tried it and come up with a faster solution (although only by a factor about 3/4). It uses a single 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;
}

where smallDiv3 is division by 3 using multipliation and working only for small arguments

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

Here is the whole code including a test and a benchmark, the results are not that impressive.

---

This function computes the result in two divisions. It should generalize nicely to other divisors and word sizes.

It works by computing the double-word addition result, then working out the 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));
}

---

Try this:

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

참고URL : https://stackoverflow.com/questions/23949785/average-of-3-long-integers