Średnia z 3 długich liczb całkowitych

103

Mam 3 bardzo duże liczby całkowite ze znakiem.

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

Chcę obliczyć ich średnią obciętą. Oczekiwana średnia wartość to long.MaxValue - 1, czyli 9223372036854775806.

Nie da się tego obliczyć jako:

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

Uwaga: czytałem wszystkie te pytania dotyczące średniej z 2 liczb, ale nie widzę, jak można zastosować tę technikę do średniej z 3 liczb.

Byłoby to bardzo łatwe przy użyciu BigInteger, ale załóżmy, że nie mogę go użyć.

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

Jeśli przejdę na double, to oczywiście stracę precyzję:

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

Jeśli przejdę na decimal, to działa, ale załóżmy też, że nie mogę go używać.

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

Pytanie: Czy można obliczyć obciętą średnią z 3 bardzo dużych liczb całkowitych tylko przy użyciu longtypu? Nie traktuj tego pytania jako specyficznego dla języka C #, po prostu łatwiej jest mi podać próbki w języku C #.

Ulugbek Umirov
źródło
1
dlaczego nie obliczyć ogólnej średniej różnicy i odjąć ją od wartości maksymalnej?
Andreas Niedermair
6
@AndreasNiedermair Nie działałbym w przypadku, gdybym miał long.MinValuei long.MaxValuewśród wartości.
Ulugbek Umirov
dobry chwyt, rzeczywiście :)
Andreas Niedermair
Czy na pewno musimy się tym martwić, czy nie powinno to być obsługiwane przez framework?
Bolu
11
Czy istnieje jakiś rzeczywisty powód, że BigIntegeralbo decimaljest wykluczona, czy jest to tylko przez wzgląd na to co trudne?
jpmc26

Odpowiedzi:

142

Ten kod będzie działał, ale nie jest taki ładny.

Najpierw dzieli wszystkie trzy wartości (piętro wartości, więc „tracisz” resztę), a następnie dzieli resztę:

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

Zauważ, że powyższa próbka nie zawsze działa poprawnie, gdy ma jedną lub więcej wartości ujemnych.

Jak omówiono z Ulugbekiem, ponieważ liczba komentarzy eksploduje poniżej, oto obecne NAJLEPSZE rozwiązanie zarówno dla wartości dodatnich, jak i ujemnych.

Dzięki odpowiedziom i komentarzom Ulugbeka Umirova , Jamesa S , KevinZa , Marca van Leeuwena , gnasher729 jest to aktualne rozwiązanie:

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);
}
Patrick Hofman
źródło
3
@DavidG Nie. W matematyce (x + y + z) / 3 = x / 3 + y / 3 + z / 3.
Kris Vandermotten
4
Użyłem Z3, aby udowodnić, że jest to poprawne dla wszystkich liczb zmiennych od 1 do 5.
usr
5
Oczywiście wydaje się, że to działa, ale sposób, w jaki działa obcinanie liczb całkowitych, może cię schrzanić. f(1,1,2) == 1podczasf(-2,-2,8) == 2
KevinZ
11
Należy zauważyć, że ze względu na uszkodzoną mózg semantykę operacji modulo, może to dać wynik różniący się o jeden, a mianowicie zaokrąglony w górę, a nie w dół, jeśli dozwolone są wartości ujemne dla zmiennych. Na przykład, jeśli x, y są dodatnimi wielokrotnościami 3, a z wynosi -2, otrzymujesz (x+y)/3za dużo.
Marc van Leeuwen
6
@KevinZ: ... którego efekt musi zostać cofnięty przez programistę, który nigdy nie chciał tego szczególnego zachowania. Pozwolenie programiście na określenie modułu zamiast wyprowadzania go z reszty, którą kompilator mógł wyprowadzić z modułu, wydawałoby się pomocne.
supercat
26

NB - Patrick udzielił już świetnej odpowiedzi . Rozwijając to, możesz zrobić ogólną wersję dla dowolnej liczby liczb całkowitych, takich jak:

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;
James S.
źródło
1
To się nie stanie w longprzypadku mniejszych typów, ale pamiętaj, że druga suma może się przepełnić.
user541686
7

Patrick Hofman opublikował świetne rozwiązanie . Ale w razie potrzeby można go nadal wdrożyć na kilka innych sposobów. Korzystając z algorytmu tutaj mam inne rozwiązanie. Jeśli zostanie starannie wdrożony, może być szybszy niż wiele podziałów w systemach z powolnymi dzielnikami sprzętowymi. Można go dodatkowo zoptymalizować, korzystając z techniki dzielenia przez stałe z zachwytu hakera

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;

W C / C ++ na platformach 64-bitowych jest to znacznie łatwiejsze dzięki __int128

int64_t average = ((__int128)x + y + z)/3;
phuclv
źródło
2
Sugerowałbym, że dobrym sposobem na podzielenie 32-bitowej wartości bez znaku przez 3 jest pomnożenie przez 0x55555555L, dodanie 0x55555555 i przesunięcie w prawo przez 32. Dla porównania, metoda divideby3 wygląda tak, jakby wymagała wielu dyskretnych kroków.
supercat
@supercat tak, znam tę metodę. Metoda z zachwytu hakera jest jeszcze bardziej poprawna, ale
wdrożę ją po
Nie jestem pewien, co oznacza „bardziej poprawne”. Mnożenia odwrotne mogą w wielu przypadkach bezpośrednio dawać dokładne wartości lub też wartości, które można udoskonalić w jednym lub dwóch krokach. Przy okazji, myślę, że powinienem był zasugerować pomnożenie przez 0x55555556, co dałoby wtedy dokładne wyniki bez potrzeby „dodawania”. Czy stan pętli jest prawidłowy? Co modyfikuje H i L w pętli?
supercat
Nawiasem mówiąc, nawet jeśli nie ma mnożenia sprzętowego, można szybko przybliżyć brak znaku x=y/3via x=y>>2; x+=x>>2; x+=x>>4; x+=x>>8; x+=x>>16; x+=x>>32;. Wynik będzie bardzo zbliżony do x i można go sprecyzować, obliczając delta=y-x-x-x;i dostosowując xw razie potrzeby.
supercat
1
@ gnasher729 Zastanawiam się, czy może użyć tej optymalizacji na komputerach 32-bitowych, ponieważ często nie może zrobić mnożenia 64x64 → 128 bitów
phuclv
7

Możesz obliczyć średnią liczb na podstawie różnic między liczbami, a nie na podstawie sumy.

Powiedzmy, że x to maksimum, y to mediana, z to min (tak jak masz). Nazwiemy je max, medianą i min.

Sprawdzanie warunkowe dodane zgodnie z komentarzem @ 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));
}
La-comadreja
źródło
2
Zobacz komentarz @ UlugbekUmirov: Nie działałbym w przypadku, gdybym miał long.MinValue i long.MaxValue wśród wartości
Bolu
@Bolu komentarz dotyczy tylko long.MinValue. Więc dodałem ten warunek, aby działał w naszym przypadku.
La-comadreja
Jak można użyć mediany, jeśli nie została zainicjowana?
phuclv
@ LưuVĩnhPhúc, mediana to wartość między minimum a maksimum.
La-comadreja
1
nie jest (double)(2 / 3)równe 0,0?
phuclv
5

Ponieważ C używa dzielenia zmiennoprzecinkowego zamiast dzielenia euklidesowego, może być łatwiej obliczyć odpowiednio zaokrągloną średnią z trzech wartości bez znaku niż z trzech ze znakiem. Po prostu dodaj 0x8000000000000000UL do każdej liczby przed obliczeniem średniej bez znaku, odejmij ją po wykonaniu wyniku i użyj niezaznaczonego rzutu z powrotem do, Int64aby uzyskać średnią ze znakiem.

Aby obliczyć średnią bez znaku, oblicz sumę pierwszych 32 bitów trzech wartości. Następnie oblicz sumę ostatnich 32 bitów trzech wartości, plus sumę z góry plus jeden [plus jeden daje zaokrąglony wynik]. Średnia wyniesie 0x55555555 razy pierwsza suma plus jedna trzecia drugiej.

Wydajność na procesorach 32-bitowych można zwiększyć, wytwarzając trzy wartości „sumy”, z których każda ma długość 32 bity, tak aby ostateczny wynik to ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; można go jeszcze bardziej ulepszyć, zastępując sumL/3go ((sumL * 0x55555556UL) >> 32), chociaż ten drugi zależałby od optymalizatora JIT [mógłby wiedzieć, jak zastąpić dzielenie przez 3 mnożeniem, a jego kod mógłby być w rzeczywistości bardziej wydajny niż jawna operacja mnożenia].

supercat
źródło
Czy po dodaniu 0x8000000000000000UL przepełnienie nie wpływa na wynik?
phuclv
@ LưuVĩnhPhúc Nie ma przepełnienia. Przejdź do mojej odpowiedzi na wdrożenie. Jednak podział na 2 32-bitowe int był niepotrzebny.
KevinZ
@KevinZ: Dzielenie każdej wartości na górną i dolną 32-bitową część jest szybsze niż dzielenie jej na iloraz dzielenia przez trzy i resztę.
supercat
1
@ LưuVĩnhPhúc: W przeciwieństwie do wartości ze znakiem, które zachowują się semantycznie jak liczby i nie mogą się przepełniać w legalnym programie w języku C, wartości bez znaku ogólnie zachowują się jak elementy zawijającego abstrakcyjnego pierścienia algebraicznego, więc semantyka zawijania jest dobrze zdefiniowana.
supercat
1
Krotka reprezentuje -3, -2, -1. Po dodaniu 0x8000U do każdej wartości, wartości należy podzielić na pół: 7F + FF 7F + FE 7F + FD. Dodaj górną i dolną połowę, uzyskując 17D + 2FA. Dodaj sumę z górnej połowy do sumy z dolnej połowy, uzyskując 477. Pomnóż 17D przez 55, otrzymując 7E81. Podziel 477 przez trzy, otrzymując 17D. Dodaj 7E81 do 17D uzyskując 7FFE. Odejmij od tego 8000 i uzyskaj -2.
supercat
5

Po poprawieniu rozwiązania Patricka Hofmana z korektą supercat , daję ci co następuje:

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

I przypadek elementu 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 ) );
}

To zawsze daje podłogę () średniej i eliminuje wszystkie możliwe przypadki skrajne.

KevinZ
źródło
1
Przetłumaczyłem AvgN na kod Z3 i udowodniłem, że jest to poprawne dla wszystkich rozsądnych rozmiarów wejściowych (np. 1 <= args.Length <= 5 i rozmiar wektorów bitowych 6). Ta odpowiedź jest poprawna.
usr
Cudowna odpowiedź, Kevin. Dziękuję za Twój wkład! meta.stackoverflow.com/a/303292/993547
Patrick Hofman
4

Możesz wykorzystać fakt, że możesz zapisać każdą z liczb jako y = ax + b, gdzie xjest stałą. Każdy abyłby y / x(całkowita część tego podziału). Każde b byłoby y % x(reszta / modulo tego podziału). Jeśli wybierzesz tę stałą w inteligentny sposób, na przykład wybierając jako stałą pierwiastek kwadratowy z maksymalnej liczby, możesz otrzymać średnią zx liczb bez problemów z przepełnieniem.

Średnią z dowolnej listy liczb można znaleźć, znajdując:

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

gdzie %oznacza modulo i/ oznacza „całą” część podziału.

Program wyglądałby mniej więcej tak:

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 );
    }
}
Sumurai8
źródło
4

Jeśli wiesz, że masz wartości N, czy możesz po prostu podzielić każdą wartość przez N i zsumować je razem?

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);
}
abelenky
źródło
to jest to samo, co rozwiązanie Patricka Hofmana, jeśli nie mniej poprawne niż wersja ostateczna
phuclv
2

Spróbowałem też tego i wymyśliłem szybsze rozwiązanie (choć tylko o współczynnik około 3/4). Używa pojedynczego podziału

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

gdzie smallDiv3jest dzielenie przez 3 przy użyciu mnożenia i działa tylko dla małych argumentów

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

Oto cały kod, w tym test i benchmark, wyniki nie są imponujące.

maaartinus
źródło
1

Ta funkcja oblicza wynik w dwóch działach. Powinien ładnie uogólniać na inne dzielniki i rozmiary słów.

Działa poprzez obliczenie wyniku dodawania podwójnych słów, a następnie obliczenie podziału.

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;
}
Řrřola
źródło
0

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

Kod

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));
}
Khaled.K
źródło
dla zestawu {1,2,3}odpowiedź to 2, ale Twój kod zwróci 1.
Ulugbek Umirov
Kod @UlugbekUmirov naprawiony, należy używać podwójnych typów do przetwarzania
Khaled.K
1
Tego właśnie chcę uniknąć - użycia double, ponieważ w takim przypadku stracimy precyzję.
Ulugbek Umirov
0

Spróbuj tego:

long n = Array.ConvertAll(new[]{x,y,z},v=>v/3).Sum()
     +  (Array.ConvertAll(new[]{x,y,z},v=>v%3).Sum() / 3);
trinalbadger587
źródło