On Thu, 15 Feb 1996, Don Woods wrote:

Can we go again? That is, can we go from Q[2n] to Q[4n]?
I think not. Shamir's method requires that of the S and T
trees, at least the T tree really be there. We have to
traverse it many times and in all kinds of orders. Being
there virtually is not enough.

But wait a sec. Can't we go from Q[2n] to Q[3n]? We still
have T sitting there. As we generate each element of Q[2n],
we could use it to generate Q[2n] x T, couldn't we? Or do
you also need S to "really be there", too? (I didn't go back
over your description to try to figure that out; I'm just
basing my suggestion on the quoted paragraph.)

As I said earlier, this is the part of Shamir's method about which I am
most uncertain. In my description of forming products st from S and T, I
emphasized the role of T. But if I understand the method correctly, the
width of what I called an m-way merge is controlled by the size of S
(remember that S contains m elements and T contains n elements). So the
merge queue itself will also have m elements. If you try to generate
Q[2n] x T, the width of the merge (and the size of the merge queue) will
have to be as large as Q[2n], which is too large to store.

In answer to your specific question, I would say that the merge queue has
to really be there. S might or might not have to really be there,
depending on exactly how you program the interaction between S and the
merge queue. But in any case, the merge queue is as big as S.

(I would gladly accept any and all help discussing these issues with
anyone who has actually programmed the algorithm.)

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                jbryan@pstcc.cc.tn.us
Pellissippi State                            (423) 539-7127
10915 Hardin Valley Road                     (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990