Justin Paston-Cooper asked:
> The problem is to find the smallest positive number
> divisible by all of the numbers from 1 to 20.
I wrote:
> the "direct solution" is to just ask for the least
> common multiple (LCM):
> *./ >: i. 20
> 232792560
Justin wrote:
> How about some smarter solutions?
Of course, *. is the obvious solution once you know about it, but what if
you didn't? (After all, it's rarely used outside of boolean lists).
Well, I'll leave mathematical alternatives to the mathematicians, and stick
with my original brute force idea of LCM. But I'll pretend we don't have *.
built in to the language, and we'd need to find another way to express it
[1]. How about:
>./ &.(_&q:) >: i. 20x
232792560
Now I can't say whether LCM is an elegant mathematical approach, but I can
say (or opine) that J allowed us to express LCM elegantly! Compare
>./&.(_&q:) to the formulas given on the Wikipedia page [2]. By the way,
GCD (+.) is analogously <./&.(_&q:) (<. in place of >.).
> When running
> $:@>:^:(+./@:(0&~:@((1 + i. 20)&|))) 1
> with 20, I get a stack error. Could anyone
> tell me how to get around this?
In J, the rule of thumb is "think big". Don't sweat the details; let the
interpreter handle them. In fact, the interpreter does not suffer
micro-management gladly, and can get recalcitrant [3].
Here, you're dealing with a scalar input, testing it, and if the test fails,
incrementing the scalar and recursing. In a "normal" (scalar) programming
language, like C, that's an appropriate algorithm. Well, you might use
iteration instead of recursion, but you can't avoid dealing in scalars. But
in J, it's best to deal in large arrays.
So, the first thing to do with your verb is to increase its scope. Have it
work on lists, or higher-ranked arrays, instead of scalars. As a first
step, let's just try it against a vector input & see what happens:
$:@>:^:(+./@:(0&~:@((1 + i. 20)&|))) 1 2 3
|length error
| $:@>:^:(+./@:(0&~:@((1+i.20)&|)))1 2 3
Hmm. Looking over the code, most of the primitive verbs are actually scalar
(rank 0), so why would it balk at being applied to an array...... ah! We
have (1+i.20)&| and | is scalar too! (You can test it with | b.0 ).
That means that the left- and right-hand arguments to it must have the same
shape. So either we make the input a vector of length 20 (an artificial
constraint and still thinking too small - we want the input as big as J can
handle), or we somehow "scale up" | .
How can we do that? Well, you remember your multiplication tables from
grammar school?
1 2 3 */ i. 10
0 1 2 3 4 5 6 7 8 9
0 2 4 6 8 10 12 14 16 18
0 3 6 9 12 15 18 21 24 27
How about we use a modulus table here?
1 2 3 |/ i. 10
0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0 1
0 1 2 0 1 2 0 1 2 0
(It turns out we're lucky | is rank 0 (like * is), because that's when /
works best for vector inputs like i.20 . With a different verb, we might've
needed to use " explicitly.)
Of course, now that we have a mod table instead of a mod vector, we may
need to re-adjust other parts of the verb (such as how we advanced the input
before recursing). That's left an exercise for the reader, but I'll note
that you still want the result of the test (the parenthesized expression) to
be a single boolean, and remind you about the . operator (as in +./ . ~:
). See also [3].
-Dan
[1] For more in the vein of rewriting primitives, see:
http://www.jsoftware.com/jwiki/PrimitivePrimitives
which is a pet project of mine, though there are many contributors.
[2] LCM and GCD formulas on Wikipedia:
http://en.wikipedia.org/wiki/Least_common_multiple#Formulas
[3] In this case, the stack error is because J does not optimize tail
calls. That is, the stack limit is imposed by C, J's host language. In
fact, the standard test of J's stack limit on a new platform is:
$:@:>: :: ] 0
6666
so writing $:@:>: ... 1 should really make you itch.
In fact, for this reason, writing $: generally makes me itch, so I often
try to re-express a recursive $:^:t algorithm as an iterative ^:t^:_
algorithm. That's not always possible, but it often is. In this case, the
fundamental issue with the algorithm is that it's scalar, but nevertheless
we could've made some progress in it by applying this transformation:
>:^:(+./@:(0&~:@((1 + i. 10)&|)))^:_: 1
2520
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
