Nim and DFns

From: John R Clark, 2nd December 2002

programming techniques competitions and puzzles

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 128

Been playing around with Dynamic Functions in Dyalog APL and the Nim arithmetic functions listed in VECTOR 19:1 pages 108 – 118. After reading the article by Eugene McDonald and the quoted letter of Professor Richard Guy, I realized the the methods for handling cases where 8 is a multiplican is far far too complicated. The nice thing about APL is you can make mathematics very simple, provided of course you think the APL way. For Nim you start by representing the values in terms of powers of 2.

For addition you actually represent the values in base 2 and then do a 2 base of the ≠/ of the values. Tis trivial. For multiplication you distribute the values of one with the other then multiply the pairs taking into account the exceptions from regular multiplication for 0, 1, 8, and the squares of 2 and 4. The functions for building these tables are:

     ∇CODE8←{                ⍝ 8 factors into 4 and 2 just regroup
[1]                          ⍝ (8 8) (8 4) or (8 2) are only possible
[2]      =/⍵:MULT¨DIST(MULT 4 4),(MULT 2 2)   ⍝ (8 8) case
[3]      4∊⍵:MULT¨DIST(MULT 4 4),2            ⍝ (8 4) case
[4]      2∊⍵:MULT¨DIST(MULT 2 2),4            ⍝ (8 2) case
[5]    }
     ∇

     ∇DIST←{
[1]      a b←⍵                              ⍝ Split multiplicans
[2]      a←((2 2 2 2⊤a)/8 4 2 1),(a=0)/0    ⍝ Convert  a
[3]      b←((2 2 2 2⊤b)/8 4 2 1),(b=0)/0    ⍝ Convert  b
[4]      ,a∘.,b                             ⍝ distribute pairs
[5]    }
     ∇

     ∇MULT←{
[1]      0∊⍵:0          ⍝ zero multiplican case
[2]      1∊⍵:×/⍵        ⍝ identity case
[3]      8∊⍵:CODE8 ⍵    ⍝ handle 8 as multiplican
[4]      =/⍵:1.5×1⊃⍵    ⍝ square of 2 or 4 case
[5]      ×/⍵            ⍝ regular multiply case
[6]    }
     ∇

     ∇NAD←{          ⍝ Nim Addition
[1]                  ⍝ 0,⍎⍕ handles single values and nested values
[2]      2⊥≠/(2 2 2 2 2 2)⊤0,⍎⍕⍵
[3]    }
     ∇

NMX←{NAD MULT¨DIST ⍵}

Addition table:

      NAD ¨(0,⍳15)∘.,0,⍳15
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
 1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14
 2  3  0  1  6  7  4  5 10 11  8  9 14 15 12 13
 3  2  1  0  7  6  5  4 11 10  9  8 15 14 13 12
 4  5  6  7  0  1  2  3 12 13 14 15  8  9 10 11
 5  4  7  6  1  0  3  2 13 12 15 14  9  8 11 10
 6  7  4  5  2  3  0  1 14 15 12 13 10 11  8  9
 7  6  5  4  3  2  1  0 15 14 13 12 11 10  9  8
 8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7
 9  8 11 10 13 12 15 14  1  0  3  2  5  4  7  6
10 11  8  9 14 15 12 13  2  3  0  1  6  7  4  5
11 10  9  8 15 14 13 12  3  2  1  0  7  6  5  4
12 13 14 15  8  9 10 11  4  5  6  7  0  1  2  3
13 12 15 14  9  8 11 10  5  4  7  6  1  0  3  2
14 15 12 13 10 11  8  9  6  7  4  5  2  3  0  1
15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0

Multiplication table:

      NMX¨(0,⍳15)∘.,0,⍳15
 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
 0  2  3  1  8 10 11  9 12 14 15 13  4  6  7  5
 0  3  1  2 12 15 13 14  4  7  5  6  8 11  9 10
 0  4  8 12  6  2 14 10 11 15  3  7 13  9  5  1
 0  5 10 15  2  7  8 13  3  6  9 12  1  4 11 14
 0  6 11 13 14  8  5  3  7  1 12 10  9 15  2  4
 0  7  9 14 10 13  3  4 15  8  6  1  5  2 12 11
 0  8 12  4 11  3  7 15 13  5  1  9  6 14 10  2
 0  9 14  7 15  6  1  8  5 12 11  2 10  3  4 13
 0 10 15  5  3  9 12  6  1 11 14  4  2  8 13  7
 0 11 13  6  7 12 10  1  9  2  4 15 14  5  3  8
 0 12  4  8 13  1  9  5  6 10  2 14 11  7 15  3
 0 13  6 11  9  4 15  2 14  3  8  5  7 10  1 12
 0 14  7  9  5 11  2 12 10  4 13  3 15  1  8  6
 0 15  5 10  1 14  4 11  2 13  7  8  3 12  6  9

Multiplication is interesting, not only is it communicative, associative, but +/ and +⌿ yields the same set of values. The 1 1⍉ has all the values as each row except the first.