On 3/22/07, Geoff Canyon <[EMAIL PROTECTED]> wrote:
The above code always checks all six values. Here it doesn't matter
because the problem is solved in a few seconds, but I want to learn:
is there a way to keep the tacit structure and at the same time short
circuit the process?
Generally, when people talk about short-circuiting function
evaluation, they are concerned about time (or perhaps some
other resource). The thought, apparently, is that short circuiting
will result in faster execution.
However, in many cases, this idea is false -- it ignores important
aspects of modern CPU design (where branching results in
scheduling stalls, testing takes time, cache prediction goes
awry, etc.)
Fundamentally, modern systems introduce parallelism and use
that to emulate serial processing, but thinking about things
serially is not always a clear win.
In J, this is further exaggerated because the language itself
is array oriented. But the above issues are relevant in any
language and are likely to become more relevant as time
progresses.
In this particular algorithm, probably the most expensive
operation is converting numbers to a sequence of digits.
As that's relatively cheap I doubt "short circuiting" would
buy you much time. That said, here's an approach:
First, we are concerned with both the numbers and
their digits. Since I expect that determining digits is
expensive I'll try to keep a box of digits for each number:
digits=: /:~@":&.>
both=: digits ; ]
Second, I wish to eliminate numbers (and their digits)
where a multiple of the number has different digits
keep=: <@(digits@([ * 1 {:: ]) = 0 {:: ]) #&.> ]
Next, I want to perform this operation for a sequence of
multipliers, then discover the surviving numbers:
F=: 1 {:: [: > [: keep&.>/ (]&.>2 3 4 5 6) , <@both
Next, since I am concerned about time more than
simplicity, I want to amortize my costs for some of these
functions over a large block of numbers. In this case,
performing this step manually is viable:
F i. 1e5
0
F 1e5+i.1e5
142857
However, more generally, I'd probably want to automate
the iteration over blocks.
To make this a somewhat more interesting exercise, I
should also use a smaller block size. And, since I have
reduced this to an exercise in serial processing,
I feel it's time to break out an explicit definition:
findNext=: (1e4 $: ]) :(4 :0)
'ndx start'=.(0,x)#:y
try=.(x*ndx)+start}.i.x
while.0=#r=.F try do.
try=.(x*ndx=.ndx+1)+i.x
end.
{.r
)
If I thought it was likely that F would return multiple values and
I was concerned about the time it took to evaluate F for a single
block, I might complicate things further by caching my results
between calls to findNext.
Alternatively, I might decide that my focus on getting a single
result was more trouble than it's worth (after all, I'm exploring
here -- otherwise I would have a better idea of my array bounds)
and change {.r to r
Have I saved time here? Not really -- the underlying computations
are too simple for my "save them in boxes" approach to be very
effective. But maybe this approach is of interest.
P.S. here's another way of looking at the problem -- it's somewhat
slower but illustrates a different way of thinking about "comparing
them all to see if they are equal":
I. *./ 2 =/\ digits"1 (>:i.6)*/i.2e5
Note that this takes about twice as long as findNext 1 -- that's
mostly because it's going all the way to 2e5. But I wanted to
illustrate the *./ 2 =/\ concept.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
