Newsgroups: comp.lang.apl
Path: utzoo!utgpu!news-server.csri.toronto.edu!torsqnt!jtsv16!blister!itcyyz!yrloc!hui
From: hui@yrloc.ipsa.reuter.COM (Roger Hui)
Subject: Re: ACORN, and other niceties
Message-ID: <1991Jun22.082236.24661@yrloc.ipsa.reuter.COM>
Reply-To: hui@yrloc.ipsa.reuter.COM (Roger Hui)
Organization: Iverson Software Inc.
References: <1991Jun11.200234.6130@aplcen.apl.jhu.edu> <1991Jun13.044828.29504@yrloc.ipsa.reuter.COM> <4481@borg.cs.unc.edu>
Date: Sat, 22 Jun 91 08:22:36 GMT

Reply to article <4481@borg.cs.unc.edu> by prins@cs.unc.edu (Jan Prins).

Thank you for your comments.  In my original post, the first step was:
 
   Propagate x and y to m*n processors     O log m>.n
 
This (obviously) assumes that there are m*n processors, without the 
lamentable parameter P.  Assuming processors as an unbounded resource 
is analogous to the common practice of assuming space as an unbounded 
resource.  I should have made this assumption more explicit.
 
Processors as an unbounded resource is not unreasonable.
(It wasn't long ago that P=64K was a parameter for space ...)
With this embarrassment of riches, how fast can one compute?
The answer for  x epsilon y  is, O log m>.n time, optimal time,
using the profligate outer product algorithm.
 
Daniel Hillis, speculating on a billion processor machine built with
current technology (Scientific American, June 1987), wrote:
 
  There are technical problems inherent in building such a
  computational engine, but they are soluble.  The real
  problems are those of the imagination:  conceiving how
  such power would be used.  ...
 
x epsilon y  is a complex and recurring theme with many nuances.
I do not pretend that a single sentence, even if an APL sentence :-),
adequately covers the subject.  Consider the outer product algorithm
a catalyst for the imagination.

-----------------------------------------------------------------
Roger Hui
Iverson Software Inc., 33 Major Street, Toronto, Ontario  M5S 2K9
(416) 925 6096