Algorithm to multiply nimbers

An algorithm is given at https://www.ics.uci.edu/~eppstein/numth/ (C++ implementation of J.H.Conway's "nimber" arithmetic.). The function to actually perform the multiplication is at nimber.C:316:nim_times.

Here is an algorithm to multiply nimbers. From now on, $+$ and $\cdot$ will refer to nimber operations, while operations enclosed in brackets will denote the usual math on $\mathbb N$. That is, $2+3=1$, but $[2+3]=5$.

Let $F_n=[2^{2^n}]$. In addition to the rules you stated, that $F_{n}F_{m}=[F_nF_m]$ when $n\neq m$, and $F_n^2=[(3/2)F_n]=F_n+[F_n/2]$, it can also be shown that $$ x<F_n \implies xF_n=[xF_n] $$ That is, the nimber product of a Fermat $2$-power with any number less than itself is equal to the regular product.

Now, onto the algorithm. Given two nimbers $a$ and $b$, you first find natural numbers $m,n$ and nimbers $a_1,a_2,b_1,b_2$ for which $a_1,a_2<F_m$, $b_1,b_2<F_n$, and $$ a=a_1F_m+a_2, \qquad b=b_1F_n+b_2 $$ Explicitly, $F_m$ is the largest Fermat $2$-power less than $a$, $a_1=[\lfloor a/F_m\rfloor]$, and $a_2=[a\pmod {F_m}]$, and similarly for $b_1$ and $b_2$.

First suppose $m$ and $n$ are unequal, say $m<n$. Then $$ ab=(ab_1)F_n+(ab_2) $$ The nimber products $ab_1$ and $ab_2$ can be computed recursively, and then $(ab_1)$ can be multiplied with $F_n$ in the ordinary sense, since it will be true that $ab_1<F_n$.

So, from now on assume $m=n$. Then \begin{align} ab &=(a_1F_n+a_2)(b_1F_n+b_2) \\&=a_1b_1F_n^2+(a_1b_2+a_2b_1)F_n+a_2b_2 \\&=(a_1b_1+a_1b_2+a_2b_1)F_n+a_2b_2+a_1b_1\cdot[F_n/2] \end{align} Therefore, we can compute $ab$ as follows:

• Compute $p_1=a_1b_1,p_2=a_2b_2,p_3=(a_1+a_2)(b_1+b_2)$, and $p_4=p_1\cdot [F_n/2]$ using recursive calls to the multiplication function.

• Compute $p_5=p_3 + p_2$, which is equal to $a_1b_1+a_1b_2+a_2b_1$, and then find the ordinary product of $p_5$ with $F_n$. Finally, the result of this is added to $p_2+p_4$ (in the nim sense).

For the runtime of this algorithm, we start with a product of two numbers with some number of bits, and then we compute this using four recursive calls to multiplication on numbers with half as many bits in their binary representation, along with doing a linear amount of work in terms of additions. That is, if $T(n)$ is the runtime of the algorithm when both $a$ and $b$ have $n$ bits, then $$ T(n)=4T(n/2)+O(n) $$ which implies $T(n)=O(n^2)$.