A Computer Program for Nim Multiplication

                         T. S. Ferguson


In my book, ``A Course in Game Theory'', it is shown how to compute 
nim multiplication of any two nonnegative integers.  Here is a 
subroutine written in C that will compute that product provided both 
integers are less than F_4=65536. (Here, F_n = 2^{2^n} is the nth 
Fermat 2-power.)



int prod(int x,int y) {
    int F,i,t;
    if (x>y) {t=x;x=y;y=t;}         //Now x<=y
    if (x==0) {return 0;}           //Now x>=1
    if (x==1) {return y;}           //Now x>=2
    if (y==2) {return 3;}           //Now y>=3
    if (y==3) {return (x==2)? 1:2;}  //Now y>=4
    F=4;   //Fermat 2-power
    do {
       if (y==F) {return (x<y)? x*y:3*y/2;}
       if (y<2*F) {return prod(F,x)^prod(y-F,x);}
       for (t=2*F;t<F*F;t*=2) {
          if (y==t) {
             if(x<F) {return prod(prod(x,t/F),F);}
             for (i=F;i<t;i*=2) {
                if (x==i) { return prod(prod(F,F),prod(t/F,i/F));}
                if (x<2*i) { return prod(t,i)^prod(t,x-i);}
             }
             if (x==t) {return prod(prod(F,F),prod(t/F,t/F));}
          }
          if (y<2*t) {return prod(t,x)^prod(y-t,x);}
       }
       F=F*F;
    }
    while (F<65536);
}

In the likely case that your C-compiler allocates 8 bytes for the length 
of a long int, then this same program will produce the nim product of 
any two nonnegative integers less than F_5=4,294,967,296, provided every 
`int' is replaced by a `long int', and the closing while statement is 
replaced by `while (F<4,294,967,296)'.  If fact, in the unlikely case 
that you are interested in the nim product of integers larger than F_5 
but less than F_6 ~ 1.84e19, you can replace every long int by an 
unsigned long int, but then you have to worry that when F=F_5, we 
will have  F*F=0.  This is countered by replacing, in the first `for' 
statement of the program, the inequality t<F*F, by the inequality 
t<=F*F-1.

However, if you don't want to worry about how big the numbers become, 
you can always use Mathematica, which treats integers of any length, 
limited only by the size of the computer memory and the amount of time 
you have.  You might like to use Mathematica anyway, so here is a 
program for that.  

A nice thing about programming in C or Javascript is that the nim sum 
is provided by the Xor function, ^ , namely, nimsum(a,b)=a^b.  
In Mathematica, the Xor function is  BitXor[n1,n2,...] 


sum[a_,b_] := BitXor[a,b]
 
prod[a_, b_] := Module[{x, y, i, t, F}, 
    If[a > b, x = b; y = a, x = a; y = b]; 
    If[x == 0, Return[0]]; 
    If[x == 1, Return[y]];
    If[y == 2, Return[3]]; 
    If[y == 3, If[x==2,Return 1,Return 2]];
    For[F = 4, True, F = F*F, 
       If[y == F, If[x < y, Return[x*y], Return[3*(y/2)]]]; 
       If[y < 2*F, Return[sum[prod[F, x], prod[y - F, x]]]]; 
       For[t = 2*F, t < F*F, t = 2*t, 
          If[y == t, 
             If[x < F, Return[prod[prod[x, t/F], F]]]; 
             For[i = F, i < t, i = 2*i, 
                If[x == i, Return[prod[prod[F, F], prod[t/F, i/F]]]]; 
                If[x < 2*i, Return[sum[prod[t, i], prod[t, x - i]]]]; 
             ]; 
             If[x == t, Return[prod[prod[F, F], prod[t/F, t/F]]]]; 
          ]; 
          If[y < 2*t, Return[sum[prod[t, x], prod[y - t, x]]]];
       ]; 
    ]; 
]