Initial population.

1 files changed, 116 insertions, 0 deletions

diff --git a/src/hyper/pages/BBTREE.ht b/src/hyper/pages/BBTREE.ht
new file mode 100644
index 00000000..e1e41d68
--- /dev/null
+++ b/src/hyper/pages/BBTREE.ht
@@ -0,0 +1,116 @@
+% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
+% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
+\newcommand{\BalancedBinaryTreeXmpTitle}{BalancedBinaryTree}
+\newcommand{\BalancedBinaryTreeXmpNumber}{9.2}
+%
+% =====================================================================
+\begin{page}{BalancedBinaryTreeXmpPage}{9.2 BalancedBinaryTree}
+% =====================================================================
+\beginscroll
+\spadtype{BalancedBinaryTrees(S)} is the domain
+of balanced binary trees with elements of type \spad{S} at the nodes.
+%-% \HDindex{tree!balanced binary}{BalancedBinaryTreeXmpPage}{9.2}{BalancedBinaryTree}
+A binary tree is either \spadfun{empty} or else
+%-% \HDindex{balanced binary tree}{BalancedBinaryTreeXmpPage}{9.2}{BalancedBinaryTree}
+consists of a \spadfun{node} having a \spadfun{value}
+and two branches, each branch a binary tree.
+A balanced binary tree is one that is balanced with respect its leaves.
+One with \texht{$2^k$}{2**k} leaves is
+perfectly ``balanced'': the tree has minimum depth, and
+the \spadfun{left} and \spadfun{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
+%-% \HDindex{Chinese Remainder Algorithm}{BalancedBinaryTreeXmpPage}{9.2}{BalancedBinaryTree}
+using balanced binary trees was first proposed by David Y. Y.
+%-% \HDindex{Yun, David Y. Y.}{BalancedBinaryTreeXmpPage}{9.2}{BalancedBinaryTree}
+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
+\Language{}.
+
+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 \texht{$12^2
+= 144$}{12 ** 2 = 144}.
+
+\xtc{
+A list of moduli.
+}{
+\spadpaste{lm := [3,5,7,11]\bound{lm}}
+}
+\xtc{
+The expression \spad{modTree(n, lm)}
+creates a balanced binary tree with leaf values
+\spad{n mod m} for each modulus \spad{m} in \spad{lm}.
+}{
+\spadpaste{modTree(12,lm)\free{lm}}
+}
+\xtc{
+Operation \spad{modTree} does this using
+operations on balanced binary trees.
+We trace its steps.
+Create a balanced binary tree \spad{t} of zeros with four leaves.
+}{
+\spadpaste{t := balancedBinaryTree(\#lm, 0)\bound{t}\free{lm}}
+}
+\xtc{
+The leaves of the tree are set to the individual moduli.
+}{
+\spadpaste{setleaves!(t,lm)\bound{t1}\free{t}}
+}
+\xtc{
+Use \spadfunX{mapUp} to do
+a bottom-up traversal of \spad{t}, setting each interior node
+to the product of the values at the nodes of its children.
+}{
+\spadpaste{mapUp!(t,_*)\bound{t2}\free{t1}}
+}
+\xtc{
+The value at the node of every subtree is the product of the moduli
+of the leaves of the subtree.
+}{
+\spadpaste{t \bound{t3}\free{t2}}
+}
+\xtc{
+Operation \spadfunX{mapDown}\spad{(t,a,fn)} replaces the value
+\spad{v} at each node of \spad{t} by \spad{fn(a,v)}.
+}{
+\spadpaste{mapDown!(t,12,_rem)\bound{t4}\free{t3}}
+}
+\xtc{
+The operation \spadfun{leaves} returns the leaves of the resulting
+tree.
+In this case, it returns the list of \spad{12 mod m} for each
+modulus \spad{m}.
+}{
+\spadpaste{leaves \%\bound{t5}\free{t4}}
+}
+\xtc{
+Compute the square of the images of \spad{12} modulo each \spad{m}.
+}{
+\spadpaste{squares := [x**2 rem m for x in \% for m in lm]\bound{t6}\free{t5}}
+}
+\xtc{
+Call the Chinese Remainder Algorithm to get the
+answer for \texht{$12^2$}{12**2}.
+}{
+\spadpaste{chineseRemainder(\%,lm)\free{t6}}
+}
+\endscroll
+\autobuttons
+\end{page}
+%