Friday, 3 May 2019

finite fields - Algorithm to multiply nimbers



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



The following rule seems like it could be helpful:



22m22n={22m22nif mn3(22m1)if m=n.



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

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...