Który algorytm jest dokładniejszy przy obliczaniu sumy posortowanej tablicy liczb?

Podano rosnącą skończoną sekwencję liczb dodatnich . Który z poniższych dwóch algorytmów jest lepszy do obliczania sumy liczb?$z_{1} ,z_{2},.....z_{n}$

s=0; 
for \ i=1:n 
    s=s + z_{i} ; 
end

Lub:

s=0; 
for \ i=1:n 
s=s + z_{n-i+1} ; 
end

Moim zdaniem lepiej zacząć dodawać liczby od największej do najmniejszej, ponieważ błąd staje się coraz mniejszy. Wiemy również, że gdy dodamy bardzo dużą liczbę do bardzo małej liczby, przybliżonym wynikiem może być duża liczba.

Czy to jest poprawne? Co jeszcze można powiedzieć?

Dodanie dowolnych liczb zmiennoprzecinkowych zwykle daje pewien błąd zaokrąglania, a błąd zaokrąglania będzie proporcjonalny do wielkości wyniku. Jeśli obliczysz pojedynczą sumę i zaczniesz od dodania najpierw największych liczb, średni wynik będzie większy. Więc zacznij dodawać z najmniejszymi liczbami.

Ale uzyskujesz lepszy wynik (i działa szybciej), jeśli wygenerujesz cztery sumy, na przykład: Zacznij od sum1, sum2, sum3, sum4 i dodaj cztery elementy tablicy kolejno do sum1, sum2, sum3, sum4. Ponieważ każdy wynik wynosi średnio tylko 1/4 oryginalnej kwoty, błąd jest czterokrotnie mniejszy.

Jeszcze lepiej: dodaj liczby parami. Następnie dodaj wyniki parami. Dodaj te wyniki ponownie parami i tak dalej, aż pozostaną dwie liczby do dodania.

Bardzo proste: użyj wyższej precyzji. Użyj długiego podwójnego, aby obliczyć sumę podwójnych. Użyj podwójnego, aby obliczyć sumę liczb zmiennoprzecinkowych.

Blisko ideału: wyszukaj opisany wcześniej algorytm Kahana. Najlepiej nadal, dodając zaczynając od najmniejszej liczby.

Czy te liczby całkowite lub zmiennoprzecinkowe? Zakładając, że jest zmiennoprzecinkowy, wybrałbym pierwszą opcję. Lepiej jest dodawać do siebie mniejsze liczby, a później dodawać większe. Z drugą opcją skończysz dodawanie małej liczby do dużej liczby, gdy rośnie i , co może prowadzić do problemów. Oto dobry zasób na temat arytmetyki zmiennoprzecinkowej: Co każdy informatyk powinien wiedzieć o arytmetyki zmiennoprzecinkowej

Odpowiedź animal_magic jest prawidłowa, dlatego należy dodawać liczby od najmniejszej do największej, ale chcę podać przykład, aby pokazać, dlaczego.

Załóżmy, że pracujemy w formacie zmiennoprzecinkowym, który zapewnia oszałamiające 3 cyfry dokładności. Teraz chcemy dodać dziesięć liczb:

[1000, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Oczywiście dokładna odpowiedź to 1009, ale nie możemy uzyskać tego w naszym 3-cyfrowym formacie. Zaokrąglając do 3 cyfr, najdokładniejszą odpowiedzią, jaką otrzymujemy, jest 1010. Jeśli dodamy najmniejszą do największej, w każdej pętli otrzymamy:

Loop Index        s
1                 1
2                 2
3                 3
4                 4
5                 5
6                 6
7                 7
8                 8
9                 9
10                1009 -> 1010

Otrzymujemy więc najdokładniejszą możliwą odpowiedź dla naszego formatu. Załóżmy teraz, że dodajemy od największego do najmniejszego.

Loop Index        s
1                 1000
2                 1001 -> 1000
3                 1001 -> 1000
4                 1001 -> 1000
5                 1001 -> 1000
6                 1001 -> 1000
7                 1001 -> 1000
8                 1001 -> 1000
9                 1001 -> 1000
10                1001 -> 1000

Ponieważ liczby zmiennoprzecinkowe są zaokrąglane po każdej operacji, wszystkie dodatki są zaokrąglane, zwiększając nasz błąd z 1 do 9 z dokładności. Teraz wyobraź sobie, czy twój zestaw liczb do dodania miał 1000, a potem sto jeden, czy milion. Zauważ, że aby być naprawdę dokładnym, chciałbyś zsumować najmniejsze dwie liczby, a następnie zastosować wynik w swoim zestawie liczb.

W ogólnym przypadku użyłbym sumowania kompensacyjnego (lub sumowania Kahana). O ile liczby nie są już posortowane, sortowanie ich będzie znacznie droższe niż ich dodawanie . Sumowanie kompensowane jest również dokładniejsze niż sumowanie sortowane lub sumowanie naiwne (patrz poprzedni link).

Jeśli chodzi o referencje, to , co każdy programista powinien wiedzieć o arytmetyki zmiennoprzecinkowej, opisuje podstawowe punkty wystarczająco szczegółowo, aby ktoś mógł je odczytać w 20 (+/- 10) minut i zrozumieć podstawy. „To, co każdy informatyk powinien wiedzieć o arytmetyki zmiennoprzecinkowej” Goldberga, jest klasycznym odniesieniem, ale większość osób, które znam, które zalecają, aby papier nie przeczytał go szczegółowo, ponieważ ma około 50 stron (więcej, w niektórych druki) i napisane gęstą prozą, więc nie mogę polecić tego jako pierwszej linii odniesienia dla ludzi. To jest dobre na drugie spojrzenie na ten temat. Odniesieniem encyklopedycznym jest dokładność i stabilność algorytmów numerycznych Highama, który obejmuje ten materiał, a także kumulację błędów numerycznych w wielu innych algorytmach; to także 680 stron, więc też nie chciałbym najpierw zajrzeć do tego źródła.

Poprzednie odpowiedzi już ogólnie omawiają tę sprawę i dają solidne rady, ale jest jeszcze jedno dziwactwo, o którym chciałbym wspomnieć. W większości nowoczesnych architektur forpętla, którą opisałeś, i tak zostałaby wykonana w 80-bitowej rozszerzonej precyzji , co gwarantuje dodatkową dokładność, ponieważ wszystkie zmienne tymczasowe zostaną umieszczone w rejestrach. Masz już jakąś formę zabezpieczenia przed błędami numerycznymi. Jednak w bardziej skomplikowanych pętlach wartości pośrednie będą przechowywane w pamięci pomiędzy operacjami, a zatem skrócone do 64 bitów. zgaduję, że

s=0; 
for \ i=1:n 
    printf("Hello World");
    s=s + z_{i} ; 
end

wystarczy uzyskać niższą precyzję w podsumowaniu (!!). Więc bądź bardzo ostrożny, jeśli chcesz printf-debugować swój kod, sprawdzając jednocześnie dokładność.

Dla zainteresowanych niniejszy artykuł opisuje problem w szeroko stosowanej procedurze numerycznej (rozkładanie rang na odkrycia Lapacka), której debugowanie i analiza była bardzo trudna właśnie z tego powodu.

Z 2 opcji dodawanie z mniejszego na większy spowoduje mniejszy błąd numeryczny niż dodawanie z większego na mniejszy.

Jednak> 20 lat temu w mojej klasie „Metody numeryczne” instruktor stwierdził to i przyszło mi do głowy, że wciąż wprowadza więcej błędów niż to konieczne z powodu względnej różnicy wartości między akumulatorem a wartościami, które były dodawane.

Logicznie, preferowanym rozwiązaniem jest dodanie 2 najmniejszych liczb na liście, a następnie ponowne wstawienie zsumowanej wartości do posortowanej listy.

Aby to zademonstrować, opracowałem algorytm, który mógłby to zrobić efektywnie (w czasie i przestrzeni), wykorzystując przestrzeń zwolnioną, gdy elementy zostały usunięte z tablicy podstawowej, aby zbudować tablicę wtórną sumowanych wartości, które były z natury uporządkowane od czasu dodania były sumami wartości, które zawsze rosły. Na każdej iteracji sprawdzane są „końcówki” obu tablic w celu znalezienia 2 najmniejszych wartości.

Ponieważ nie ograniczyłeś używanego typu danych, aby osiągnąć idealnie dokładny wynik, po prostu użyj liczb o dowolnej długości ... w takim przypadku kolejność nie będzie miała znaczenia. Będzie znacznie wolniej, ale osiągnięcie doskonałości wymaga czasu.

Użyj dodawania drzewa binarnego, tj. Wybierz średnią rozkładu (najbliższa liczba) jako korzeń drzewa binarnego i utwórz posortowane drzewo binarne, dodając mniejsze wartości po lewej stronie wykresu i większe wartości po prawej stronie itd. . Dodaj rekurencyjnie wszystkie węzły podrzędne jednego rodzica w podejściu oddolnym. Będzie to skuteczne, gdy średni błąd wzrośnie wraz z liczbą podsumowań, a w podejściu do drzewa binarnego liczba podsumowań będzie zgodna z logarytmem n w bazie 2. Stąd średni błąd będzie mniejszy.

To, co Hristo Iliev powiedział powyżej o 64-bitowych kompilatorach preferujących instrukcje SSE i AVX zamiast FPU (AKA NDP) jest absolutnie prawdziwe, przynajmniej w przypadku Microsoft Visual Studio 2013. Jednak dla operacji zmiennoprzecinkowych podwójnej precyzji, których używałem, znalazłem w rzeczywistości szybsze, a także teoretycznie bardziej dokładne, korzystanie z FPU. Jeśli jest to dla Ciebie ważne, proponuję najpierw przetestować różne rozwiązania, a następnie wybrać ostateczne podejście.

Podczas pracy w Javie bardzo często używam typu danych BigDecimal o dowolnej precyzji. Jest to po prostu zbyt łatwe i zwykle nie zauważa się zmniejszenia prędkości. Obliczanie funkcji transcendentalnych za pomocą nieskończonych szeregów i sqrt przy użyciu metody Newtona może zająć milisekundę lub więcej, ale jest wykonalne i dość dokładne.

Zostawiłem to tylko tutaj /programming//a/58006104/860099 (kiedy tam wejdziesz, kliknij, aby „pokazać fragment kodu” i uruchomić go przyciskiem

Jest to przykład JavaScript, który wyraźnie pokazuje, że suma zaczynająca się od największej daje większy błąd

arr=[9,.6,.1,.1,.1,.1];

sum     =             arr.reduce((a,c)=>a+c,0);  // =  9.999999999999998
sortSum = [...arr].sort().reduce((a,c)=>a+c,0);  // = 10

console.log('sum:     ',sum);
console.log('sortSum:',sortSum);