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

Odpowiedzi:

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)$

$\;\;\;\;$