# Most significant bit of integer multiplication and binary decision diagrams

Let $x$ and $y$ two binary numbers with $n$ bits and $z = x \cdot y\$ the binary number (length $2n$) of the product of $x$ and $y$. We want to compute the most siginifcant bit $z_{2n-1}$ of the product $z = z_{2n-1} \ldots z_0$.

In order to analyse the complexity of this function in the model of binary decision diagrams (in particular read-once branching programs) I try to look for some equivalent expressions for the case $z_{2n-1} = 1$. The first obvious thing is $z_{2n-1} = 1 \Leftrightarrow x \cdot y \geq 2^{2n-1}$ (here $x$ and $y$ are the corresponding integers to the binary numbers). I want to get an intuition what happens if I set some input bits constant. E.g. if I set the most significant input bit from $x$ and $y$ to 0 I get the constant 0 function. But bits with lower significance haven't such an influence on the result.

Are there any other equivalent expressions for the case $z_{2n-1} = 1$ which help more to see what happens if I fix some input bits? Are there any refined methods to compute the product of two binary numbers which can help? Or do you have some other approach to this problem?

• I find the three questions in the last paragraph rather vague. Please consider making a more concrete question. – slimton Dec 2 '10 at 17:07
• The questions are intentionally vague. Perhaps someone has a new approach or new ideas for this problem. – Marc Bury Dec 2 '10 at 19:50
• Are you looking for the width of a BDD for the problem? – Sylvain Peyronnet Dec 3 '10 at 0:47
• I'm interested in a lower bound on the BDD size. – Marc Bury Dec 14 '10 at 20:10
• You mean a polynomial lower bound? Multiplication is in L, hence it has uniform polynomial-size BDDs (even width 5, since it is in uniform $\mathrm{NC}^1$). – Emil Jeřábek Oct 31 '11 at 15:05