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 long
typu? Nie traktuj tego pytania jako specyficznego dla języka C #, po prostu łatwiej jest mi podać próbki w języku C #.
źródło
long.MinValue
ilong.MaxValue
wśród wartości.BigInteger
albodecimal
jest wykluczona, czy jest to tylko przez wzgląd na to co trudne?Odpowiedzi:
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ę:
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:
źródło
(x + y + z) / 3 = x / 3 + y / 3 + z / 3
.f(1,1,2) == 1
podczasf(-2,-2,8) == 2
(x+y)/3
za dużo.NB - Patrick udzielił już świetnej odpowiedzi . Rozwijając to, możesz zrobić ogólną wersję dla dowolnej liczby liczb całkowitych, takich jak:
źródło
long
przypadku mniejszych typów, ale pamiętaj, że druga suma może się przepełnić.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
W C / C ++ na platformach 64-bitowych jest to znacznie łatwiejsze dzięki
__int128
źródło
x=y/3
viax=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ącdelta=y-x-x-x;
i dostosowującx
w razie potrzeby.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:
źródło
(double)(2 / 3)
równe 0,0?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,
Int64
aby 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ącsumL/3
go((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].źródło
Po poprawieniu rozwiązania Patricka Hofmana z korektą supercat , daję ci co następuje:
I przypadek elementu N:
To zawsze daje podłogę () średniej i eliminuje wszystkie możliwe przypadki skrajne.
źródło
Możesz wykorzystać fakt, że możesz zapisać każdą z liczb jako
y = ax + b
, gdziex
jest stałą. Każdya
byłbyy / x
(całkowita część tego podziału). Każde b byłobyy % 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:
gdzie
%
oznacza modulo i/
oznacza „całą” część podziału.Program wyglądałby mniej więcej tak:
źródło
Jeśli wiesz, że masz wartości N, czy możesz po prostu podzielić każdą wartość przez N i zsumować je razem?
źródło
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
gdzie
smallDiv3
jest dzielenie przez 3 przy użyciu mnożenia i działa tylko dla małych argumentówOto cały kod, w tym test i benchmark, wyniki nie są imponujące.
źródło
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.
źródło
Math
Kod
źródło
{1,2,3}
odpowiedź to2
, ale Twój kod zwróci1
.double
, ponieważ w takim przypadku stracimy precyzję.Spróbuj tego:
źródło