Bit perkalian integer dan diagram keputusan biner yang paling signifikan

15

Biarkan dan y dua angka biner dengan n bit dan z = x y angka biner (panjang 2 n ) dari produk x dan y . Kami ingin menghitung bit paling signifikan z 2 n - 1 dari produk z = z 2 n - 1 ... z 0 .xynz=xy 2nxyz2n1z=z2n1z0

Untuk menganalisis kompleksitas fungsi ini dalam model diagram keputusan biner (khususnya program percabangan baca-sekali), saya mencoba mencari beberapa ekspresi setara untuk kasus . Hal pertama yang jelas adalah z 2 n - 1 = 1 x y 2 2 n - 1 (di sini x dan y adalah bilangan bulat yang sesuai dengan bilangan biner). Saya ingin mendapatkan intuisi apa yang terjadi jika saya menetapkan beberapa bit input konstan. Misalnya jika saya mengatur bit input paling signifikan dariz2n1=1z2n1=1xy22n1xy dan yxy hingga 0 Saya mendapatkan fungsi konstan 0. Tetapi bit dengan signifikansi yang lebih rendah tidak memiliki pengaruh seperti itu pada hasilnya.

Apakah ada ekspresi setara lainnya untuk kasus yang membantu lebih banyak untuk melihat apa yang terjadi jika saya memperbaiki beberapa bit input? Apakah ada metode yang disempurnakan untuk menghitung produk dari dua angka biner yang dapat membantu? Atau apakah Anda memiliki pendekatan lain untuk masalah ini?z2n1=1

Marc Bury
sumber
Saya menemukan tiga pertanyaan di paragraf terakhir agak kabur. Silakan pertimbangkan untuk membuat pertanyaan yang lebih konkret.
slimton
Pertanyaan-pertanyaan itu sengaja tidak jelas. Mungkin seseorang memiliki pendekatan baru atau ide baru untuk masalah ini.
Marc Bury
Apakah Anda mencari lebar BDD untuk masalahnya?
Sylvain Peyronnet
Saya tertarik pada batas bawah pada ukuran BDD.
Marc Bury
1
NC1

Jawaban:

5

Sumber yang menarik adalah DE Knuth: Seni Pemrograman Komputer, Volume 4, Fascicle 1, Trik & Teknik Bitwise; Diagram Keputusan Biner , Addison-Wesley, Pearson Education 2009

Pada halaman 96, ada BDD untuk semua bit z = x⋅y, di mana x dan y memiliki 3 bit. Ini menunjukkan, bahwa dalam kasus 3 bit, BDD mewakili bit paling signifikan memiliki 7 node non-terminal. Lihat gambar di bawah, saya telah menggambarnya kembali menggunakan indeks Anda x = (x2, x1, x0) dan y = (y2, y1, y0).

Pada halaman 140 dalam buku Knuth, ada pertanyaan (no. 183) tentang BDD yang mewakili bit paling signifikan untuk perkalian dua angka dengan bit yang tak terhingga banyaknya (ini disebut "membatasi fungsi bit memimpin") - ini mirip dengan apa yang Anda untuk loking! Jawaban pada halaman 223 memberikan level pertama dari BDD yang dihasilkan dan membahas jumlah node pada semua level, tetapi sayangnya tidak memberikan algoritma untuk membangun BDD seperti itu.

Bit paling signifikan untuk perkalian dua angka 3-bit

Gambar 1: Bit paling signifikan untuk perkalian (x2, x1, x0) * (y2, y1, y0)

meolic
sumber
1
Terima kasih atas referensi ini. Saya tidak tahu bahwa diagram keputusan biner adalah bagian dari "pemrograman ensiklopedia" ini.
Marc Bury