Dlaczego dodawanie prawdopodobieństw dziennika jest szybsze niż pomnożenie prawdopodobieństw?

Aby sformułować pytanie, w informatyce często chcemy obliczyć iloczyn kilku prawdopodobieństw:

P(A,B,C) = P(A) * P(B) * P(C)

Najprostszym podejściem jest po prostu pomnożenie tych liczb i właśnie to zamierzałem zrobić. Jednak mój szef powiedział, że lepiej jest dodać dziennik prawdopodobieństwa:

log(P(A,B,C)) = log(P(A)) + log(P(B)) + log(P(C))

Daje to prawdopodobieństwo dziennika, ale w razie potrzeby możemy je później uzyskać:

P(A,B,C) = e^log(P(A,B,C))

Dodawanie dziennika jest uważane za lepsze z dwóch powodów:

1. Zapobiega „niedomiarowi”, przez co iloczyn prawdopodobieństwa jest tak mały, że zostaje zaokrąglony do zera. Może to często stanowić ryzyko, ponieważ prawdopodobieństwo jest często bardzo małe.
2. Jest to szybsze, ponieważ wiele architektur komputerowych może wykonywać dodawanie szybciej niż mnożenie.

Moje pytanie dotyczy drugiej kwestii. Tak to widziałem, ale nie bierze ono pod uwagę dodatkowych kosztów uzyskania dziennika! Powinniśmy porównać „koszt dziennika + koszt dodania” do „kosztu pomnożenia”. Czy po uwzględnieniu tego jest jeszcze mniejszy?

Strona Wikipedii ( prawdopodobieństwo dziennika ) jest pod tym względem myląca, mówiąc: „Konwersja do postaci dziennika jest kosztowna, ale następuje tylko raz”. Nie rozumiem tego, ponieważ myślę, że musisz dodać dziennik każdego terminu niezależnie przed dodaniem. czego mi brakuje?

Wreszcie uzasadnienie, że „komputery wykonują dodawanie szybciej niż mnożenie” jest niejasne. Czy jest to specyficzne dla zestawu instrukcji x86, czy może jest to bardziej fundamentalna cecha architektury procesorów?

Również strona Wikipedii ( https://en.wikipedia.org/wiki/Log_probability ) jest myląca pod tym względem, stwierdzając: „Konwersja do postaci dziennika jest kosztowna, ale następuje tylko raz”. Nie rozumiem tego, ponieważ myślę, że musisz dodać dziennik każdego terminu niezależnie przed dodaniem. czego mi brakuje?

Jeśli chcesz tylko raz obliczyć , masz rację. Będziesz musiał obliczyć n logarytmów i n - 1 dodatków, podczas gdy naiwna metoda wymaga n - 1 multiplikacji.$P(A_1)\ldots P(A_n)$$n$$n-1$$n-1$

Jednak często zdarza się, że chcesz odpowiadać na zapytania formularza:

Oblicz dla niektórych podzbiorów I z { 1 , … n } .$\prod_{i \in I} P(A_i)$$I$$\{1, \ldots n\}$

W takim przypadku możesz wstępnie przetworzyć swoje dane, aby obliczyć wszystkie tylko raz i odpowiedzieć na każde zapytanie, wykonując | Ja | wzbogacenie.$\log P(A_i)$$|I|$

Wreszcie uzasadnienie, że „komputery wykonują dodawanie szybciej niż mnożenie” jest niejasne. Czy jest to specyficzne dla zestawu instrukcji x86, czy może jest to bardziej fundamentalna cecha architektury procesorów?

To jest szersze pytanie. Zasadniczo (prawdopodobnie?) Trudniej jest obliczyć mnożenie niż dodawanie. Obliczanie + b jest liniowa w rozmiarze i B (przy użyciu algorytmu trywialne), natomiast obecnie nie wiem jak obliczyć do × B o tej samej złożoności czasowej (Sprawdź najlepsze algorytmy tutaj ).$a+b$$a$$b$$a\times b$

Oczywiście nie ma ostatecznej odpowiedzi: na przykład, jeśli masz do czynienia tylko z liczbami całkowitymi i mnożymy przez potęgi , powinieneś raczej porównać shift z operacjami dodawania.$2$

Niemniej jednak jest to rozsądne stwierdzenie na wszystkich popularnych architekturach komputerowych: mnożenie liczb zmiennoprzecinkowych będzie wolniejsze niż dodawanie.

$N$$p_1,...p_N$$p_i$

$N$

$O(n)$$n$$O(n^2)$

Nawiasem mówiąc, ten pomysł jest podobny do modularnego mnożenia Montgomery, w którym mnożenia są wykonywane w postaci Montgomery, która jest znacznie szybsza niż zwykłe mnożenie, a następnie redukcja.