Menor número de portas para Multiplicação

Qual é o melhor resultado para o número de portas em um circuito multiplicando dois números inteiros de n bits?

O método óbvio gera portas . Existem abordagens melhores com as portas e . $\theta(n^2)$ $\theta(n\log n \log\log n)$ $\theta(n\log n2^{\log^*(n)})$

Não encontrei nenhuma família de circuitos booleanos capaz de lidar com a multiplicação com gates. Gostaria de saber se existe uma família de circuitos. $n\log n$

cc.complexity-theory circuit-complexity Amir
fonte

você está procurando um circuito aritmético ou um circuito booleano?

Suresh Venkat

Estou à procura de um circuito booleano.

Amir

O (n \log n)

$O(n \log n)$

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

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

t (n)

$t(n)$

t (n)

$t(n)$

O (n \lg n)

$O(n\lg n)$

Respostas:

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

Multiplicação Rápida e Suas Aplicações , Bernstein (Teoria dos Números Algorítmicos / MSRI Publications / Volume 44, 2008)

vzn
fonte

O documento vinculado não possui as páginas 335 ou 336. Talvez você quisesse vincular a um arquivo diferente?

argentpepper

oops! thx por dica. versão acima marcada como rascunho. esta versão com pg #s citada talvez seja final?

vzn

@vzn:

$\:$

\log^{*} (n)

$\log^*(n)$

$\;\;\;\;$