The Library
Shallow multiplication circuits and wise financial investments
Tools
Tools
Tools
Paterson, Michael S. and Zwick, Uri (1992) Shallow multiplication circuits and wise financial investments. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-209.pdf - Other - Requires a PDF viewer. Download (6Mb) | Preview |
Abstract
Paterson, Pippenger and Zwick have recently obtained a general theory that describes the optimal way in which given carry-save adders can be combined into carry-save networks. Their work produces, in particular, multiplication circuits of depth 3.71 log* n (these circuits put out two numbers whose sum is the result of the multiplication). In this work an extension of the above general theory is obtained. We now consider carry-save adders that may receive inputs and produce outputs using several different representation methods. We describe the optimal way of utilising any such collection of carry-save adders. The optimality proof uses the min-max theorem of game theory. By using several different representation standards, the depth of multiplication circuits can be surprisingly reduced to 3.48 log* n (again two output numbers are produced). We introduce bit level redundancy by using a novel coding scheme in which each bit is distributed over four wires. Interestingly, the information on these four wires is usually not transmitted simultaneously. Finally, an analogy is made between the optimisation problem faced by the circuit designer and the optimisation problem faced by an investor, offered a collection of financial investment plans, each involving perhaps several different currencies. This analogy is used to obtain intuitive explanations of the results obtained.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Computer arithmetic and logic units | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | 1992 | ||||
| Dates: |
|
||||
| Number: | Number 209 | ||||
| Number of Pages: | 14 | ||||
| DOI: | CS-RR-209 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | Michael Paterson and Uri Zwick, “Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication”, <i>Computational Complexity</i> <b>3</b>(3), pp. 262-291 (1993) | ||||
| Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | 3075 (ESPRIT) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
