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

35

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$

— T ....
źródło

6

Biorąc pod uwagę , po prostu stwórz tabelę wyszukiwania z wpisami. (Oczywiście nie tego chciałeś, ale myślę, że powinieneś sprecyzować swoje wymagania ...)

A

$A$

2^{n}

$2^n$

— Jukka Suomela,

9

Myślę, że pytanie to ma sens w standardowym modelu obwodu logicznego.

— Noam

4

Czy mógłbyś podsumować oczywiste górne i dolne granice oraz najlepsze wyniki, których jesteś świadomy? Pokazuje, że zależy ci na problemie i że o nim pomyślałeś, i zachęca wszystkich do myślenia o twoim problemie.

— Robin Kothari,

4

Myślę, że pytający domyślnie oznacza, że wstępnie przetworzona część musi zająć tylko miejsca. (Multimetryczny wektor macierzowy ma tę właściwość.)

n^{O (1)}

$n^{O(1)}$

— Ryan Williams

Chciałbym wiedzieć, co chcesz; Czuję, że mógłbym przejść przez niekończące się sprawy w tej sprawie. To moja pierwsza odpowiedź, dlatego szczególnie cieszę się, że mogę dać ci jak najwięcej informacji. Jeśli chcesz, możesz wysłać mi wiadomość e-mail na adres mgroff100@hotmail.com, a chętnie z Tobą będę pracować o wiele więcej.

— Matt Groff,

20

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 przez powtarzane dodawanie (każdy dodatek oczywiście będąc działanie). Przeciwnie, szybki algorytm do obliczania dla dowolnego prowadzi do szybkiego algorytmu do obliczania $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.

— Steven Stadnicki
źródło

17

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 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 i odejmujemy 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(n^2)$ w średnim przypadku, który jest szybszy niż DFT dla małych. $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.

— Matt Groff
źródło

Cześć Matt: Co to jest

i

?

| A |

$|A|$

| B |

$|B|$

— T ....

jest wielkości

, w zasadzie liczba elementów w

. Jest to równoważne z twoim

, tj.

. To samo dotyczy

. Jednakże, wzór ten nadal jest, gdy

jest różne dla

i

.

| A |

$|A|$

A

$A$

A

$A$

n

$n$

| A | \equiv n

$|A| \equiv n$

| B |

$|B|$

n

$n$

A

$A$

B

$B$

— Matt Groff,

17

Artykuł o nazwie Mnożenie przez stałą jest sublinearny ( PDF ) podaje algorytm dla operacje przesunięcia / dodania, gdziejest 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 bitów w stałej (jak długie mnożenie dla binarnych, gdzie bit w dolnej liczbie do pomnożenia oznacza góra nie jest przesunięta i dodana, a bit oznacza, że góra jest przesunięta i dodana). Jest to jednak nadal , ponieważ w stałej może być 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ż , dlatego wymagana jest podliniowa liczba dodatków. Jednak nadal jest to $0$ $\mathcal{O}(n)$ rzeczywiste operacje ze względu nakosztkażdego dodania (gdziejest rozmiarem stałej, ajest 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ż $\log n$ można uzyskać za pomocą tego algorytmu. $\mathcal{O}\left(\frac{n^2} {\log n}\right)$

— Realz Slaw
źródło

@JAS to moja specjalność: D.

— Realz Slaw

3

Pojawił się w ARITH 2007 jako dx.doi.org/10.1109/ARITH.2007.24 (dla kompletności).

— András Salamon,

10

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

— Maverick Woo
źródło

8

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 może być realizowana przez automat sekwencyjny, pod warunkiem, że jest zapisany w odwróconej notacji binarnej (to znaczy Najpierw bit o znaczącej wartości). Liczba stanów automatu wynosi gdzie jest największą potęgą dzielących . Na przykład operacja 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 . Tak więc, w odwrotnym systemie binarnym, zapisano jako a (zły wybór, wiem ...) jako . Przetwarzanie wpisu w tym automacie daje ścieżkę $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ście. Typ sekwencyjnego automatu, którego tu używam, został nazwanyprzez Schützenbergerpodsekwencyjnie: jak widać, istniejepoczątkowy prefiks(w kolorze zielonym) ifunkcja wyjścia terminala

\overset{0}{\to} 0 \overset{1 ∣ 1}{\to} 1 \overset{0 ∣ 1}{\to} 0 \overset{0 ∣ 0}{\to} 0 \overset{1 ∣ 1}{\to} 1 \overset{1 ∣ 0}{\to} 2 \overset{1 ∣ 1}{\to} 2 \overset{0 ∣ 0}{\to} 1 \overset{1 ∣ 0}{\to} 2 \overset{01}{\to}

$\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}}$

01101010001

$\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 .

— J.-E. Kołek
źródło

Czy mógłbyś rozwinąć swój komentarz?

— J.-E.

k

$k$

> 2

$>2$

n \to k n

$n \to kn$

k

$k$

k

$k$ główny.

— J.-E. Pin

\frac{k}{2^{r}}

$\frac{k}{2^r}$ is exponential.

— T ....

k

$k$ jest stałą stałą, niezwiązaną z

n

$n$ .

— J.-E. Pin