4
$\begingroup$

Let $a,b$ be nimbers. Is there an efficient algorithm to calculate $a*b$, the nim-product of $a$ and $b$?

The following rule seems like it could be helpful:

$$ 2^{2^m} * 2^{2^n} = \begin{cases} 2^{2^m} 2^{2^n} & \text{if $m \ne n$} \\ 3(2^{2^m - 1}) & \text{if $m = n$} \\ \end{cases}. $$

Juxtaposition denotes ordinary ordinal multiplication here (not nim-multiplication).

$\endgroup$
2
  • 1
    $\begingroup$ I think, the recursive algorithm should work fine. You can somehow combine Karatsuba algorithm with the representation of a nim number $a$ as $a = bk+c$ where $k=[\log_2\log_2 a]$ where $b,c \leq k.$ $\endgroup$ – Ehsan M. Kermani Aug 26 '14 at 3:07
  • $\begingroup$ In this thread there is a bit more. The rule you have, which might be more suggestive to write in the form $2^{2^n}*2^{2^n}=2^{2^n}+2^{2^{n-1}}$ (unless I made a mistake), is related to a recursive construction of this field as a tower of quadratic extensions. IIRC the material linked to in that question was nice. My answer there is probably less useful, because it simply reworks a few things from this tower of quadratic extensions, but does not touch nimbers. $\endgroup$ – Jyrki Lahtonen Aug 26 '14 at 5:33
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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+b_1)(a_2+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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.