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).
Answer
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.
No comments:
Post a Comment