BalancedBinaryTrees(S) is the domain of balanced binary trees with elements of type S at the nodes. A binary tree is either empty or else consists of a node having a value and two branches, each branch a binary tree. A balanced binary tree is one that is balanced with respect its leaves. One with leaves is perfectly ``balanced'': the tree has minimum depth, and the left and right branch of every interior node is identical in shape.
Balanced binary trees are useful in algebraic computation for so-called ``divide-and-conquer'' algorithms. Conceptually, the data for a problem is initially placed at the root of the tree. The original data is then split into two subproblems, one for each subtree. And so on. Eventually, the problem is solved at the leaves of the tree. A solution to the original problem is obtained by some mechanism that can reassemble the pieces. In fact, an implementation of the Chinese Remainder Algorithm using balanced binary trees was first proposed by David Y. Y. Yun at the IBM T. J. Watson Research Center in Yorktown Heights, New York, in 1978. It served as the prototype for polymorphic algorithms in Axiom.
In what follows, rather than perform a series of computations with a single expression, the expression is reduced modulo a number of integer primes, a computation is done with modular arithmetic for each prime, and the Chinese Remainder Algorithm is used to obtain the answer to the original problem. We illustrate this principle with the computation of .
A list of moduli.
The expression modTree(n, lm) creates a balanced binary tree with leaf values n mod m for each modulus m in lm.
Operation modTree does this using operations on balanced binary trees. We trace its steps. Create a balanced binary tree t of zeros with four leaves.
The leaves of the tree are set to the individual moduli.
Use mapUp! to do a bottom-up traversal of t, setting each interior node to the product of the values at the nodes of its children.
The value at the node of every subtree is the product of the moduli of the leaves of the subtree.
Operation mapDown!(t,a,fn) replaces the value v at each node of t by fn(a,v).
The operation leaves returns the leaves of the resulting tree. In this case, it returns the list of 12 mod m for each modulus m.
Compute the square of the images of 12 modulo each m.
Call the Chinese Remainder Algorithm to get the answer for .