The Basic Search Algorithm

The Search algorithm is simply a depth-first search on the tree described in the previous section. Note that we do not allow operations involving specific integers; only letters involving unknown quantities. The naive form of the basic algorithm is easily stated:

Input: m variables, a budget consisting of M multiplications, and A adds, and n goal expressions to be determined.

Output: A way of computing the goal expressions without exceeding the budgeted number of operations or a statement that no such method exists.

Method: Initialize the first m levels to the input variables.
Initialize level to m + 1.

 
 Search()

For input1 = 1 to level - 1:

   For input2 = 1 to level - 1:

	For each operation type left in the budget:

		Apply operation to the expressions at input1 and input2.

		 Remove the operation from the budget.

		 .

		 If the new expression is a goal expression not yet found,

		 	mark the goal expression as found.

		 If all the goals are found, return the solution.


		 If ,  Search().

		 Unmark the goal expression found, if any.

		 Restore operation to the budget.

	End For.

   End For.

End For.

In principle, questions like 'is there a method of finding the product of two complex numbers involving three real multiplications and five real adds?' can be answered by exhaustive search. This approach is naive in general because there are so many possible algorithms with these constraints. Since the two input expressions can be taken from any previously computed expression, the number of input combinations is (A + M + m - 1)!² / (m - 1)!². There are

ways to place the multiplications in the set of steps. Since the `add' operations can be any of addition, subtraction, or reverse subtraction, there are 3^A possible sets of add operations for any specified placing of multiplications. The total number of elements in the search space by the naïve method is

For the complex product with 4 inputs and a budget of 3 multiplications and 5 adds, this value is approximately

A massively parallel collection of 8000 processors, each checking one million nodes per second, would take more than 2 years in the worst case that there is only one such algorithm and that it is the last one checked. The existence of multiple algorithms in the search space and termination of the search when the first is found might reduce this time by an order of magnitude, but it would still not be the sort of problem casually attempted with 1992 technology!

To make the problem more tractable, we began the accumulation of `pruning rules' for eliminating subtrees in the search without any danger of missing a solution. These pruning rules are conservative because they still allow the resulting tree to be called an exhaustive search. Later we consider pruning rules that seem to greatly assist in finding clever methods that trade multiplications for adds, but cannot be used to prove the nonexistence of a method with a given operation budget.

Next: Conservative Pruning Rules Up: Massively Parallel Searching Previous: Modeling as a