Better upper bounds on the QOBDD size of integer multiplication Original Research Article

We show that the middle bit of the multiplication of two n-bit integers can be computed by an ordered binary decision diagram (OBDD) of size less than 2.8·26n/52.8·26n/5. This improves the previously known upper bound of View the MathML source(73)·24n/3 by Woelfel (New Bounds on the OBDD-size of integer multiplication via Universal Hashing, J. Comput. System Sci. 71(4) (2005) 520–534). The experimental results suggest that our exponent of 6n/56n/5 is optimal or at least very close to optimal. A general upper bound of O(23n/2)O(23n/2) on the OBDD size of each output bit of the multiplication is also presented.