Should J really be putting us through such hoops, you ask?
But is it J that's the problem, or the Collatz Conjecture?
I mean, you've stated that you d not understand the vector approach, and
then gone from there on to other issues. But is it really fair to the
language to ignore its strengths because you are having difficulty
understanding a problem which all mathematicians have problems with? Does
the Collatz Conjecture actually have a practical use?
I'm not sure it does - I suspect the primary beauty of the problem is in
understanding it.
So let's take a quick look at that vector approach:
collatzv=: 3 : '<. (2|y)} 0 1 + 0.5 3 */y'
This performs just a single step: it either multiplies by 3 or it divides
by 2, depending on if the number is odd or even. It also works on a bunch
of numbers.
Let's say that y is 1 2 3 4 5 6 7 8 9
Then 0.5 3 */ y is
0.5 1 1.5 2 2.5 3 3.5 4 4.5
3 6 9 12 15 18 21 24 27
In other words the first row is half of y and the second row is 3 times y.
We then add 1 to the second row with 0 1 + which gives us:
0.5 1 1.5 2 2.5 3 3.5 4 4.5
4 7 10 13 16 19 22 25 28
And I just know that some people will be thinking "that's inefficient" but
it's *not*. And that's sort of the point. I am not going to go into the
hardware design issues here, but the entire field of computer science has
been infested with false concepts of efficiency. They are not always false,
but the concepts are based on assumptions which are quite often irrelevant.
Anyways, we then use 2|y to find out which numbers are odd and which are
even:
2|1 2 3 4 5 6 7 8 9
1 0 1 0 1 0 1 0 1
And we use that list to pick values from either the first or second row of
that matrix we calculated:
1 0 1 0 1 0 1 0 1} 0 1 + 0.5 3 */1+i.9
4 1 10 2 16 3 22 4 28
Now... on to cnv...
cnv=: 3 : 0
f=. 2^m=. i. <.@(2&^.)&.<: y
m=. >:m
C=. 0 ,~ m f} y{._1
j=.i=. 3 + i.@<.&.-: y-2
while. #i do.
j=. collatzv j
b=. 0<(j<.y){C
p=. , f */ b#i
q=. , m +/ (b#j){C
m=. >:m
i=. (-.b)#i
j=. (-.b)#j
b=. y>p
C=. (b#q) (b#p)}C
end.
}:C
)
That's a fair bit of code, what's it doing?
Well... let's take a look at that first line:
f=. 2^m=. i. <.@(2&^.)&.<: y
Since it uses i. we know it's going to build a
list and we should probably expect that y needs to
be an integer.
The big verb to the left of i. is, in english "floor under log 2 under
decrement" -- in other words "how many bits do we need to store y"
(actually: how many bits do we need to store a value one less than y).
So that means m is bit numbers and f is bit significance. If y is 9, then m
is 0 1 2 3 and f is 1 2 4 8
Next line we make m be 1 2 3 4
C is then made to be a 10 element vector. The positions with power-of-two
indices, the last value and any other positions (except the first) are 0.
For our example, that makes it:
_1 1 2 0 3 0 0 0 4 0
Next we make i and j be odd numbers greater than 1 and smaller than y-1 --
in our case they are 3 5 7
Next we use our collatzv to find the successors of j, which will be 10 16 22
All pretty mysterious, right?
But hopefully, this next line should make it clear:
b=. 0<(j<.y){C
C is a cache of the collatz lengths for each of its indices. That's why the
first value is _1 - there's no collatz length for a starting point of 0, so
that's just a garbage value. And that's why the power of two indices get
counting integers - we just halve powers of two until they become 1.
In other words: the "vector approach" is exactly the caching system you
have been looking for.
Is this enough so that you can read the code? If you like, we could go over
the rest of it...
Thanks,
--
Raul
On Wed, Aug 6, 2014 at 7:13 PM, Alex Giannakopoulos <[email protected]
> wrote:
> My apologies if I've missed it, but has anyone posted how long the vector
> approach takes to find the longest chain under 1000000 and the highest
> number in that chain?
> The answers are - longest chain: 837799 ; steps: 524 ; biggest number in
> chain: 2974984576
>
> I am also not completely clear on the verdict re M.
> It's a very simple functionality usually, for any monadic function, already
> computed results are stored in a lookup table, which is checked on every
> invocation to avoid recomputation. Even if there is something wrong with
> the builtin adverb M. (is there?) it shouldn't be too difficult to write
> another one from scratch.
>
> In any case, it should be doable, and usable for anyone who does not want
> to resort to the vector approach, which I still find somewhat inscrutable.
> I've even done the recursive one in Javascript (as well as C++, < 1") for
> crying out loud, should J really be putting us through such hoops?
>
>
>
>
> On 6 August 2014 06:51, mvillarino <[email protected]> wrote:
>
> > > Roger's version wins by a long shot (2.2 vs 2.1 vs 1.7). It invokes
> > fewer
> > > verbs. The interesting thing is that it's collatzv that runs faster
> not
> > > the code that follows - meaning that the interpreter is smart enough to
> > use
> > > integer arithmetic before we even get to *<.* ?!?
> >
> > In Roger's definition of cnv, it uses an auxiliary with a helpful
> > name: "m", containing a <. which, if my tests are right, is unneeded
> > because of the same reason.
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> >
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
