Algorytm czynnikowy jest bardziej wydajny niż naiwne mnożenie

38

Wiem, jak kodować silnie przy użyciu iteracji i rekurencji (np. n * factorial(n-1)Na przykład). Przeczytałem w podręczniku (bez dalszych wyjaśnień), że istnieje jeszcze bardziej wydajny sposób kodowania silni poprzez dzielenie ich na pół rekurencyjnie.

Rozumiem, dlaczego tak może być. Chciałem jednak spróbować napisać go samodzielnie i nie sądzę, że wiem od czego zacząć. Przyjaciel zasugerował, że najpierw napiszę przypadki podstawowe. i myślałem o użyciu tablic, aby śledzić liczby ... ale tak naprawdę nie widzę żadnego wyjścia do zaprojektowania takiego kodu.

Jakie techniki powinienem badać?

użytkownik65165
źródło

Odpowiedzi:

40

Najlepszym znanym algorytmem jest wyrażanie silni jako iloczynu sił pierwszych. Można szybko określić liczby pierwsze, a także odpowiednią moc dla każdej liczby pierwszej, stosując podejście sitowe. Obliczenie każdej mocy można wykonać skutecznie za pomocą wielokrotnego kwadratu, a następnie mnożymy czynniki razem. Zostało to opisane przez Petera B. Borweina, On the Complexity of Calculating Factorials , Journal of Algorytmy 6 376–380, 1985. ( PDF ) Krótko mówiąc, można obliczyć w czasie O ( n ( log n ) 3 log log n ) , w porównaniu do Ω ( nn!O(n(logn)3loglogn) czas wymagany podczas korzystania z definicji.Ω(n2logn)

Podręcznik mógł chyba oznaczać metodę „dziel i rządź”. Można zmniejszyć mnożenie , stosując regularny wzór produktu.n1

Niech oznacz 1 3 5 ( 2 n - 1 ) jako wygodny zapis. Zmień kolejność współczynników ( 2 n ) ! = 1 2 3 ( 2 n ) jako ( 2 n ) ! = n ! 2 n3 5 7 ( 2 n -n?135(2n1)(2n)!=123(2n) Załóżmy teraz, że n =

(2n)!=n!2n357(2n1).
dla jakiejś liczby całkowitej k > 0 . (Jest to użyteczne założenie, aby uniknąć komplikacji w poniższej dyskusji, a pomysł można rozszerzyć na ogólne n .) Następnie ( 2 k ) ! = ( 2 k - 1 ) ! 2 2 k - 1 ( 2 k - 1 ) ? i poprzez rozszerzenie tego nawrotu ( 2 k ) ! =n=2)kk>0n(2)k)!=(2)k-1)!2)2)k-1(2)k-1)? Komputery( 2 k - 1 )?
(2k)!=(22k1+2k2++20)i=0k1(2i)?=(22k1)i=1k1(2i)?.
(2k1)? i mnożenie produktów cząstkowych na każdym etapie zajmuje (k-2))+2)k-1-2) krotności. Jest to poprawa współczynnika prawie z mnożenia 2 k - 2 przy użyciu samej definicji. Niektóre dodatkowe operacje są wymagane do obliczenia potęgi 2 , ale w binarnej arytmetyce można to zrobić tanio (w zależności od tego, co dokładnie jest wymagane, może wymagać jedynie dodania przyrostka 2 k - 1 zer).2)2)k-2)2)2)k-1

Poniższy kod Ruby implementuje uproszczoną wersję tego. Nie pozwala to uniknąć ponownego obliczanianawet tam, gdzie może to zrobić:n?

def oddprod(l,h)
  p = 1
  ml = (l%2>0) ? l : (l+1)
  mh = (h%2>0) ? h : (h-1)
  while ml <= mh do
    p = p * ml
    ml = ml + 2
  end
  p
end

def fact(k)
  f = 1
  for i in 1..k-1
    f *= oddprod(3, 2 ** (i + 1) - 1)
  end
  2 ** (2 ** k - 1) * f
end

print fact(15)

Nawet ten kod pierwszego przejścia poprawia banalność

f = 1; (1..32768).map{ |i| f *= i }; print f

o około 20% w moich testach.

Przy odrobinie pracy można to jeszcze ulepszyć, usuwając również wymóg, aby była potęgą 2 (patrz obszerna dyskusjan2) ).

András Salamon
źródło
Pominąłeś ważny czynnik. Czas obliczeń według pracy Borweina nie jest równy O (n log n log log n). Jest to O (M (n log n) log n), gdzie M (n log n) to czas pomnożenia dwóch liczb o rozmiarze n log n.
gnasher729
18

Pamiętaj, że funkcja silnia rośnie tak szybko, że będziesz potrzebować liczb całkowitych o dowolnej wielkości, aby uzyskać korzyści z bardziej wydajnych technik niż naiwne podejście. Silnia 21 jest już zbyt duża, aby zmieścić się w wersji 64-bitowej unsigned long long int.

n!n ), która jest szybsza niż mnożenie.¹

Θ(|za||b|)|x|xΩ(|za|+|b|)max(|za|,|b|)

Uzbrojony w to tło, artykuł Wikipedii powinien mieć sens.

Ponieważ złożoność mnożenia zależy od wielkości liczb całkowitych, które są mnożone, można zaoszczędzić czas, ustawiając mnożenia w kolejności, w której liczby są mnożone. Działa to lepiej, jeśli liczby są mniej więcej tego samego rozmiaru. „Podział na pół”, do którego odnosi się twój podręcznik, składa się z następujących elementów podejścia dziel i zwyciężaj, aby pomnożyć (wiele) zestaw liczb całkowitych:

  1. 1n) w dwóch zestawach, których produkt ma w przybliżeniu ten sam rozmiar. Jest to o wiele tańsze niż mnożenie:|zab||za|+|b| (jeden dodatek do maszyny).
  2. Zastosuj algorytm rekurencyjnie do każdego z dwóch podzbiorów.
  3. Pomnóż dwa wyniki pośrednie.

Więcej informacji znajduje się w instrukcji GMP .

Istnieją jeszcze szybsze metody, które nie tylko zmieniają czynniki 1 do nale podzielił liczby, rozkładając je na ich pierwotne rozkładanie na czynniki pierwsze i przestawiając wynikowy bardzo długi iloczyn głównie małych liczb całkowitych. Przytoczę tylko odniesienia do artykułu z Wikipedii: „O złożoności obliczania czynników czynnikowych” Petera Borweina i implementacji Petera Luschnego .

Đ Są szybsze sposoby obliczania aproksymacje zn!, ale to już nie oblicza silni, lecz jej przybliżenie.

Gilles „SO- przestań być zły”
źródło
9

Ponieważ funkcja silnia rośnie tak szybko, twój komputer może tylko przechowywać n! dla stosunkowo małych n. Na przykład podwójne może przechowywać wartości do171!. Więc jeśli chcesz naprawdę szybkiego algorytmu obliczeniowegon!, po prostu użyj tabeli rozmiarów 171.

Pytanie staje się bardziej interesujące, jeśli jesteś zainteresowany log(n!) lub w Γ funkcja (lub w logΓ). We wszystkich tych przypadkach (w tymn!), Tak naprawdę nie rozumiem komentarza w twoim podręczniku.

Nawiasem mówiąc, twoje algorytmy iteracyjne i rekurencyjne są równoważne (do błędów zmiennoprzecinkowych), ponieważ używasz rekurencji ogona.

Yuval Filmus
źródło
„twoje algorytmy iteracyjne i rekurencyjne są równoważne”, mówisz o ich asymptotycznej złożoności, prawda? jeśli chodzi o komentarz w podręczniku, to tłumaczę go z innego języka, więc może moje tłumaczenie jest do bani.
user65165
Książka mówi o iteracyjnych i rekurencyjnych, a następnie komentuje, jak użyć dzielenia i podbijania, aby podzielić n! o połowę można uzyskać znacznie szybsze rozwiązanie ...
user65165
1
Moje pojęcie równoważności nie jest całkowicie formalne, ale można powiedzieć, że wykonywane operacje arytmetyczne są takie same (jeśli zmienisz kolejność argumentów w algorytmie rekurencyjnym). „Z natury” inny algorytm wykona inne obliczenia, być może wykorzystując jakąś „sztuczkę”.
Yuval Filmus,
1
Jeśli weźmiesz pod uwagę wielkość liczby całkowitej jako parametr w złożoności mnożenia, ogólna złożoność może ulec zmianie, nawet jeśli operacje arytmetyczne są „takie same”.
Tpecatte
1
@CharlesOkwuagwu Racja, możesz użyć stołu.
Yuval Filmus