Seja e dois números binários com bits e o número binário (comprimento ) do produto de e . Queremos calcular o bit mais significativo do produto .
Para analisar a complexidade dessa função no modelo de diagramas de decisão binária (em particular programas de ramificação de leitura única), tento procurar algumas expressões equivalentes para o caso . A primeira coisa que é óbvio (aqui e são números inteiros para os números binários correspondentes). Quero ter uma intuição do que acontece se eu definir alguns bits de entrada constantes. Por exemplo, se eu definir o bit de entrada mais significativa de e a 0 fico com a função constante 0. Mas bits com menor significado não têm tanta influência no resultado.
Existem outras expressões equivalentes para o caso que ajudam mais a ver o que acontece se eu corrigir alguns bits de entrada? Existem métodos refinados para calcular o produto de dois números binários que podem ajudar? Ou você tem alguma outra abordagem para esse problema?
Respostas:
Uma fonte interessante é DE Knuth: The Art of Computer Programming, Volume 4, Fascicle 1, Bitwise Tricks & Techniques; Diagramas de Decisão Binária , Addison-Wesley, Pearson Education 2009
Na página 96, há um BDD para todos os bits de z = x⋅y, em que x e y têm 3 bits. Mostra que, no caso de 3 bits, o BDD que representa o bit mais significativo possui 7 nós não terminais. Veja a imagem abaixo, redesenhei usando seus índices x = (x2, x1, x0) e y = (y2, y1, y0).
Na página 140 do livro de Knuth, há uma pergunta (nº 183) sobre o BDD que representa o bit mais significativo para multiplicação de dois números com infinitos bits (é chamado de "função limitadora de bit inicial") - isso é semelhante ao que você estão procurando! A resposta na página 223 fornece os primeiros níveis do BDD resultante e discute o número de nós em todos os níveis, mas infelizmente não fornece algoritmo para construir esse BDD.
Fig. 1: O bit mais significativo para multiplicação de (x2, x1, x0) * (y2, y1, y0)
fonte