1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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}
%
|
