Mnożenie liczb całkowitych, gdy jedna liczba całkowita jest ustalona

Niech $A$ będzie stałą dodatnią liczbą całkowitą o rozmiarze $n$ bitów.

Można odpowiednio wstępnie przetworzyć tę liczbę całkowitą.

Biorąc pod uwagę kolejną dodatnią liczbę całkowitą $B$ o rozmiarze $m$ bitów, jaka jest złożoność mnożenia $AB$ ?

ϵ = $(\max(n,m))^{1+\epsilon}$$\epsilon=0$

Chociaż nie zawsze będzie to najbardziej wydajny algorytm, pytanie to ma bardzo ścisły związek z łańcuchami dodawania; każdy algorytm do obliczania szybko łańcuchów addycyjnych przekłada się na algorytmie obliczania F ( B ) = A B przez powtarzane dodawanie (każdy dodatek oczywiście będąc O ( n ) działanie). Przeciwnie, szybki algorytm do obliczania A B dla dowolnego B prowadzi do szybkiego algorytmu do obliczania A.A$A$$A$$f(B) = AB$$O(n)$$AB$$B$$A$, ale oczywiście ten algorytm niekoniecznie musi mieć postać łańcucha dodatków; nadal wydaje się, że jest to doskonałe miejsce na początek. Zajrzyj na http://en.wikipedia.org/wiki/Addition_chain lub sprawdź vol. 2 sztuki programowania komputerowego po więcej szczegółów.

Aby rozwinąć pomysł Stevena Stadnickiego, możemy szybko skonstruować naiwny algorytm, który działa lepiej niż mnożenie macierzy za pomocą dyskretnej transformaty Fouriera.

Liczymy liczbę jedynek w . Jeśli mniej niż połowa bitów to jedności, tworzymy połączoną listę ich pozycji. Aby pomnożyć, po prostu przesuwamy B w lewo o każdą pozycję na liście (mnożąc przez ten reprezentowany bit) i dodajemy wyniki.$A$$B$

Jeśli więcej niż połowa bitów to jedności, robimy to samo, co powyżej, ale zamiast tego używamy zer, aby zapełnić listę pozycji. Chodzi o to, że odejmiemy tę sumę od sumy, która zostałaby uzyskana przez pomnożenie przez wszystkie. Aby uzyskać sumę wszystkich, przesuwamy o liczbę bitów w A i odejmujemy B od tego. Następnie możemy odjąć naszą sumę uzyskaną z połączonej listy.$B$$A$$B$

Możemy to nazwać naiwnym algorytmem listy połączonej. Jego czas działania wynosi w najgorszym przypadku, ale O ( | B | $O(n^2)$w średnim przypadku, który jest szybszy niż DFT dla małych| A| .$O(|B| \sqrt{\frac{|A|}{2\pi}})$$|A|$

Aby optymalnie wykorzystać ideę list, używamy podziału i podboju. Dzielimy na pół i znajdujemy rozmiary powiązanych list przy użyciu naiwnego algorytmu. Jeśli są większe niż 5, ponownie wywołujemy naiwny algorytm na połówkach większych niż 5, dopóki nie uda nam się przeciąć wszystkich połówek na mniej niż pięć. (Jest tak, ponieważ możemy zmniejszyć to do 4 odejmowań)$A$

Jeszcze lepiej, ulepszamy nasz algorytm dziel i zwyciężaj. Iterujemy wszystkie możliwe kombinacje rozgałęzień, łapczywie wybierając najlepszą. To wstępne przetwarzanie zajmuje mniej więcej tyle samo czasu, co rzeczywiste pomnożenie.

Jeśli mamy wstęp do nieskończonej swobody dzięki przetwarzaniu wstępnemu, optymalnie rozwiązujemy zoptymalizowany algorytm dziel i zwyciężaj dla wszystkich gałęzi. W najgorszym przypadku wymaga to czasu , ale powinno być optymalne metodami łańcucha addycyjnego.$O(2^{|A|})$

Pracuję nad obliczeniem dokładniejszych wartości dla powyższych algorytmów.

Artykuł o nazwie Mnożenie przez stałą jest sublinearny ( PDF ) podaje algorytm dla operacje przesunięcia / dodania, gdzienjest rozmiarem stałej.$\mathcal{O}\left(\frac{n}{\log n}\right)$$n$

Zasadniczo działa, szukając bitów w stałej, przesuwając i dodając liczbę do pomnożenia tylko dla tych 1 bitów w stałej (jak długie mnożenie dla binarnych, gdzie 0 bit w dolnej liczbie do pomnożenia oznacza góra nie jest przesunięta i dodana, a 1 bit oznacza, że ​​góra jest przesunięta i dodana). Jest to jednak nadal O ( n ) , ponieważ w stałej może być O ( n ) 1- bitów.$1$$1$$0$$1$$\mathcal{O}\left(n\right)$$\mathcal{O}(n)$ $1$

Papier następnie mówi o zmianie reprezentacji liczby stałej w systemie liczbowym podwójnej bazowej, gdzie najwyraźniej, że nie- bits są rzadszy, jeśli konwersja jest wykonywana prawidłowo (jest to bardzo zbędny system liczbowy). Obliczają, jak rzadki jest; liczba niezerowych bitów jest ograniczona do mniejszej niż O ( n ) , dlatego wymagana jest podliniowa liczba dodatków. Jednak nadal jest to O ( n $0$$\mathcal{O}(n)$rzeczywiste operacje ze względu nakosztO(m)każdego dodania (gdzienjest rozmiarem stałej, amjest rozmiarem drugiej liczby).$\mathcal{O}\left(\frac{nm} {\log n}\right)$$\mathcal{O}(m)$$n$$m$

Tak więc, aby odpowiedzieć na twoje pytanie, tak, jest podobny wynik do mnożenia macierzy-wektora, w którym otrzymujesz przyspieszenie jeśli jest stałe; ale oczywiście to przyspieszenie kończy się tylko naiwnym długim mnożeniem i istnieją algorytmy mnożenia, które są znacznie lepsze niż O ( n $\log n$można uzyskać za pomocą tego algorytmu.$\mathcal{O}\left(\frac{n^2} {\log n}\right)$

Jak sugeruje Matt Groff, możesz zainteresować się inspiracją w społeczności praktyków (lub jeśli w twojej sytuacji mieści się w zakresie szerokości bitów bieżącego procesora). Rzeczywiście, problem mnożenia liczb całkowitych przez stałą był rozważany przez wielu autorów kompilatorów i projektantów obwodów, chociaż zwykle są oni zainteresowani „multiplikatorem bez mnożnika” (mnożenie za pomocą shift, dodawania i odejmowania). Jednym z pierwszych odniesień, o których wiem, jest (dowiedziałem się tego z rozdziału 8.4 Hacker's Delight):$n$

Bernstein, R. (1986), Mnożenie przez stałe całkowite. Oprogramowanie: Practice and Experience, 16: 641–652. doi: 10.1002 / spe.4380160704

Bardziej nowoczesne dzieło Vincenta Lefèvre'a można znaleźć tutaj (koniecznie zapoznaj się z jego kontynuacją), a także zauważa projekt CMU dotyczący wydajnej syntezy obwodów (patrz odnośniki). Ten ostatni projekt rozważa nawet jednoczesne mnożenie przez zbiór stałych.

PS Zachęcam do rozważenia zmiany nazwy użytkownika na rozpoznawalną.

Nie jestem pewien, czy ma to bezpośredni związek z pytaniem, ale następujący elementarny wynik może być interesujący. Biorąc pod uwagę stałą liczbę naturalną , operacja n → k n może być realizowana przez automat sekwencyjny, pod warunkiem, że n jest zapisany w odwróconej notacji binarnej (to znaczy Najpierw bit o znaczącej wartości). Liczba stanów automatu wynosi k / 2 r, gdzie 2 r jest największą potęgą 2 dzielących k . Na przykład operacja n → 6 n jest realizowana przez następujący automat. $k$$n \to kn$$n$$k/2^r$$2^r$$2$$k$$n \to 6n$

Na przykład i 6 × 185 = 1110 = 2 + 4 + 16 + 64 + 1024 . Tak więc, w odwrotnym systemie binarnym, 185 zapisano jako 10011101, a 1110 (zły wybór, wiem ...) jako 01101010001 . Przetwarzanie wpisu 10011101 w tym automacie daje ścieżkę 0 → 0 1 ∣ 1 →$185 = 1 + 8 + 16 + 32 + 128$$6 \times 185 = 1110 = 2 + 4 + 16 + 64 + 1024$$185$$10011101$$1110$$01101010001$$\color{red}{10011101}$ co daje prawidłowe wyjście01101010001. Typ sekwencyjnego automatu, którego tu używam, został nazwanyprzez Schützenbergerpodsekwencyjnie: jak widać, istniejepoczątkowy prefiks(w kolorze zielonym) ifunkcja wyjścia terminala

$$\xrightarrow{\color{green}0} 0 \xrightarrow{\color{red}1\mid \color{blue}1} 1 \xrightarrow{\color{red}0\mid \color{blue}1} 0 \xrightarrow{\color{red}0\mid \color{blue}0} 0 \xrightarrow{\color{red}1\mid \color{blue}1} 1 \xrightarrow{\color{red}1\mid \color{blue}0} 2 \xrightarrow{\color{red}1\mid \color{blue}1} 2 \xrightarrow{\color{red}0\mid \color{blue}0} 1 \xrightarrow{\color{red}1\mid \color{blue}0} 2 \xrightarrow{\color{green}{01}}$$ $\color{blue}{01101010001}$(także w kolorze zielonym). Aby uzyskać więcej informacji na temat tego, jak można sekwencyjnie obliczać tę maszynę sekwencyjną, zobacz ten link .