On the minimum computation time of functions 论文

摘要

I. Machines with a Bounded Number of Active Elements1. Introduction.An underlying goal of the research reported here is to develop a theory showing that the process of multiplying decimal integers is intrinsically more difficult than the process of adding them (2).In part I of this paper we present a precise conjecture which is a possible formulation of this proposition.The formulation is not completely satisfactory, but it certainly bears on the problem and raises interesting mathematical questions.Part II contains a proof of a weakened form of the conjecture.There are several different ways in which multiplication seems to be more difficult than addition, and each could lead to a different formulation of the problem.For example, experience of computer designers indicates that it takes more circuitry to compute the fixed-point product of two «-digit integers than to find the sum.Again, even with the increased circuitry, the time required to carry out the multiplication exceeds that for addition.But still a third way in which the difficulties seem to differ is suggested not by computers, but by our centuries old experience with longhand multiplication.If a man is equipped only with paper and pencil, in general it will take him longer to multiply two numbers than to add them.It is this experience with longhand multiplication which motivates the present theory.Thus a rough attempt to formalize our belief is embodied in the following statement: Given any algorithm for multiplying arbitrary decimal integers, and an algorithm for adding them, the number of steps required, on the average, to apply the first algorithm to a given pair of integers should substantially exceed the number of steps required by the second.Since the ordinary addition algorithm requires a number of steps proportional to the number of digits in the addends, the statement can be rephrased as follows:1.1.No matter what algorithm is used, the number of steps, on the average,