Nim Multiplication

Question

Background

If you do much code golfing, you're likely aware of the bitwise XOR operation. Given two integers, it gives another integer with 1s in the bits where the two inputs differ. So, for example, 1010 XOR 0011 = 1001.

It turns out to be very useful in game theory, where it's better known as the "nim sum". If you have the sum of two games (that is, you're making moves in one game at a time), the value of the position is the nim sum of the values of the positions in each individual game.

But we can take this a step further. With nim addition and an appropriate definition of nim multiplication, we can form a field from the nonnegative integers. So the challenge is to golf nim multiplication.

Definition

Nim multiplication obeys the following rules:
The nim product of a Fermat 2-power n = (2^(2^k)) with any smaller number is the ordinary product.
The nim product of a Fermat 2-power n with itself is 3n/2.
Nim multiplication distributes over nim addition.
Nim multiplication is commutative and associative (as is nim addition).
The multiplicative identity is 1 (and the additive identity is 0).

Any nonnegative integer can be written as the nim sum of distinct powers of two, and any power of two can be written as the product of distinct Fermat numbers, so this is sufficient to define nim multiplication for all nonnegative integers.

Example

That was all pretty abstract, so let's work through an example. I'll use + to denote nim addition (XOR) and * for nim multiplication.

6 * 13
= (4 + 2) * (8 + 4 + 1)
= (4 + 2) * ((4 * 2) + 4 + 1)
= (4 * 4 * 2) + (4 * 2 * 2) + (4 * 4) + (4 * 2) + (4 * 1) + (2 * 1)
= (6 * 2) + (4 * 3) + 6 + 8 + 4 + 2
= ((4 + 2) * 2) + 12 + 6 + 8 + 4 + 2
= (4 * 2) + (2 * 2) + 12 + 6 + 8 + 4 + 2
= 8 + 3 + 12 + 6 + 8 + 4 + 2
= 15

Additional Test Cases

4, 4 -> 6
4, 3 -> 12
4, 7 -> 10
2, 4 -> 8
2, 3 -> 1
1, 42 -> 42

Challenge

Write a program or function which, given two nonnegative integers in any convenient form, computes their nim product.

This is code-golf, so shortest submission wins.

Answer 1

Nim, 120 bytes

proc f(a,b:int):int=
 var s={0..a*b}
 for i in 0..<a*b:s=s-{f(i%%a,i/%a)xor f(a,i/%a)xor f(i%%a,b)}
 for i in s:return i

Try it online!

OK, this might be crazy, but somebody had to do Nim multiplication in Nim...

This is standard algorithm from Wikipedia. The problem is that I don't know the language, so had to learn the basics on the fly. In particular, I was surprised that -= and min didn't work for sets, and the best way I managed to find for extracting the minimum was to use the iterator and return the first value. Hopefully, Nim experts will help me to improve this.

Answer 2

Python 2, 85 bytes

f=lambda x,y:min(set(range(x*y+1))-{f(i%x,i/x)^f(x,i/x)^f(i%x,y)for i in range(x*y)})

Try it online!

Slow as heck. Computes mex({α′ β ⊕ α β′ ⊕ α' β′ : α′ < α, β′ < β}) recursively.

Answer 3

Jelly, 16 bytes

p’ß/;ß"^/ʋ€ṭ‘ḟ$Ṃ

Uses the recursive formula xy = mex({ay ⊕ xb ⊕ ab : a < x, b < y}) for nimber multiplication.

Try it online!

How it works

p’ß/;ß"^/ʋ€ṭ‘ḟ$Ṃ  Main link. Left argument: x. Right argument: y.

p                 Cartesian product; yield the array of all pairs [a, b] such that
                  0 < a ≤ x and 0 < b ≤ y.
 ’                Decrement, changing the conditions to 0 ≤ a < x and 0 ≤ b < y.
          ṭ       Tack; yield [y, x].
        ʋ€        Combine the four links to the left into a dyadic chain. Call it
                  with right argument [y, x] and each of the [a, b] as left one.
  ß/                  Reduce [a, b] by the main link, computing the product ab.
     ß"               Zip [a, b] with [y, x] using the main link, computing the
                      array of products [ay, xb].
    ;                 Concatenate, yielding [ab, ay, xb].
       ^/             Reduce by bitwise XOR, yielding ab ⊕ ay ⊕ xb.
                  All that's left is to compute the minimum excluded (mex) non-
                  negative integer.
             $    Combine the two links to the left into a monadic chain.
           ‘          Increment the XOR sums.
            ḟ         Filterfalse; remove all incremented sums that appear in the
                      original sums.
              Ṃ  Take the minimum if the resulting array is non-empty or yield 0.
                 If x = 0 or y = 0, the array of sums is empty and Ṃ yields 0.
                 If x > 0 and y > 0, since 0 is among the sums, this finds the
                 smallest non-sum n+1 such that n ≥ 0 is a sum.
                 In either case, Ṃ yields xy.

Answer 4

CGSuite, 52 39 22 bytes

(a,b)->a.NimProduct(b)

Didn't realize it has this builtin, and anonymous "procedures".

Original version, 36 bytes:

(a,b)->*a.ConwayProduct(*b).NimValue

Or 25 bytes if the input/output could be nimbers:

(a,b)->a.ConwayProduct(b)

Well, I hoped *a**b/a*b to work, but it doesn't.

Answer 5

Pyth, 21 bytes

Mf-TsmmxxgkdgkHgGdGH0

Demonstration

Uses the minimum excluded element formulation of nim multiplication, as given here.

Two nested maps are used to iterate over all smaller values (mm ... GH), then the results are flattened (s). The clever part comes with f-T ... 0, where we iterate over integers upward from 0 to find the first one not contained in the set mentioned above. By doing it this way, we don't need to calculate an iteration upper bound, saving a few bytes.

In the end, the function g computes the nim product.

Answer 6

JavaScript (ES6), 142 128 bytes

f=(x,y,z=Math.log2,v=x&-x,t=z(x),u=z(y),s=t&u,r=s&-s)=>x<2|y<2?x*y:x>v?f(v,y)^f(x^v,y):y&y-1?f(y,x):r?f(f(x>>r,y>>r),3<<r-1):x*y

<div oninput=o.textContent=f(x.value,y.value)><input id=x><input id=y><pre id=o>

The first step is to split both x and y into an XOR of powers of 2, take their pairwise nim products, and then XOR the results (because nim product distributes over XOR). Once we have recursed to the case of x and y both powers of 2, we note that Fermat powers multiply with each other using ordinary arithmetic, so we can therefore factorise x and y into Fermat powers. If x and y don't share a Fermat power we can reverse the process and simply return x * y. However if they share a Fermat power, then we divide both x and y by that power, calculate the nim product, then take the nim product with the nim square of that Fermat power. Ungolfed:

function nimprod(x, y) {
    if (x < 2 || y < 2) return x * y;
    var v = x & -x;
    if (x > v) return nimprod(v, y) ^ nimprod(x ^ v, y); // nimprod distributes over ^
    if (y & (y - 1)) return nimprod(y, x); // x is a power of 2 but y is not
    var t = Math.log2(x);
    var u = Math.log2(y);
    var s = t & u;
    if (!s) return x * y; // x and y do not share a Fermat power
    var r = s & -s;
    return nimprod(nimprod(x >> r, y >> r), 3 << r - 1); // square the Fermat power
}

Answer 7

Wolfram Language (Mathematica), 81 bytes

x_±y_:=Min@Complement[Range[0,x*y],##&@@Array[BitXor[x±#2,#±y,±##]&,{x,y},0]]

Try it online!

Using the formula:

\$\alpha \beta = \operatorname{mex}(\{\,\alpha' \beta + \alpha \beta' + \alpha' \beta' : \alpha' < \alpha , \beta' < \beta \,\}).\$