
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

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.E82A
No.5
pp.756766 Publication Date: 1999/05/25 Online ISSN:
DOI: Print ISSN: 09168508 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>>
Summary:
A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binaryvectors 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.

