Najmniejsza liczba bramek do mnożenia

Jaki jest najlepszy wynik dla liczby bramek w obwodzie pomnożącym dwie liczby całkowite n-bitowe?

Oczywista metoda generuje bramki . Istnieją lepsze podejścia z i . $\theta(n^2)$ $\theta(n\log n \log\log n)$ $\theta(n\log n2^{\log^*(n)})$

Nie mogłem znaleźć żadnej rodziny obwodów boolowskich, która obsługiwałaby mnożenie za pomocą bramek . Zastanawiam się, czy istnieje taka rodzina obwodów. $n\log n$

cc.complexity-theory circuit-complexity

— Amir
źródło

szukasz obwodu arytmetycznego lub logicznego?

— Suresh Venkat

Szukam obwodu logicznego.

— Amir

dla rekordu jaki jest algorytm ? czy nie użyłby tylu bram?

O (n \log n)

$O(n \log n)$

— vzn

@vzn Nie, algorytm Martina Fuerera jest najlepiej znany i daje obwód z bramkami . Schonhage-Strassen jest faktycznie używany w niektórych systemach algebry komputerowej dla bardzo dużych liczb.

O (n \log n 2^{\log^{*} n})

$O(n\log n 2^{\log^* n})$

— Sasho Nikolov

Jest trochę narzutów, aby zmienić TM w obwód. Drzwi algorytmu czasu nie dają obwodu z bramkami . Ogólne tłumaczenie nie może być lepsze niż złożoność obwodu problemu z wartością obwodu. Z drugiej strony, najlepsza jednorodna złożoność nie implikuje niższego ograniczenia złożoności obwodu, ponieważ istnieje narzut również w odwrotnym kierunku, tj. Mogą istnieć obwody o wielkości nawet jeśli nie ma z tym TM czas działania do pomnożenia.

t (n)

$t(n)$

t (n)

$t(n)$

O (n \lg n)

$O(n\lg n)$

— Kaveh

Poniżej znajduje się szczegółowa ankieta z 2008 r., Która obejmuje najlepsze teoretyczne algorytmy mnożenia, w tym te omówione w komentarzach do twojego pytania (w tym algorytm Schönhage – Strassen i Algorytm Fuerera, patrz strona 335 ankiety). Jednak implementacja to inna sprawa i niektóre z tych algorytmów mogą nie być uważane za praktyczne; ankieta nie obejmuje praktycznych wdrożeń. Chociaż badanie obejmuje algorytmy wielomianów, szeregów mocy, liczb rzeczywistych i liczb 2-adycznych, ich szczególnym przypadkiem są liczby całkowite (patrz Rysunek 1 na stronie 336). $O(n\log n \, 2^{\log^* n})$

Szybkie mnożenie i jego zastosowania , Bernstein (Teoria liczb algorytmicznych / MSRI Publications / Tom 44, 2008)

— vzn
źródło

Powiązany artykuł nie ma stron 335 ani 336. Być może chciałeś utworzyć link do innego pliku?

— argentpepper

ups! dzięki za wskazówkę. powyżej wersji oznaczonej jako wersja robocza. ta wersja z cytowanymi pg #s jest może ostateczna?

— vzn

@vzn: Nawet ten papier ma duże-O wokół .

$\:$

\log^{*} (n)

$\log^*(n)$

$\;\;\;\;$