Średnia liczb

Zadanie pozornie oczywiste: dany jest wektor liczb zmiennoprzecinkowych, policzyć ich średnią arytmetyczną.

Ale oba narzucające się natychmiast rozwiązania są błędne: jeśli najpierw te wartości zsumujemy, a potem podzielmy, to ryzykujemy, że suma nam wyskoczy poza zakres i nie otrzymamy poprawnego wyniku. Podobnie, jeśli najpierw będziemy dzielić, a potem sumować, ryzykujemy niedopełnienie i znowu błędny wynik.

Myślałem więc, żeby najpierw spróbować pierwszą metodą i tylko pilnować, czy nie wyskakujemy. Jeśli tak, to cofamy się o jeden krok i odkładamy sobie taką średnią częściową na bok, zerujemy sumę i liczymy dalej, na końcu biorąc odpowiednią średnią ważoną całości. Ale i ta metoda nie jest w pełni skuteczna, nie mówiąc już o tym, że wydaje się nadmiernie skomplikowana.

Jak więc liczyć średnią tak, żeby jej wartość była możliwie niezniekształcona?

zalezy od jezyka w ktorym piszesz (ai rowniez jakiego typu uzywasz)

W C# funkcja Average dziala dosc dobrze dla wiekszosci danych wiec robisz tam jakas Liste liczb i robisz na niej proste average

https://www.dotnetperls.com/average

jezeli potrzebujesz cos bardziej dokladnego to musialbys podac dziedzine liczb, jak duzo by ich bylo oraz jak szybko mialoby to dzialac i przede wszystkim do czego to mialoby byc

Chciałem się po prostu zastanowić nad algorytmem, w oderwaniu od języka, w którym mógłby być implementowany (stąd wybór działu).

Powiedzmy więc, że piszę w C lub czymś jeszcze niższym (nie chcę korzystać z gotowych funkcji bibliotecznych, tylko zrozumieć sposób liczenia), mam na wejściu double’e (pełen zakres zmiennej, nie wiem nic więcej; co najwyżej przyjmijmy, że nie ma tam NaNów ani nieskończoności) i o tym, ile ich jest, dowiem się dopiero podczas wykonywania programu.

Szybkość działania obojętna, liczy się możliwa precyzja. Absolutnym minimum jest, by średnia n takich samych liczb była policzona dobrze, bez wyszczególniania tego warunku w samym algorytmie. Celem jest lepsze poznanie liczb zmiennoprzecinkowych i podstawowych algorytmów na nich.

Zadanie ambitne, zwłaszcza ten warunek: "Absolutnym minimum jest, by średnia n takich samych liczb była policzona dobrze"

(0.1 + 0.1 + 0.1)/3
0.10000000000000002

System.out.println((0.1 + 0.1 + 0.1)/3); // => 0.10000000000000002

Tak. Oczywistym jest, że najprostsze rozwiązania zawiodą, ale nie widzę powodu, dla którego nie miałoby to być wykonywalne. Szczególnie że nie oczekuję złożoności stałej, nie przeszkadza mi np. konieczność dzielenia wektora na fragmenty o długości wyrażanej potęgami dwójki i liczenia średniej z nich, a potem średniej ważonej z całości.

Cóż, masz jeszcze znane ze statystyki estymacje średniej i wyliczenie z poziomem ufności dla bardzo dużej ilości danych. Wtedy przy zadanym poziomie ufności, możesz próbkować strumień danych i liczyć średnią "w locie" :-)

Jeśli chcesz mieć zagwarantowaną precyzję, to używaj jakichś bibliotek BigNum.

@datdata: czyli co, przekształcić każdego double’a na liczbę wymierną/parę bigintów, policzyć średnią wtedy, przekonwertować z powrotem? Zacne rozwiązanie, ale wolałbym się pomęczyć na samych zmiennoprzecinkowych.

Kolejny pomysł:
Robimy sobie pomocniczy słownik [wartość: zliczenia], dzielimy zliczenia przez największy wspólny dzielnik wszystkich zliczeń, liczymy średnią na tak poprawionych danych. Wtedy „problem” z rozjeżdżającą się średnią takich samych wartości mamy z głowy. Pozostaje dalej problem z przekraczaniem zakresu/liczbami subnormalnymi.

No twoje podejście wygląda jak próba odważenia składników na ciasto za pomocą wagi łazienkowej.

Zdaję sobie z tego sprawę. Mam wrażenie, że takie absurdalnie niepraktyczne podejście do kompletnie wydumanych problemów jest najlepszą metodą nauki — a nauka jest tutaj celem jedynym. Chcę lepiej zrozumieć ograniczenia i kłopoty wynikające z używania liczb zmiennoprzecinkowych, więc biorę się za coś, do czego się kompletnie nie nadają, i patrzę, gdzie się porozbijam; po czym zapamiętuję każdą z tych pułapek na później, żebym nie miał w przyszłości nierealnych oczekiwań co do tego, co możliwe jest, a co nie. Dodatkowo, świadomość które z tych pułapek ominąć można (i jakim kosztem) także wydaje mi się cenna.

Powtarzam, ja tego nie chcę wykorzystywać w praktyce, to rozwiązanie nigdy nie znajdzie się w żadnym moim programie. Ja po prostu chcę lepiej zrozumieć liczby zmiennoprzecinkowe, algorytmy na nich. Tak jak wcześniej mi @Mokrowski podpowiedział z algorytmem Kahana — to było dla mnie bardzo cenne, bo nie znałem tego algorytmu, a teraz wiem, że mogę kontrolować sumowanie liczb zmiennoprzecinkowych i z jakim kosztem się to wiąże.
Podobnie, może uda mi się dowiedzieć, jak mogę kontrolować dzielenie przez liczby nie będące potęgami dwójki. Albo jak mogę lepiej kontrolować operacje na subnormalnych. Albo jak sprawnie operować na liczbach, gdy istnieje ryzyko przepełnienia. Itd.