An Exchange on Primes
Vector 9:4, page 130
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 130
USENET is a world-wide network connecting approximately 37,000 machines in academia, government, business, and other organizations (see reference [1]). It has a "news" subsystem of discussion groups, including the APL group "comp.lang.apl". Over the last 20 months, the group averaged about 2.3 messages per day. The following exchange took place recently:
----------------------------------------
From: Johann Mitloehner
Subject: explicit <-> tacit, space/time usage on prime numbers
Date: Fri, 30 Oct 1992 10:55:15 GMT
Organization: Wirtschaftsuniversitaet Wien
Here are some experiments (by T. Kolarik and myself) with the well-known primes-idiom on several machines, comparing tacit and explicit definition of the verb:
On an HP 9000/720 (HP-UX):
eprimes =. '(i.y.)#~2=+/0=|/~i.y.':'' NB. explicit def
tprimes =. (=&2 @ (+/ @ (=&0 @ |/~ @ i.))) # i. NB. tacit def
time =. 6!:2
space =. 7!:2
ts =. (time, space)
ts 'tprimes 100'
2.71 2528
ts 'eprimes 100'
0.15 464
[Similar timings on a Mac Quadra and Mac IIx.]
Result: explicit definition is much faster.
I have done a similar thing on a Mac Classic with J 5.1a; interestingly, tacit was slightly faster (the difference being very small; I did no space measure).
But tacitly defined verbs are supposed to be (much?) faster, aren’t they? Or is this just a bad example? (Or is our tacit version so bad):
----------------------------------------
From: Sam Sirlin
Subject: Re: explicit <-> tacit, space/time usage on prime numbers
Organization: Jet Propulsion Laboratory, Pasadena, CA
Date: Wed, 4 Nov 1992 19:33:52 GMT
[Quotes from Mitloehner's message deleted.]
Using J6 on a sun sparcstation 1:
ts 'tprimes 100'
4.53315 24
ts 'eprimes 100'
0.099996 24
ts 'eprimes 100'
0.116662 24
teprimes=. '(i.y.)#~2=+/0=|/~i.y.' : 11 NB. tacitize eprimes
ts 'teprimes 100'
0.116662 24
So not all tacit definitions are equal.
----------------------------------------
From: McDonnell, Eugene E.
Date: Sat, 7 Nov 92 22:00:03 UT
s=.'(i.y.)#~2=+/0=|/~i.y.'
eprimes =. s :'' NB. explicit def
tprimes =. (=&2 @ (+/ @ (=&0 @ |/~ @ i.))) # i. NB. tacit def
cprimes=. s : 20 NB. :20 replaces obsolescent :11
lr=.5!:5 [linear representation]
lr <'cprimes'
i.@] #~ 2&=@(+/@(0&=@(|/~@(i.@]))))
time =. 6!:2
time 'eprimes 100'
0.116667
time 'tprimes 100'
3.53333
time 'cprimes 100'
0.1
Herr Mitlöhner is correct: tprimes is not equivalent to eprimes.
Using the :20 compiler on s gives a tacit form cprimes whose logic is that of eprimes, and which is more efficient than the explicit form, by a small amount.
These measurements were made on a Mac Quadra 700.
----------------------------------------
From: Roger Hui
Subject: Re: explicit <-> tacit, space/time usage on prime numbers
Organization: Iverson Software Inc.
Date: Sat, 7 Nov 92 23:38:13 GMT
[Quotes from Mitloehner's message deleted.]
In July 1990, at the APL90 Conference in Copenhagen, Eugene McDonnell presented timings indicating that a tacitly defined nub was faster than an explicitly defined nub, and was as fast as the primitive ~..
I was in the audience and was surprised by this result. Tacit defns arise from the use of adverbs and conjunctions, function assignment, and forks; that they happen to be faster is an unexpected benefit.
The slower times for tprimes obtained above can be accounted for by the difference between =&0@|/ vs. =&0@(|/). I applied the tacit translator to the explicit defn, and obtained the following time/space results (J6 on a PC486/33):
ts 'tprimes 100'
2.86 24692
ts 'eprimes 100'
0.05 53420
f0 =. '(i.y.)#~2=+/0=|/~i.y.': 11
ts 'f0 100'
0.05 50312
lr =. 5!:5
lr <'f0'
i.@] #~ 2&=@(+/@(0&=@(|/~@(i.@]))))
This shows that tacit defn is at least no slower than explicit defn. The following table shows that it is in fact faster. All times are obtained using 100 time 'f n' on J6 PC486/33.
200 100 10 5 1
tprimes 11.0334 2.8456 0.0341 0.0109 0.0033
eprimes 0.2230 0.0582 0.0049 0.0044 0.0044
f0 0.2213 0.0565 0.0032 0.0027 0.0027
f1 0.2208 0.0566 0.0033 0.0027 0.0026
f2 0.2208 0.0566 0.0033 0.0027 0.0027
f3 0.0193 0.0138 0.0038 0.0033 0.0038
f4 0.0143 0.0088 0.0017 0.0016 0.0016
f0 is faster than eprime by a fixed amount, 0.0017. This is consistent with the explanation of why tacit is faster than explicit: a tacit defn is not reparsed on execution, and 0.0017 is the time it takes to parse eprimes. The relative advantage of tacit over explicit is thus greatest for small vectors, when parsing time dominates, and diminishes as vector size increases. This fact is of interest to compiler writers.
f1 is an attempt to see how much better or worse a "hand-written" tacit defn may be. f0=.i.@] #~ 2&=@(+/@(0&=@(|/~@(i.@])))), the defn produced by the translator, is periphrastic (from the Greek "periphrasis": a round about expression. Ed). It is easy to see that the two uses of @] are unnecessary, and the use of passive can be eliminated by rearranging the tines of the fork. As well, I tend to shy away from deeply right-nested compositions. Putting it all together:
The timings in the table indicate that f1 is slightly faster than f0. Not too surprising, as f1 is only slightly different from f0.
As indicated at the start, speed is not the main point of tacit defn. Some of the advantages of tacit defn were outlined in a msg two weeks ago:
0) The tacit form encourages the use of components, primitive and user-defined. Use of components is one of the few effective ways of dealing with complexity.
1) The tacit form focuses on how components are combined, i.e. it focuses on the interface between components, where errors tend to occur.
2) Tacit expressions are algebraic, i.e. they are amenable to proof and other formal manipulations.
3) Tacit expressions are constructed using operators (adverbs and conjunctions), ideas debugged in mathematics over hundreds of years.
Even for something as small as this primes problem, it is possible to see how these benefits may be applicable. f1 can be redefined to use a sub-function, of interest in its own right:
f2 is slightly clearer than the others, in bringing into sharper relief the structure of the computation. It is about as fast as the others (see table).
I’d previously written a recursive version of primes which avoids generating the n^2 table:
t=.i. 0 0
t=.t,'$.=.1+30<y.'
t=.t,'y.(>: # ])2 3 5 7 11 13 17 19 23 29'
t=.t,'p,(*./0~:p|/s)#s=.k+i.>:y.-k=.{:p=.f3 <.%:y.'
f3 =. t :''
A hand-translated tacit version of same:
basis =. (>: # ])&2 3 5 7 11 13 17 19 23 29
sieve =. *./@(0&~:)@(|/)
suffix =. {:@[ ([ + i.@-.@-) ]
extend =. [ , [ (sieve # ]) suffix
f4 =. ($:@<.@%: extend ])`basis @. (30&>)
The time and space complexity of f3 and f4 are of a lesser order than the others, so that the advantage shown in the table increases with argument size:
100 time 'f0 500' 100 time 'f0 1000'
1.3583 ws full
100 time 'f3 500' 100 time 'f3 1000'
0.038 0.09
100 time 'f4 500' 100 time 'f4 1000'
0.0335 0.0829
Finally, 2) speaks of tacit expressions as being more amenable to proof and other formal manipulations. Optimization is a class of formal manipulation, and in the future the implementation may exploit formal properties of tacit defns to effect faster execution. I described some possible approaches at the Minnowbrook ’92 conference in mid September.
Tacit definition is discussed in an APL91 paper [2]. Briefly, an explicit definition is one which explicitly mentions its argument, as in sum=.'+/y.':''; a tacit definition is one which does not, as in sum=.+/ . The tacit translator mentioned in the messages is also discussed in [2].
The "well-known primes idiom" in the original message computes the n by n residue table of the integers from 0 to n-1, sums a mask marking the divisors, and selects the integers with exactly two divisors. In contrast, the recursive algorithm in f3 and f4 computes a vector p of the primes up to the square root of n, then computes the (#p) by n-k residue table of p against the integers from k to n, where k is the last element of p, and returns p suffixed by integers from k to n having no divisors in p. The following dialog illustrates the internal workings of the algorithm:
<.%: 40 f4 6 basis 6
6 2 3 5 2 3 5
(f4 6) suffix 40
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
(f4 6) sieve (f4 6) suffix 40
0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0
1 0 0 0
(f4 6) (sieve # ]) (f4 6) suffix 40
7 11 13 17 19 23 29 31 37
(f4 6) extend 40
2 3 5 7 11 13 17 19 23 29 31 37
f4 40
2 3 5 7 11 13 17 19 23 29 31 37
References¶
[1] Cerf, V.G. Networks, Scientific American — Special Issue on Communications, Computers, and Networks, 1991 9.
[2] Hui, R.K.W., K.E. Iverson, and E.E. McDonnell, Tacit Definition, APL91 Conference Proceedings, 1991 8.