Sorry, I've only just noticed this correspondence.
FWIW, Eugene posted a query on JForum, dated 21/5/2002 at 18:59 under the
heading "Nim Multiplication" . He asked for help (help - Eugene!) in
understanding
a Maple function for multiplying two Nimbers (sic).
I jumped in with an attempt at translating the Maple into J, posted to
Jforum on
22/5/2002 at 13:38 with a derived "Re:" heading. I deliberately recoded
the Maple
pretty well line for line so that the original and the result could be
compared. Others
(such as KEI!) have optimised it.
I attach my 2002 j script in case it's of any interest. It does include
Eugene's verb,
nimsum.
Mike
Ian Clark wrote:
....Clarification: it's the Nim-addition table that has 0s down the
main diagonal, not the Nim-multiplication table.
I've updated http://www.jsoftware.com/jwiki/Doc/Articles/Play191 to
include all this new material: nimsum, label and References.
Ian
On Tue, Nov 17, 2009 at 10:05 AM, Ian Clark <earthspo...@googlemail.com> wrote:
Thanks, Fraser, for tracking that down. Yes, that works fine!
Vector 19.1 is one of the few editions I don't happen to have. I'm
wondering where I got the original copy of Play191 from...
FYI, I note:
nimsum
~:/&.#:@,"0/~
NS
~:/&.#:
NS 3 6
5
nimsum 3 6
0 5
5 0
...and so on, for all the args I've tried.
So they're not so very different. I guess nimsum is more efficient for
calculating the table (a symmetric matrix with 0s down the diagonal)
because it provides 2 entries at once.
Ian
On Tue, Nov 17, 2009 at 9:11 AM, Fraser Jackson
<fraser.jack...@xtra.co.nz> wrote:
In the printed copy (Vector 19.1) it gives
nimsum =: ~:/&.#:@,"0/~ NB. EEmcD
That gives the correct results from Mike Day's function.
Fraser
----- Original Message -----
From: "Ian Clark" <earthspo...@googlemail.com>
To: "Programming forum" <programming@jsoftware.com>
Sent: Tuesday, November 17, 2009 7:27 AM
Subject: Re: [Jprogramming] APWJ Chapter 31: missing object: nimsum
I haven't explained the problem well enough.
Let me try and do so without making suppositions which conceal where
the error actually lies.
Play191 exhibits a function NS, which calculates a statistic called
the "nim sum" which helps you win at the game of Nim. NS maps into a
domain of numbers which Conway & Guy call "nimbers", with their own
idiosyncratic addition & multiplication.
Having discussed the addition of nimbers, the paper discusses their
multiplication. It offers two verbs for producing the multiplication
table of nimbers. Both are called mt. I propose to call the one by
Mike Day mtMD, which (quote) "accurately translates" a Maple program
(not shown, but viewable at the OEIS site).
Now mtMD won't work as it stands, because it uses an entity (verb?)
named nimsum, which is nowhere defined. What is nimsum?
I conjecture that nimsum is precisely the NS which is defined earlier.
So accordingly I assign: nimsum=: NS
Hey presto, mtMD now works, and it computes the following table:
mtMD 4
0 0 0 0 0
0 1 2 3 4
0 2 3 3 4
0 3 3 3 3
0 4 4 3 8
However, when you compare it with mt, they don't give the same result,
which I conjecture they should:
mt 5 NB. (index-origin strikes again!)
0 0 0 0 0
0 1 2 3 4
0 2 3 1 8
0 3 1 2 12
0 4 8 12 6
Now in view of the "correct" 15-by-15 multiplication table at the end
of the article, mt is giving the right result but mtMD isn't.
Accordingly I deduce that the assumption: nimsum <--> NS is an unsound
one. So what should the missing verb nimsum really be?
Ian
On Mon, Nov 16, 2009 at 2:31 AM, Henry Rich <henryhr...@nc.rr.com> wrote:
To me, nimsum is what you use to solve the game of Nim. It is NS as
described in the article. A Nim position with nimsum=0 is a loser for
the player with the move. You calculate it by writing the number of
stones in the piles in binary, and adding them up in binary, EXCEPT that
you discard any carries produced during the addition.
You win a Nim game by always making a move that leaves the nimsum=0. It
is easy to prove that such a move is possible iff the nimsum is not 0
already.
Henry Rich
Ian Clark wrote:
In: http://www.jsoftware.com/jwiki/Doc/Articles/Play191 (Chapter 31, J
be nimble, J be quick)
the version of mt attributed to Mike Day fails with value error: nimsum
Can anyone see what nimsum is supposed to be? It only occurs once
(outside a comment). I've tried equating it to the verb NS, the "nim
sum" derived at the start of the article, but although mt then runs,
it does not produce the same table as the previous definition of mt
(quite apart from needing to be run as (mt 4) not (mt 5) like the
previous one).
Ian Clark
Subeditor, APWJ Edn 2.
nimsum =: ~:/&.#:@,"0/~ NB. EEmcD
sort =: /:~
nimtimes =: (< @: ,) { (mt @: >./ ) NB. exploit mt
NB. verb mt is a fairly close simulation of the maple source
NB. - not necessarily good J!
NB.
mt =: verb define
iN =. i. >: N =. y.
NB. ======================================================
NB. lines 1 to 6
MT =. 0 $~ 2 # N + 1 NB. initialise MT with 0 top & left
MT =. iN 1 } MT NB. and indices in row 1
NB. MT =. iN 1 }"_1 MT NB. originally also in col 1
NB. - We can defer symmetrising and just work on diag
NB. and upper triangle
NB. ======================================================
NB. lines 7 - 11 - should be able to cut out some loops
NB. by eg recursion or scan
for_a. 2 }. iN do.
for_b. iN }.~ a do.
t1 =. i. 0
for_i. i. a do.
for_j. i. b do.
NB. ======================================================
NB. lines 12-24 are preamble to line 25
NB. references to stored AT where available
NB. or nimsum where not avail. obscures the process -
NB. This is ok on a fast m/c and/or for small N
NB. line 25 (26 is a comment) ...
NB. sort refs since using diag and upper triangle only
refs =. sort each (i,b);(a,j);(i,j)
t1 =. t1 , nimsum / refs { MT
NB. ======================================================
end. NB. line 27
end. NB. line 28
NB. ======================================================
NB. line 29 - seems to require the nub
t2 =. sort ~. t1
NB. ======================================================
NB. lines 31 - 36 - locate first element of t2
NB. not equal to its index
j =. 1 i.~ t2 ~: i. # t2
NB. ======================================================
NB. line 37 only
MT =. j (<a,b) } MT NB. don't need line 38
NB. ======================================================
end. NB. line 39
end. NB. line 40
NB. ======================================================
NB. extra line to symmetrise
MT + (iN >/ iN) * |: MT
)
NB. a line-numbered Maple source listing for comparison
maple_source =: 0 : 0
0 MT:=array(0..N,0..N); for a from 0 to N
1 do
2 MT[a,0]:=0;
3 MT[0,a]:=0;
4 MT[a,1]:=a;
5 MT[1,a]:=a;
6 od;
7 for a from 2 to N do
8 for b from a to N do
9 t1:={};
10 for i from 0 to a-1 do
11 for j from 0 to b-1 do
12 u1:=MT[i,b];
13 u2:=MT[a,j];
14 if u1<=NA and u2<=NA then
15 u12:=AT[u1,u2];
16 else
17 u12:=nimsum(u1,u2);
18 fi;
19 u3:=MT[i,j];
20 if u12<=NA and u3<=NA then
21 u4:=AT[u12,u3];
22 else
23 u4:=nimsum(u12,u3);
24 fi;
25 t1:={ op(t1), u4};
26 #t1:={ op(t1), AT[ AT[ MT[i,b], MT[a,j] ], MT[i,j] ] };
27 od;
28 od;
29 t2:=sort(convert(t1,list));
30 j:=nops(t2);
31 for i from 1 to nops(t2) do
32 if t2[i] <> i-1 then
33 j:=i-1;
34 break;
35 fi;
36 od;
37 MT[a,b]:=j;
38 MT[b,a]:=j;
39 od;
40 od;
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
