Najbardziej znaczący bit mnożenia liczb całkowitych i diagramy decyzji binarnych

Niech i dwa binarne liczby z bitów i liczby binarnej (o długości ) produktu z i . Chcemy obliczyć najbardziej znaczący bit produktu . $x$ $y$ $n$ $z = x \cdot y\$ $2n$ $x$ $y$ $z_{2n-1}$ $z = z_{2n-1} \ldots z_0$

Aby przeanalizować złożoność tej funkcji w modelu binarnych diagramów decyzyjnych (w szczególności programów rozgałęziających read-once) staram się poszukać równoważnych wyrażeń dla przypadku . Pierwszy oczywiste jest to, (tu i są liczbami całkowitymi, do odpowiednich liczb binarnych). Chcę uzyskać intuicję, co się stanie, jeśli ustawię niektóre bity wejściowe na stałe. Np. Jeśli ustawię najbardziej znaczący bit wejściowy z $z_{2n-1} = 1$ $z_{2n-1} = 1 \Leftrightarrow x \cdot y \geq 2^{2n-1}$ $x$ $y$ i do 0 uzyskać funkcję stałą 0. Ale bity o niższym znaczeniu nie mają takiego wpływu na wynik. $x$ $y$

Czy istnieją inne równoważne wyrażenia dla przypadku które pomagają bardziej zobaczyć, co się stanie, jeśli naprawię niektóre bity wejściowe? Czy są jakieś udoskonalone metody obliczania iloczynu dwóch liczb binarnych, które mogą pomóc? Czy masz jakieś inne podejście do tego problemu? $z_{2n-1} = 1$

cc.complexity-theory binary-decision-diagrams

— Marc Bury
źródło

Trzy pytania w ostatnim akapicie uważam za dość niejasne. Rozważ bardziej konkretne pytanie.

— slimton,

Pytania są celowo niejasne. Być może ktoś ma nowe podejście lub nowe pomysły na ten problem.

— Marc Bury,

Szukasz szerokości BDD dla problemu?

— Sylvain Peyronnet,

Interesuje mnie dolna granica rozmiaru BDD.

— Marc Bury,

Masz na myśli wielomian dolną granicę? Mnożenie w L, a więc posiada jednolite BDDs wielomian wymiarach (szerokość nawet 5, ponieważ jest w jednolity

{N C}^{1}

$\mathrm{NC}^1$

— Emil Jeřábek wspiera Monikę

Ciekawym źródłem jest DE Knuth: The Art of Computer Programming, Tom 4, Fascicle 1, Bitwise Tricks & Techniques; Diagramy decyzji binarnych , Addison-Wesley, Pearson Education 2009

Na stronie 96 znajduje się BDD dla wszystkich bitów z = x⋅y, gdzie xiy mają 3 bity. Pokazuje, że w przypadku 3 bitów BDD reprezentujący najbardziej znaczący bit ma 7 węzłów nieterminalnych. Zobacz obrazek poniżej, przerysowałem go za pomocą twoich wskaźników x = (x2, x1, x0) iy = (y2, y1, y0).

Na stronie 140 książki Knutha znajduje się pytanie (nr 183) dotyczące BDD reprezentującego najbardziej znaczący bit do pomnożenia dwóch liczb z nieskończenie wieloma bitami (nazywa się to „ograniczającą funkcją bitów wiodących”) - jest podobny do tego, co szukają! Odpowiedź na stronie 223 podaje pierwsze poziomy wynikowego BDD i omawia liczbę węzłów na wszystkich poziomach, ale niestety nie podaje algorytmu konstruowania takiego BDD.

Najbardziej znaczący bit dla pomnożenia dwóch liczb 3-bitowych

Ryc. 1: Najbardziej znaczący bit dla mnożenia (x2, x1, x0) * (y2, y1, y0)

— meolic
źródło

Dziękuję za to odniesienie. Nie wiedziałem, że diagramy decyzji binarnych są częścią tej „encyklopedii programowania”.

— Marc Bury,