<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-169

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

M.S. Paterson and U. Zwick, Shallow Multiplication Circuits (December 1, 1990).

Abstract

Ofman, Wallace and others used carry save adders to design multiplication circuits whose total delay is proportional to the logarithm of the length of the two numbers multiplied. An extension of their work is presented here. The first part presents a general theory describing the optimal way in which given carry save adders can be combined into carry save networks. In the second part, two new designs of basic carry save adders are described. Using these building blocks and the above general theory, the shallowest know theoretical circuits for multiplication are obtained.

<%@ include file="cited.html" %>

Michael Paterson and Uri Zwick, "Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication", Computational Complexity 3(3), pp. 262-291 (1993)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>