Jumlah gerbang paling sedikit untuk Penggandaan

Apa hasil terbaik untuk jumlah gerbang dalam rangkaian yang mengalikan dua bilangan bulat n-bit?

Metode yang jelas menghasilkan gerbang . Ada pendekatan yang lebih baik dengan gerbang dan . $\theta(n^2)$ $\theta(n\log n \log\log n)$ $\theta(n\log n2^{\log^*(n)})$

Saya tidak bisa menemukan keluarga sirkuit Boolean yang dapat menangani perkalian dengan gerbang. Saya ingin tahu apakah keluarga sirkuit seperti itu ada. $n\log n$

cc.complexity-theory circuit-complexity Amir
sumber

Apakah Anda mencari sirkuit aritmatika atau sirkuit boolean?

Suresh Venkat

Saya mencari sirkuit Boolean.

Amir

untuk catatan apa algoritma

? bukankah itu menggunakan banyak gerbang?

O (n \log n)

$O(n \log n)$

vzn

@vzn Tidak, algoritma Martin Fuerer adalah yang paling dikenal, dan memberikan sirkuit dengan gerbang

. Schonhage-Strassen sebenarnya digunakan dalam beberapa sistem aljabar komputer untuk jumlah yang sangat besar.

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

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

Sasho Nikolov

t (n)

$t(n)$

t (n)

$t(n)$

O (n \lg n)

$O(n\lg n)$

Jawaban:

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

Penggandaan Cepat Dan Penerapannya , Bernstein (Algorithmic Number Theory / MSRI Publications / Volume 44, 2008)

vzn
sumber

Kertas yang ditautkan tidak memiliki halaman 335 atau 336. Mungkin Anda bermaksud menautkan ke file lain?

argentpepper

Ups! thx untuk tip. versi di atas ditandai sebagai konsep. versi ini dengan pg # yang dikutip mungkin final?

vzn

@vzn:

$\:$

\log^{*} (n)

$\log^*(n)$

$\;\;\;\;$