El bit más significativo de la multiplicación entera y los diagramas de decisión binarios

15

Deje e dos números binarios conxyn bits y el número binario (longitud 2 n ) del producto de x e y . Queremos calcular el bit más significativo z 2 n - 1 del producto z = z 2 n - 1 ... z 0 .z=xy 2nxyz2n1z=z2n1z0

Para analizar la complejidad de esta función en el modelo de diagramas de decisión binarios (en particular, programas de ramificación de lectura única), trato de buscar algunas expresiones equivalentes para el caso . La primera cosa obvia es z 2 n - 1 = 1 x y 2 2 n - 1 (aquí x e y son los números enteros correspondientes a los números binarios). Quiero tener una intuición de lo que sucede si establezco algunos bits de entrada constantes. Por ejemplo, si configuro el bit de entrada más significativo dez2n1=1z2n1=1xy22n1xy e y a 0 obtengo la función constante 0. Pero los bits con menor importancia no tienen tanta influencia en el resultado.xy

¿Hay otras expresiones equivalentes para el caso que ayuden más a ver qué sucede si corrijo algunos bits de entrada? ¿Existen métodos refinados para calcular el producto de dos números binarios que puedan ayudar? ¿O tienes algún otro enfoque para este problema?z2n1=1

Marc Bury
fuente
Las tres preguntas del último párrafo me parecen bastante vagas. Por favor considere hacer una pregunta más concreta.
slimton
Las preguntas son intencionalmente vagas. Quizás alguien tenga un nuevo enfoque o nuevas ideas para este problema.
Marc Bury
¿Está buscando el ancho de un BDD para el problema?
Sylvain Peyronnet
Estoy interesado en un límite inferior en el tamaño de BDD.
Marc Bury
1
¿Te refieres a un límite inferior polinómico? La multiplicación está en L, por lo tanto, tiene BDD de tamaño polinómico uniforme (incluso ancho 5, ya que está en uniforme ). NC1
Emil Jeřábek apoya a Monica el

Respuestas:

5

Una fuente interesante es DE Knuth: The Art of Computer Programming, Volume 4, Fascicle 1, Bitwise Tricks & Techniques; Diagramas de decisiones binarias , Addison-Wesley, Pearson Education 2009

En la página 96, hay un BDD para todos los bits de z = x⋅y, donde x e y tienen 3 bits. Muestra que, en el caso de 3 bits, BDD que representa el bit más significativo tiene 7 nodos no terminales. Vea la imagen a continuación, la he redibujado usando sus índices x = (x2, x1, x0) e y = (y2, y1, y0).

En la página 140 del libro de Knuth, hay una pregunta (n. ° 183) acerca de que BDD representa el bit más significativo para la multiplicación de dos números con infinitos bits (se llama "función de límite de bits líder"): esto es similar a lo que usted están buscando! La respuesta en la página 223 proporciona los primeros niveles del BDD resultante y discute el número de nodos en todos los niveles, pero desafortunadamente no proporciona un algoritmo para construir dicho BDD.

El bit más significativo para la multiplicación de dos números de 3 bits.

Fig. 1: El bit más significativo para la multiplicación de (x2, x1, x0) * (y2, y1, y0)

meolic
fuente
1
Gracias por esta referencia No sabía que los diagramas de decisión binarios son parte de esta "enciclopedia de programación".
Marc Bury