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

Niech i y dwa binarne liczby z n bitów i oo = x ⋅ y liczby binarnej (o długości 2 n ) produktu z x i y . Chcemy obliczyć najbardziej znaczący bit z 2 n - 1 produktu z = z 2 n - 1 … z 0 .$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, z 2 n - 1 = 1 ⇔ x ⋅ Y ≥ 2 2 n - 1 (tu x i y 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 y 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$

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.

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