Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Finding Computation Trees From a Basis to a Goal

IP.com Disclosure Number: IPCOM000078660D
Original Publication Date: 1973-Feb-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 48K

Publishing Venue

IBM

Related People

Shamir, E: AUTHOR

Abstract

The flow chart describes a method for finding whether a given goal is computable from a given basis of operands and binary operators. In general applications, the algorithm takes less storage and runs faster than previously known methods.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Finding Computation Trees From a Basis to a Goal

The flow chart describes a method for finding whether a given goal is computable from a given basis of operands and binary operators. In general applications, the algorithm takes less storage and runs faster than previously known methods.

A general "background routine" is set forth which, given a basis B of operands, a family F of binary operators and a goal value Z, finds whether Z is computable from the base B by successively applying the operators in F. To do this, the routine searches for a binary computation tree with root Z and leaves in B, where passage from two son nodes to their father node is done by an operation in F.

If successful, the routine outputs all triplets where (f, Z(1), Z(2)) = Z is the last step of a successful computation (the top of the tree). If desired, the routine can be extended to output a whole (or all) computation tree(s) by setting Z(1),Z(2) as goals, finding the tops of their trees, etc. The routine becomes a concrete program when the operations F and the basis B are prescribed (two examples of this kind are discussed below).

The routine is illustrated in the flow chart. It has two parameters, K and L. K is the number of program variables, each variable is a pair (X(k), Y(k)), X(k) ranges over the collection D of possible intermediate computation results, Y(k) is a binary digit (a test bit). L is the number of storage bits needed (or given) for the X components of the program variables. For given values of K and L, the routine will find if there is a computation tree which requires at most 2/cK/ operation nodes (c can be taken as 1/Log 9/7), and whose intermediate computation results require L bits to store. The collection D is linearly ordered, adding an extra first element 0 and last element 'Last'. The function Next (X) gives the next element in this order, Absolute value of X is the number of bits needed to Store X, with 0 = 1 and absolute value of Last = 1.

The routine applies to any collection of operations, not necessarily binary. This means a search is conducted for general trees instead of binary. Only notational change is needed for this case. The main features of the routine are the minimal storage requirement ((L+1)K) and its wide range of applications. In particular, it can handle computations whose standard implementation would require a stack (a pushdown). Using the routine, there is no stack but a relatively small increase of the rest of the storage.

The advantage of the present routine, aside from its general purpose nature, is in revealing what features of a special computation process (specializing B and
F) will...