An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division

Masaki NAKANISHI  Kiyoharu HAMAGUCHI  Toshinobu KASHIWABARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.5   pp.756-766
Publication Date: 1999/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
binary moment diagram,  division,  lower bound,  

Full Text: PDF>>
Buy this Article




Summary: 
A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binary-vectors to integers (f : {0,1}n Z). A multiplicative binary moment diagram is an extension of a binary moment diagram with edge weights attached. A multiplicative binary moment diagram can represent addition, multiplication and many other functions with polynomial numbers of vertices. Lower bounds for division, however, had not been investigated. In this paper, we show an exponential lower bound on the number of vertices of a multiplicative binary moment diagram representing a quotient function or a remainder function.