<p>An interesting source is D. E. Knuth: <a href="http://www-cs-faculty.stanford.edu/~uno/taocp.html" rel="nofollow noreferrer">The Art of Computer Programming, Volume 4, Fascicle 1, Bitwise Tricks &amp; Techniques; Binary Decision Diagrams</a>, Addison-Wesley, Pearson Education 2009</p>

<p>On page 96, there is a BDD for all bits of z = x⋅y, where x and y have 3 bits. It shows, that in the case of 3 bits, BDD representing the most significant bit has 7 non-terminal nodes. See the image bellow, I have redraw it using your indices x = (x2,x1,x0) and y = (y2,y1,y0).</p>

<p>On page 140 in Knuth's book, there is a question (no. 183) about BDD representing the most significant bit for multiplication of two numbers with infinitely many bits (it is called "limiting leading bit function") - this is similar to what you are loking for! The answer on page 223 gives first levels of the resulting BDD and discusses the number of nodes on all levels, but unfortunatelly it does not give algorithm to construct such a BDD.</p>

<p><img src="https://i.sstatic.net/DUsIO.png" alt="The most significant bit for multiplication of two 3-bits numbers"></p>

<p>Fig. 1: The most significant bit for multiplication of (x2,x1,x0) * (y2,y1,y0)</p>

CC BY-SA 3.0
2011-10-28T21:42:26.810Z
Thank you for this reference. I didn't know that binary decision diagrams are part of this "programming encyclopedia".
Marc Bury
CC BY-SA 3.0
2011-10-28T09:31:41.320Z
2011-10-28T09:31:41.320Z
meolic
<p>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$.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 2.5
2010-12-02T17:07:23.973Z
I find the three questions in the last paragraph rather vague. Please consider making a more concrete question.
slimton
CC BY-SA 2.5
2010-12-02T19:50:02.893Z
The questions are intentionally vague. Perhaps someone has a new approach or new ideas for this problem.
Marc Bury
CC BY-SA 2.5
2010-12-03T00:47:49.160Z
Are you looking for the width of a BDD for the problem?
Sylvain Peyronnet
CC BY-SA 2.5
2010-12-14T20:10:20.257Z
I'm interested in a lower bound on the BDD size.
Marc Bury
CC BY-SA 3.0
2011-10-31T15:05:47.483Z
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
<cc.complexity-theory><binary-decision-diagrams>
Most significant bit of integer multiplication and binary decision diagrams
Marc Bury
# Most significant bit of integer multiplication and binary decision diagrams

(Asked by: username_0 on 2010-12-02)

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?

**Tags:** cc.complexity-theory, binary-decision-diagrams
> **Comments:**
> **username_1**: I find the three questions in the last paragraph rather vague. Please consider making a more concrete question.  
> **username_0**: The questions are intentionally vague. Perhaps someone has a new approach or new ideas for this problem.  
> **username_2**: Are you looking for the width of a BDD for the problem?  
> **username_0**: I'm interested in a lower bound on the BDD size.  
> **username_3**: 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$).  

---

## 1 answers

### Answer by username_4 on 2011-10-28. Score: 5

An interesting source is D. E. Knuth: [The Art of Computer Programming, Volume 4, Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams](http://www-cs-faculty.stanford.edu/~uno/taocp.html), Addison-Wesley, Pearson Education 2009

On page 96, there is a BDD for all bits of z = x⋅y, where x and y have 3 bits. It shows, that in the case of 3 bits, BDD representing the most significant bit has 7 non-terminal nodes. See the image bellow, I have redraw it using your indices x = (x2,x1,x0) and y = (y2,y1,y0).

On page 140 in Knuth's book, there is a question (no. 183) about BDD representing the most significant bit for multiplication of two numbers with infinitely many bits (it is called "limiting leading bit function") - this is similar to what you are loking for! The answer on page 223 gives first levels of the resulting BDD and discusses the number of nodes on all levels, but unfortunatelly it does not give algorithm to construct such a BDD.

![The most significant bit for multiplication of two 3-bits numbers](https://i.sstatic.net/DUsIO.png)

Fig. 1: The most significant bit for multiplication of (x2,x1,x0) \* (y2,y1,y0)

> **Comments:**
> **username_0**: Thank you for this reference. I didn't know that binary decision diagrams are part of this "programming encyclopedia".  

---

