Algorytm czynnikowy jest bardziej wydajny niż naiwne mnożenie

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ć?

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 Ω ( $n!$$O(n(\log n)^3\log \log n)$ czas wymagany podczas korzystania z definicji.$\Omega(n^2 \log n)$

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

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 n ⋅ 3 ⋅ 5 ⋅ 7 ⋯ ( 2 n $n?$$1 \cdot 3 \cdot 5 \dotsm (2n-1)$$(2n)! = 1 \cdot 2 \cdot 3 \dotsm (2n)$ Załóżmy teraz, że n

$$(2n)! = n! \cdot 2^n \cdot 3 \cdot 5 \cdot 7 \dotsm (2n-1).$$ 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^k$$k>0$$n$$(2^k)! = (2^{k-1})!2^{2^{k-1}}(2^{k-1})?$ Komputery( 2 k - 1 ) $$(2^k)! = \left(2^{2^{k-1}+2^{k-2}+\dots+2^0}\right) \prod_{i=0}^{k-1} (2^i)? = \left(2^{2^k - 1}\right) \prod_{i=1}^{k-1} (2^i)?.$$ $(2^{k-1})?$ 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 dyskusja$n$$2$ ).

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.¹

$\Theta(|a| \cdot |b|)$$|x|$$x$$\Omega(|a| + |b|)$$\max(|a|,|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. $1$$n$) w dwóch zestawach, których produkt ma w przybliżeniu ten sam rozmiar. Jest to o wiele tańsze niż mnożenie:$|a \cdot b| \approx |a| + |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 $n$ale 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 z$n!$, ale to już nie oblicza silni, lecz jej przybliżenie.}

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 do$171!$. Więc jeśli chcesz naprawdę szybkiego algorytmu obliczeniowego$n!$, po prostu użyj tabeli rozmiarów $171$.

Pytanie staje się bardziej interesujące, jeśli jesteś zainteresowany $\log(n!)$ lub w $\Gamma$ funkcja (lub w $\log \Gamma$). We wszystkich tych przypadkach (w tym$n!$), 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.