Like Eugene, I read 'The Book of Numbers' because of Ken's lab, so enjoyed
revisiting it in editing this piece by Eugene.
Trying to understand what he did, and just what 'nimber' multiplication is I
found that we can write some simple functions to generate the multiplication
table which are quite different in approach from those Ken used and which
Mike Day used for his code converting the Maple code.
A note might be appropriate, and it might be a good place to explain some of
the multiple base capabilities of J. However I think it would be better to
make some reference to a suitable more expanded comment on the JWiki -
perhaps as an Essay though I think Roger has edited all those.
What would you recommend?
Those interested about the detail might like to read on.
Nimber products for the powers of 2 can be found using the rules specified
by Guy and Conway, but differ depending on how the power of 2 is formed. One
approach is to consider all the powers of two and their nimber products. I
found it very difficult to get these right working by hand but it is much
simpler than direct construction of the general table. It took a lot of
trial and error before I got them all right mainly because you have to be
very careful distinguishing between ordinary and nimber multiplication.
Then express all elements of a product in terms of the binary components,
and form their nimber sum using the function in Eugene's code. This works
because in binary all coefficients are zero or one, and for nimber products
1 is the identity.
The table pt and the function p provide the nimber products for binary terms
required for elements from i.16.
Tables of nimber products exist for all Fermat powers, so tables, of shape 2
2 ;4 4 ;16 16; 256 256 etc can be formed. For each table the previous table
is required in its construction.
The multiple base numbers available in J provide an alternative simple way
of constructing the powers. Representing each number by a mixed base with
elements 2,2,4,16,256,...provides an alternative method of finding the
nimber product of any pair of numbers. The very much slower function pf
provides these products for nimbers from the set i.256.
There are several ways of simplifying these functions, but a general form is
likely only to be used for one further step as the next table is of shape
65536 65536. This led to the decision to have two simple functions for the
cases with base 16 and 256, and combine them in a manner which reduces the
number of computations.
The following is a script:
NB. Nim sums and multiplication for values up to 255
s =: [: #. [: ~:/ (#: @ ,)
NB. A slow function using Fermat powers
pf =: 4 : 0
xf =. |. "1 ]16 4 2 2 #: x NB. convert to Fermat powers
yf =. |. "1 ]16 4 2 2 #: y
xy =. xf p/ "1 1/ yf NB. form products of Fermat powers
xyp =. xy (pp"0) "2 _ pmf 4
(s@,)"2 xyp
)
pmf =: 3 : 0
v =. i.y
a =. 1,}: 2^2^v
m =. a */ a
(1,3r2*}.a) (<"1 v,.v)}m
)
NB. the rules require the products of various binary
NB. numbers and nimber products for lower order terms
NB. I began with calculating pt, then moving to pt8
pt8 =: noun define
1 2 4 8 16 32 64 128
2 3 8 12 32 48 128 192
4 8 6 11 64 128 96 176
8 12 11 13 128 192 176 208
16 32 64 128 24 44 75 141
32 48 128 192 44 52 141 198
64 128 96 176 75 141 103 185
128 192 176 208 141 198 185 222
)
pt8 =: ". > < ;._2 pt8
pt =: 4 4 {. pt8
p =: 4 : 0"0 0 NB. Nimber products for i.16
s , pt *(4{. |. #: x) * / 4 {. |. #:y
)
pp =: 4 : 0 "0 0 NB. Nimber products for i.256
s , pt8 *(8{. |. #: x) * / 8 {. |. #:y
)
NB. A function to calculate the terms in pt and pt8 would
NB. welcome. Parts of pt8 are not used in pf for i.256 so
NB. this assisted in checking the higher power terms.
Fraser
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
