15
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ I find the three questions in the last paragraph rather vague. Please consider making a more concrete question. $\endgroup$
    – slimton
    Dec 2, 2010 at 17:07
  • $\begingroup$ The questions are intentionally vague. Perhaps someone has a new approach or new ideas for this problem. $\endgroup$
    – Marc Bury
    Dec 2, 2010 at 19:50
  • $\begingroup$ Are you looking for the width of a BDD for the problem? $\endgroup$
    – Sylvain Peyronnet
    Dec 3, 2010 at 0:47
  • $\begingroup$ I'm interested in a lower bound on the BDD size. $\endgroup$
    – Marc Bury
    Dec 14, 2010 at 20:10
  • 1
    $\begingroup$ 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$). $\endgroup$
    – Emil Jeřábek
    Oct 31, 2011 at 15:05

1 Answer 1

Reset to default
5
$\begingroup$

An interesting source is D. E. Knuth: The Art of Computer Programming, Volume 4, Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams, 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

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you for this reference. I didn't know that binary decision diagrams are part of this "programming encyclopedia". $\endgroup$
    – Marc Bury
    Oct 28, 2011 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.