Bit mais significativo de multiplicação de números inteiros e diagramas de decisão binária

15

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 .xynz=xy 2nxyz2n-1 1z=z2n-1 1...z0 0

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.z2n-1 1=1 1z2n-1 1=1 1xy22n-1 1xyxy

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?z2n-1 1=1 1

Marc Bury
fonte
Acho as três perguntas no último parágrafo bastante vagas. Por favor, considere fazer uma pergunta mais concreta.
slimton
As perguntas são intencionalmente vagas. Talvez alguém tenha uma nova abordagem ou novas idéias para esse problema.
Marc Bury
Você está procurando a largura de um BDD para o problema?
Sylvain Peyronnet
Estou interessado em um limite inferior para o tamanho do BDD.
Marc Bury
11
Você quer dizer um limite inferior polinomial? A multiplicação é em L, portanto, possui BDDs de tamanho polinomial uniforme (largura uniforme 5, pois é uniforme ). NC1 1
Emil Jeřábek apoia Monica

Respostas:

5

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.

O bit mais significativo para multiplicação de dois números de 3 bits

Fig. 1: O bit mais significativo para multiplicação de (x2, x1, x0) * (y2, y1, y0)

meólico
fonte
11
Obrigado por esta referência. Eu não sabia que os diagramas de decisão binária fazem parte dessa "enciclopédia de programação".
Marc Bury