Thanks for the explanation. I don't really see what you're hinting at with using arrays and the dot operator. Could you give me a further hint?
On 7 January 2011 14:20, Dan Bron <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
