Nimber arithmetic: Difference between revisions
Content added Content deleted
m (added whitespace.) |
|||
| Line 774: | Line 774: | ||
nim-product: 21508 ⊗ 42689 = 35202 |
nim-product: 21508 ⊗ 42689 = 35202 |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
|||
{{trans|FreeBASIC}} |
|||
<lang Nim>import bitops, strutils |
|||
type Nimber = Natural |
|||
func hpo2(n: Nimber): Nimber = |
|||
## Return the highest power of 2 that divides a given number. |
|||
n and -n |
|||
func lhpo2(n: Nimber): Nimber = |
|||
## Return the base 2 logarithm of the highest power of 2 dividing a given number. |
|||
fastLog2(hpo2(n)) |
|||
func ⊕(x, y: Nimber): Nimber = |
|||
## Return the nim-sum of two nimbers. |
|||
x xor y |
|||
func ⊗(x, y: Nimber): Nimber = |
|||
## Return the nim-product of two nimbers. |
|||
if x < 2 and y < 2: return x * y |
|||
var h = hpo2(x) |
|||
if x > h: |
|||
return ⊗(h, y) xor ⊗(x xor h, y) # Recursively break "x" into its powers of 2. |
|||
if hpo2(y) < y: |
|||
return ⊗(y, x) # Recursively break "y" into its powers of 2 by flipping the operands. |
|||
# Now both "x" and "y" are powers of two. |
|||
let comp = lhpo2(x) * lhpo2(y) |
|||
if comp == 0: return x * y # No Fermat number in common. |
|||
h = hpo2(comp) |
|||
# A fermat number square is its sequimultiple. |
|||
result = ⊗(⊗(x div (1 shl h), y div (1 shl h)), 3 * (1 shl (h - 1))) |
|||
when isMainModule: |
|||
for (opname, op) in [("⊕", ⊕), ("⊗", ⊗)]: |
|||
stdout.write ' ', opname, " |" |
|||
for i in 0..15: stdout.write ($i).align(3) |
|||
stdout.write "\n--- -", repeat('-', 48), '\n' |
|||
for b in 0..15: |
|||
stdout.write ($b).align(2), " |" |
|||
for a in 0..15: |
|||
stdout.write ($op(a, b)).align(3) |
|||
stdout.write '\n' |
|||
echo "" |
|||
const A = 21508 |
|||
const B = 42689 |
|||
echo "$1 ⊕ $2 = $3".format(A, B, ⊕(A, B)) |
|||
echo "$1 ⊗ $2 = $3".format(A, B, ⊗(A, B))</lang> |
|||
{{out}} |
|||
<pre> ⊕ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|||
--- ------------------------------------------------- |
|||
0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|||
1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 |
|||
2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 |
|||
3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 |
|||
4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 |
|||
5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 |
|||
6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 |
|||
7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 |
|||
8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 |
|||
9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 |
|||
10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 |
|||
11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 |
|||
12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 |
|||
13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 |
|||
14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 |
|||
15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 |
|||
⊗ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|||
--- ------------------------------------------------- |
|||
0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
|||
1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|||
2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 |
|||
3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 |
|||
4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 |
|||
5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 |
|||
6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 |
|||
7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 |
|||
8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 |
|||
9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 |
|||
10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 |
|||
11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 |
|||
12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 |
|||
13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 |
|||
14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 |
|||
15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 |
|||
21508 ⊕ 42689 = 62149 |
|||
21508 ⊗ 42689 = 35202</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Revision as of 22:41, 23 February 2021
You are encouraged to solve this task according to the task description, using any language you may know.
The nimbers, also known as Grundy numbers, are the values of the heaps in the game of Nim. They have addition and multiplication operations, unrelated to the addition and multiplication of the integers. Both operations are defined recursively:
The nim-sum of two integers m and n, denoted m⊕n is given by
m⊕n=mex(m'⊕n, m⊕ n' : m'<m, n'<n),
where the mex function returns the smallest integer not in the set. More simply: collect all the nim-sums of m and numbers smaller than n, and all nim-sums of n with all numbers less than m and find the smallest number not in that set. Fortunately, this also turns out to be equal to the bitwise xor of the two.
The nim-product is also defined recursively:
m⊗n=mex([m'⊗n]⊕[m⊗n']⊕[m'⊗n'] : m'<m, n'<n)
The product is more complicated and time-consuming to evaluate, but there are a few facts which may help:
- The operators ⊕ and ⊗ are commutative and distributive
- the nim-product of a Fermat power (22k) and a smaller number is their ordinary product
- the nim-square of a Fermat power x is the ordinary product 3x/2
- Tasks
- Create nimber addition and multiplication tables up to at least 15
- Find the nim-sum and nim-product of two five digit integers of your choice
C
<lang c>#include <stdio.h>
- include <stdint.h>
// highest power of 2 that divides a given number uint32_t hpo2(uint32_t n) {
return n & -n;
}
// base 2 logarithm of the highest power of 2 dividing a given number uint32_t lhpo2(uint32_t n) {
uint32_t q = 0, m = hpo2(n);
for (; m % 2 == 0; m >>= 1, ++q) {}
return q;
}
// nim-sum of two numbers uint32_t nimsum(uint32_t x, uint32_t y) {
return x ^ y;
}
// nim-product of two numbers uint32_t nimprod(uint32_t x, uint32_t y) {
if (x < 2 || y < 2)
return x * y;
uint32_t h = hpo2(x);
if (x > h)
return nimprod(h, y) ^ nimprod(x ^ h, y);
if (hpo2(y) < y)
return nimprod(y, x);
uint32_t xp = lhpo2(x), yp = lhpo2(y);
uint32_t comp = xp & yp;
if (comp == 0)
return x * y;
h = hpo2(comp);
return nimprod(nimprod(x >> h, y >> h), 3 << (h - 1));
}
void print_table(uint32_t n, char op, uint32_t(*func)(uint32_t, uint32_t)) {
printf(" %c |", op);
for (uint32_t a = 0; a <= n; ++a)
printf("%3d", a);
printf("\n--- -");
for (uint32_t a = 0; a <= n; ++a)
printf("---");
printf("\n");
for (uint32_t b = 0; b <= n; ++b) {
printf("%2d |", b);
for (uint32_t a = 0; a <= n; ++a)
printf("%3d", func(a, b));
printf("\n");
}
}
int main() {
print_table(15, '+', nimsum);
printf("\n");
print_table(15, '*', nimprod);
const uint32_t a = 21508, b = 42689;
printf("\n%d + %d = %d\n", a, b, nimsum(a, b));
printf("%d * %d = %d\n", a, b, nimprod(a, b));
return 0;
}</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202
C++
<lang cpp>#include <cstdint>
- include <functional>
- include <iomanip>
- include <iostream>
// highest power of 2 that divides a given number uint32_t hpo2(uint32_t n) {
return n & -n;
}
// base 2 logarithm of the highest power of 2 dividing a given number uint32_t lhpo2(uint32_t n) {
uint32_t q = 0, m = hpo2(n);
for (; m % 2 == 0; m >>= 1, ++q) {}
return q;
}
// nim-sum of two numbers uint32_t nimsum(uint32_t x, uint32_t y) {
return x ^ y;
}
// nim-product of two numbers uint32_t nimprod(uint32_t x, uint32_t y) {
if (x < 2 || y < 2)
return x * y;
uint32_t h = hpo2(x);
if (x > h)
return nimprod(h, y) ^ nimprod(x ^ h, y);
if (hpo2(y) < y)
return nimprod(y, x);
uint32_t xp = lhpo2(x), yp = lhpo2(y);
uint32_t comp = xp & yp;
if (comp == 0)
return x * y;
h = hpo2(comp);
return nimprod(nimprod(x >> h, y >> h), 3 << (h - 1));
}
void print_table(uint32_t n, char op, std::function<uint32_t(uint32_t, uint32_t)> func) {
std::cout << ' ' << op << " |";
for (uint32_t a = 0; a <= n; ++a)
std::cout << std::setw(3) << a;
std::cout << "\n--- -";
for (uint32_t a = 0; a <= n; ++a)
std::cout << "---";
std::cout << '\n';
for (uint32_t b = 0; b <= n; ++b) {
std::cout << std::setw(2) << b << " |";
for (uint32_t a = 0; a <= n; ++a)
std::cout << std::setw(3) << func(a, b);
std::cout << '\n';
}
}
int main() {
print_table(15, '+', nimsum);
printf("\n");
print_table(15, '*', nimprod);
const uint32_t a = 21508, b = 42689;
std::cout << '\n';
std::cout << a << " + " << b << " = " << nimsum(a, b) << '\n';
std::cout << a << " * " << b << " = " << nimprod(a, b) << '\n';
return 0;
}</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202
Factor
<lang factor>USING: combinators formatting io kernel locals math sequences ;
! highest power of 2 that divides a given number
- hpo2 ( n -- n ) dup neg bitand ;
! base 2 logarithm of the highest power of 2 dividing a given number
- lhpo2 ( n -- n )
hpo2 0 swap [ dup even? ] [ -1 shift [ 1 + ] dip ] while drop ;
! nim sum of two numbers ALIAS: nim-sum bitxor
! nim product of two numbers
- nim-prod ( x y -- prod )
x hpo2 :> h!
0 :> comp!
{
{ [ x 2 < y 2 < or ] [ x y * ] }
{ [ x h > ] [ h y nim-prod x h bitxor y nim-prod bitxor ] } ! recursively break x into its powers of 2
{ [ y hpo2 y < ] [ y x nim-prod ] } ! recursively break y into its powers of 2 by flipping the operands
{ [ x y [ lhpo2 ] bi@ bitand comp! comp zero? ] [ x y * ] } ! we have no fermat power in common
[
comp hpo2 h! ! a fermat number square is its sequimultiple
x h neg shift y h neg shift nim-prod
3 h 1 - shift nim-prod
]
} cond ;
! words for printing tables
- dashes ( n -- ) [ CHAR: - ] "" replicate-as write ;
- top1 ( str -- ) " %s |" printf 16 <iota> [ "%3d" printf ] each nl ;
- top2 ( -- ) 3 dashes bl 49 dashes nl ;
- row ( n quot -- )
over "%2d |" printf curry 16 <iota> swap [ call "%3d" printf ] curry each ; inline
- table ( quot str -- )
top1 top2 16 <iota> swap [ row nl ] curry each ; inline
! task [ nim-sum ] "+" table nl [ nim-prod ] "*" table nl 33333 77777 [ 2dup nim-sum "%d + %d = %d\n" printf ] [ 2dup nim-prod "%d * %d = %d\n" printf ] 2bi</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 33333 + 77777 = 110052 33333 * 77777 = 2184564070
FreeBASIC
<lang freebasic>function hpo2( n as uinteger ) as uinteger
'highest power of 2 that divides a given number return n and -n
end function
function lhpo2( n as uinteger ) as uinteger
'base 2 logarithm of the highest power of 2 dividing a given number
dim as uinteger q = 0, m = hpo2( n )
while m mod 2 = 0
m = m shr 1
q += 1
wend
return q
end function
function nimsum(x as uinteger, y as uinteger) as uinteger
'nim-sum of two numbers return x xor y
end function
function nimprod(x as uinteger, y as uinteger) as uinteger
'nim-product of two numbers if x < 2 orelse y < 2 then return x*y dim as uinteger h = hpo2(x) if x > h then return nimprod(h, y) xor nimprod(x xor h, y) 'recursively break x into its powers of 2 if hpo2(y) < y then return nimprod(y, x) 'recursively break y into its powers of 2 by flipping the operands 'now both x and y are powers of two dim as uinteger xp = lhpo2(x), yp = lhpo2(y), comp = xp and yp if comp = 0 then return x*y 'we have no fermat power in common h = hpo2(comp) return nimprod(nimprod(x shr h, y shr h), 3 shl (h - 1)) 'a fermat number square is its sequimultiple
end function
'print tables
function padto( i as ubyte, j as integer ) as string
return wspace(i-len(str(j)))+str(j)
end function
dim as uinteger a, b dim as string outstr
outstr = " + | " for a = 0 to 15
outstr += padto(2, a)+" "
next a print outstr print "--- -------------------------------------------------" for b = 0 to 15
outstr = padto(2, b)+ " | "
for a = 0 to 15
outstr += padto(2, nimsum(a,b))+" "
next a
print outstr
next b print outstr = " * | " for a = 0 to 15
outstr += padto(2, a)+" "
next a print outstr print "--- -------------------------------------------------" for b = 0 to 15
outstr = padto(2, b)+ " | "
for a = 0 to 15
outstr += padto(2, nimprod(a,b))+" "
next a
print outstr
next b print a = 21508 b = 42689
print using "##### + ##### = ##########"; a; b; nimsum(a,b) print using "##### * ##### = ##########"; a; b; nimprod(a,b)</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202
Go
<lang go>package main
import (
"fmt" "strings"
)
// Highest power of two that divides a given number. func hpo2(n uint) uint { return n & (-n) }
// Base 2 logarithm of the highest power of 2 dividing a given number. func lhpo2(n uint) uint {
q := uint(0)
m := hpo2(n)
for m%2 == 0 {
m = m >> 1
q++
}
return q
}
// nim-sum of two numbers. func nimsum(x, y uint) uint { return x ^ y }
// nim-product of two numbers. func nimprod(x, y uint) uint {
if x < 2 || y < 2 {
return x * y
}
h := hpo2(x)
if x > h {
return nimprod(h, y) ^ nimprod(x^h, y) // break x into powers of 2
}
if hpo2(y) < y {
return nimprod(y, x) // break y into powers of 2 by flipping operands
}
xp, yp := lhpo2(x), lhpo2(y)
comp := xp & yp
if comp == 0 {
return x * y // no Fermat power in common
}
h = hpo2(comp)
// a Fermat number square is its sequimultiple
return nimprod(nimprod(x>>h, y>>h), 3<<(h-1))
}
type fnop struct {
fn func(x, y uint) uint op string
}
func main() {
for _, f := range []fnop{{nimsum, "+"}, {nimprod, "*"}} {
fmt.Printf(" %s |", f.op)
for i := 0; i <= 15; i++ {
fmt.Printf("%3d", i)
}
fmt.Println("\n--- " + strings.Repeat("-", 48))
for i := uint(0); i <= 15; i++ {
fmt.Printf("%2d |", i)
for j := uint(0); j <= 15; j++ {
fmt.Printf("%3d", f.fn(i, j))
}
fmt.Println()
}
fmt.Println()
}
a := uint(21508)
b := uint(42689)
fmt.Printf("%d + %d = %d\n", a, b, nimsum(a, b))
fmt.Printf("%d * %d = %d\n", a, b, nimprod(a, b))
}</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------ 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------ 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202
Java
<lang java>import java.util.function.IntBinaryOperator;
public class Nimber {
public static void main(String[] args) {
printTable(15, '+', (x, y) -> nimSum(x, y));
System.out.println();
printTable(15, '*', (x, y) -> nimProduct(x, y));
System.out.println();
int a = 21508, b = 42689;
System.out.println(a + " + " + b + " = " + nimSum(a, b));
System.out.println(a + " * " + b + " = " + nimProduct(a, b));
}
// nim-sum of two numbers
public static int nimSum(int x, int y) {
return x ^ y;
}
// nim-product of two numbers
public static int nimProduct(int x, int y) {
if (x < 2 || y < 2)
return x * y;
int h = hpo2(x);
if (x > h)
return nimProduct(h, y) ^ nimProduct(x ^ h, y);
if (hpo2(y) < y)
return nimProduct(y, x);
int xp = lhpo2(x), yp = lhpo2(y);
int comp = xp & yp;
if (comp == 0)
return x * y;
h = hpo2(comp);
return nimProduct(nimProduct(x >> h, y >> h), 3 << (h - 1));
}
// highest power of 2 that divides a given number
private static int hpo2(int n) {
return n & -n;
}
// base 2 logarithm of the highest power of 2 dividing a given number
private static int lhpo2(int n) {
int q = 0, m = hpo2(n);
for (; m % 2 == 0; m >>= 1, ++q) {}
return q;
}
private static void printTable(int n, char op, IntBinaryOperator func) {
System.out.print(" " + op + " |");
for (int a = 0; a <= n; ++a)
System.out.print(String.format("%3d", a));
System.out.print("\n--- -");
for (int a = 0; a <= n; ++a)
System.out.print("---");
System.out.println();
for (int b = 0; b <= n; ++b) {
System.out.print(String.format("%2d |", b));
for (int a = 0; a <= n; ++a)
System.out.print(String.format("%3d", func.applyAsInt(a, b)));
System.out.println();
}
}
}</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202
Julia
<lang julia>""" highest power of 2 that divides a given number """ hpo2(n) = n & -n
""" base 2 logarithm of the highest power of 2 dividing a given number """ lhpo2(n) = begin q, m = 0, hpo2(n); while iseven(m) m >>= 1; q += 1 end; q end
""" nim-sum of two numbers """ nimsum(x, y) = x ⊻ y
""" nim-product of two numbers """ function nimprod(x, y)
(x < 2 || y < 2) && return x * y h = hpo2(x) (x > h) && return nimprod(h, y) ⊻ nimprod(x ⊻ h, y) (hpo2(y) < y) && return nimprod(y, x) xp, yp = lhpo2(x), lhpo2(y) comp = xp & yp comp == 0 && return x * y h = hpo2(comp) return nimprod(nimprod(x >> h, y >> h), 3 << (h - 1))
end
""" print a table of nim-sums or nim-products """ function printtable(n, op)
println(" $op |", prod([lpad(i, 3) for i in 0:n]), "\n--- -", "---"^(n + 1))
for j in 0:n
print(lpad(j, 2), " |")
for i in 0:n
print(lpad(op == '⊕' ? nimsum(i, j) : nimprod(i, j), 3))
end
print(j == n ? "\n\n" : "\n")
end
end
const a, b = 21508, 42689
printtable(15, '⊕') printtable(15, '⊗') println("nim-sum: $a ⊕ $b = $(nimsum(a, b))") println("nim-product: $a ⊗ $b = $(nimprod(a, b))")
</lang>
- Output:
⊕ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ⊗ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 nim-sum: 21508 ⊕ 42689 = 62149 nim-product: 21508 ⊗ 42689 = 35202
Nim
<lang Nim>import bitops, strutils
type Nimber = Natural
func hpo2(n: Nimber): Nimber =
## Return the highest power of 2 that divides a given number. n and -n
func lhpo2(n: Nimber): Nimber =
## Return the base 2 logarithm of the highest power of 2 dividing a given number. fastLog2(hpo2(n))
func ⊕(x, y: Nimber): Nimber =
## Return the nim-sum of two nimbers. x xor y
func ⊗(x, y: Nimber): Nimber =
## Return the nim-product of two nimbers.
if x < 2 and y < 2: return x * y
var h = hpo2(x) if x > h: return ⊗(h, y) xor ⊗(x xor h, y) # Recursively break "x" into its powers of 2. if hpo2(y) < y: return ⊗(y, x) # Recursively break "y" into its powers of 2 by flipping the operands.
# Now both "x" and "y" are powers of two. let comp = lhpo2(x) * lhpo2(y) if comp == 0: return x * y # No Fermat number in common. h = hpo2(comp) # A fermat number square is its sequimultiple. result = ⊗(⊗(x div (1 shl h), y div (1 shl h)), 3 * (1 shl (h - 1)))
when isMainModule:
for (opname, op) in [("⊕", ⊕), ("⊗", ⊗)]:
stdout.write ' ', opname, " |"
for i in 0..15: stdout.write ($i).align(3)
stdout.write "\n--- -", repeat('-', 48), '\n'
for b in 0..15:
stdout.write ($b).align(2), " |"
for a in 0..15:
stdout.write ($op(a, b)).align(3)
stdout.write '\n'
echo ""
const A = 21508 const B = 42689 echo "$1 ⊕ $2 = $3".format(A, B, ⊕(A, B)) echo "$1 ⊗ $2 = $3".format(A, B, ⊗(A, B))</lang>
- Output:
⊕ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ⊗ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 ⊕ 42689 = 62149 21508 ⊗ 42689 = 35202
Perl
<lang perl>use strict; use warnings; use feature 'say'; use Math::AnyNum qw(:overload);
sub msb {
my($n, $base) = (shift, 0); $base++ while $n >>= 1; $base;
}
sub lsb {
my $n = shift; msb($n & -$n);
}
sub nim_sum {
my($x,$y) = @_; $x ^ $y
}
sub nim_prod {
no warnings qw(recursion); my($x,$y) = @_; return $x * $y if $x < 2 or $y < 2; my $h = 2 ** lsb($x); return nim_sum( nim_prod($h, $y), nim_prod(nim_sum($x,$h), $y)) if $x > $h; return nim_prod($y,$x) if lsb($y) < msb($y); return $x * $y unless my $comp = lsb($x) & lsb($y); $h = 2 ** lsb($comp); nim_prod(nim_prod(($x >> $h),($y >> $h)), (3 << ($h - 1)));
}
my $upto = 15; for (['+', \&nim_sum], ['*', \&nim_prod]) {
my($op, $f) = @$_;
print " $op |"; printf '%3d', $_ for 0..$upto;
say "\n───┼" . ('────' x ($upto-3));
for my $r (0..$upto) {
printf('%2s |', $r);
printf '%3s', &$f($r, $_) for 0..$upto;
print "\n";
}
print "\n";
}
say nim_sum(21508, 42689); say nim_prod(21508, 42689); say nim_sum(2150821508215082150821508, 4268942689426894268942689); say nim_prod(2150821508215082150821508, 4268942689426894268942689); # pretty slow</lang>
- Output:
+ │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ───┼──────────────────────────────────────────────── 0 │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 │ 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 │ 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 │ 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 │ 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 │ 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 │ 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 │ 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 │ 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 │ 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 │ 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 │ 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 │ 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 │ 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 │ 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 │ 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ───┼──────────────────────────────────────────────── 0 │ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 │ 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 │ 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 │ 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 │ 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 │ 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 │ 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 │ 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 │ 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 │ 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 │ 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 │ 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 │ 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 │ 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 │ 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 62149 35202 2722732241575131661744101 221974472829844568827862736061997038065
Phix
<lang Phix>function hpo2(integer n)
-- highest power of 2 that divides a given number return and_bits(n,-n)
end function
function lhpo2(integer n)
-- base 2 logarithm of the highest power of 2 dividing a given number
integer q = 0, m = hpo2(n)
while remainder(m,2)=0 do
m = floor(m/2)
q += 1
end while
return q
end function
function nimsum(integer x, y)
-- nim-sum of two numbers return xor_bits(x,y)
end function
function nimprod(integer x, y)
-- nim-product of two numbers
if x < 2 or y < 2 then return x*y end if
integer h = hpo2(x)
if x > h then
return xor_bits(nimprod(h, y),nimprod(xor_bits(x,h), y)) -- recursively break x into its powers of 2
elsif hpo2(y) < y then
return nimprod(y, x) -- recursively break y into its powers of 2 by flipping the operands
end if
-- now both x and y are powers of two
integer xp = lhpo2(x), yp = lhpo2(y), comp = and_bits(xp,yp)
if comp = 0 then return x*y end if -- we have no fermat power in common
h = hpo2(comp)
return nimprod(nimprod(floor(x/power(2,h)), floor(y/power(2,h))), 3*power(2,h-1)) -- a fermat number square is its sequimultiple
end function
procedure print_table(integer n, op)
-- print a table of nim-sums or nim-products
printf(1," %c | "&join(repeat("%3d",n+1))&"\n",op&tagset(n,0))
printf(1,"---+%s\n",repeat('-',(n+1)*4))
for j=0 to n do
printf(1,"%2d |",j)
for i=0 to n do
printf(1,"%4d",iff(op='+' ? nimsum(i, j) : nimprod(i, j)))
end for
printf(1,"\n")
end for
printf(1,"\n")
end procedure
print_table(25, '+') print_table(25, '*') constant a = 21508, b = 42689 printf(1,"%5d + %5d = %5d\n",{a,b,nimsum(a,b)}) printf(1,"%5d * %5d = %5d\n",{a,b,nimprod(a,b)})</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ---+-------------------------------------------------------------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 18 19 16 17 22 23 20 21 26 27 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 19 18 17 16 23 22 21 20 27 26 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 20 21 22 23 16 17 18 19 28 29 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 21 20 23 22 17 16 19 18 29 28 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 22 23 20 21 18 19 16 17 30 31 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 21 20 19 18 17 16 31 30 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 24 25 26 27 28 29 30 31 16 17 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 25 24 27 26 29 28 31 30 17 16 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 26 27 24 25 30 31 28 29 18 19 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 27 26 25 24 31 30 29 28 19 18 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 28 29 30 31 24 25 26 27 20 21 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 29 28 31 30 25 24 27 26 21 20 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 30 31 28 29 26 27 24 25 22 23 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 31 30 29 28 27 26 25 24 23 22 16 | 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 0 1 2 3 4 5 6 7 8 9 17 | 17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30 1 0 3 2 5 4 7 6 9 8 18 | 18 19 16 17 22 23 20 21 26 27 24 25 30 31 28 29 2 3 0 1 6 7 4 5 10 11 19 | 19 18 17 16 23 22 21 20 27 26 25 24 31 30 29 28 3 2 1 0 7 6 5 4 11 10 20 | 20 21 22 23 16 17 18 19 28 29 30 31 24 25 26 27 4 5 6 7 0 1 2 3 12 13 21 | 21 20 23 22 17 16 19 18 29 28 31 30 25 24 27 26 5 4 7 6 1 0 3 2 13 12 22 | 22 23 20 21 18 19 16 17 30 31 28 29 26 27 24 25 6 7 4 5 2 3 0 1 14 15 23 | 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 7 6 5 4 3 2 1 0 15 14 24 | 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 8 9 10 11 12 13 14 15 0 1 25 | 25 24 27 26 29 28 31 30 17 16 19 18 21 20 23 22 9 8 11 10 13 12 15 14 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ---+-------------------------------------------------------------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 32 34 35 33 40 42 43 41 44 46 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 48 51 49 50 60 63 61 62 52 55 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 64 68 72 76 70 66 78 74 75 79 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 80 85 90 95 82 87 88 93 83 86 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 96 102 107 109 110 104 101 99 103 97 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 112 119 121 126 122 125 115 116 127 120 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 128 136 140 132 139 131 135 143 141 133 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 144 153 158 151 159 150 145 152 149 156 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 160 170 175 165 163 169 172 166 161 171 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 176 187 189 182 183 188 186 177 185 178 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 192 204 196 200 205 193 201 197 198 202 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 208 221 214 219 217 212 223 210 222 211 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 224 238 231 233 229 235 226 236 234 228 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 240 255 245 250 241 254 244 251 242 253 16 | 0 16 32 48 64 80 96 112 128 144 160 176 192 208 224 240 24 8 56 40 88 72 120 104 152 136 17 | 0 17 34 51 68 85 102 119 136 153 170 187 204 221 238 255 8 25 42 59 76 93 110 127 128 145 18 | 0 18 35 49 72 90 107 121 140 158 175 189 196 214 231 245 56 42 27 9 112 98 83 65 180 166 19 | 0 19 33 50 76 95 109 126 132 151 165 182 200 219 233 250 40 59 9 26 100 119 69 86 172 191 20 | 0 20 40 60 70 82 110 122 139 159 163 183 205 217 229 241 88 76 112 100 30 10 54 34 211 199 21 | 0 21 42 63 66 87 104 125 131 150 169 188 193 212 235 254 72 93 98 119 10 31 32 53 203 222 22 | 0 22 43 61 78 88 101 115 135 145 172 186 201 223 226 244 120 110 83 69 54 32 29 11 255 233 23 | 0 23 41 62 74 93 99 116 143 152 166 177 197 210 236 251 104 127 65 86 34 53 11 28 231 240 24 | 0 24 44 52 75 83 103 127 141 149 161 185 198 222 234 242 152 128 180 172 211 203 255 231 21 13 25 | 0 25 46 55 79 86 97 120 133 156 171 178 202 211 228 253 136 145 166 191 199 222 233 240 13 20 21508 + 42689 = 62149 21508 * 42689 = 35202
Prolog
<lang prolog>% highest power of 2 that divides a given number hpo2(N, P):-
P is N /\ -N.
% base 2 logarithm of the highest power of 2 dividing a given number lhpo2(N, Q):-
hpo2(N, M), lhpo2_(M, 0, Q).
lhpo2_(M, Q, Q):-
1 is M mod 2, !.
lhpo2_(M, Q1, Q):-
M1 is M >> 1, Q2 is Q1 + 1, lhpo2_(M1, Q2, Q).
% nim-sum of two numbers nimsum(X, Y, Sum):-
Sum is X xor Y.
% nim-product of twp numbers nimprod(X, Y, Product):-
(X < 2 ; Y < 2), !, Product is X * Y.
nimprod(X, Y, Product):-
hpo2(X, H), X > H, !, nimprod(H, Y, P1), X1 is X xor H, nimprod(X1, Y, P2), Product is P1 xor P2.
nimprod(X, Y, Product):-
hpo2(Y, H), H < Y, !, nimprod(Y, X, Product).
nimprod(X, Y, Product):-
lhpo2(X, Xp),
lhpo2(Y, Yp),
Comp is Xp /\ Yp,
(Comp == 0 ->
Product is X * Y
;
hpo2(Comp, H),
X1 is X >> H,
Y1 is Y >> H,
Z is 3 << (H - 1),
nimprod(X1, Y1, P),
nimprod(P, Z, Product)
).
print_row(N, B, Function):-
writef('%3r |', [B]),
Goal =.. [Function, A, B, C],
forall(between(0, N, A), (Goal, writef('%3r', [C]))),
nl.
print_table(N, Operator, Function):-
writef(' %w |', [Operator]),
forall(between(0, N, A), writef('%3r', [A])),
writef('\n --- -', []),
forall(between(0, N, _), writef('---', [])),
nl,
forall(between(0, N, A), print_row(N, A, Function)).
main:-
print_table(15, '+', nimsum),
nl,
print_table(15, '*', nimprod),
nl,
A = 21508, B = 42689,
nimsum(A, B, Sum),
nimprod(A, B, Product),
writef('%w + %w = %w\n', [A, B, Sum]),
writef('%w * %w = %w\n', [A, B, Product]).</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202
Quackery
(Mostly translated from Julia, although 'translated' doesn't do the process justice.)
<lang Quackery>
[ dup negate & ] is hpo2 ( n --> n )
[ 1 & 0 = ] is even ( n --> b )
[ 0 swap hpo2
[ dup even while
1 >>
dip 1+ again ]
drop ] is lhpo2 ( n --> n )
[ ^ ] is nim+ ( n n --> n )
forward is nim* ( x y --> r )
[ over 2 < over 2 < or iff
* done
over dup hpo2
tuck > iff
[ 2dup swap nim*
dip [ rot nim+ swap nim* ]
nim+ ] done
drop
dup hpo2 over < iff
[ swap nim* ] done
over lhpo2 over lhpo2 &
dup 0 = iff
[ drop * ] done
hpo2 tuck >>
dip [ tuck >> ]
nim*
swap 1 - 3 swap <<
nim* ] resolves nim* ( x y --> r )
[ over size - space swap of swap join ] is justify ( $ n --> $ ) [ number$ 3 justify echo$ ] is j.echo ( n --> )
[ cr sp echo$ say "|"
temp put
16 times [ i^ j.echo ] cr
sp char - 3 of echo$
say "+"
char - 48 of echo$ cr
16 times
[ i^ dup j.echo
say " |"
16 times
[ dup i^
temp share do
j.echo ]
drop cr ]
temp release ] is tabulate ( $ x --> )
' nim+ $ "(+)" tabulate cr ' nim* $ "(*)" tabulate cr say " 10547 (+) 14447 = " 10547 14447 nim+ echo cr say " 10547 (*) 14447 = " 10547 14447 nim* echo cr
</lang>
- Output:
(+)| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ---+------------------------------------------------ 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 (*)| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ---+------------------------------------------------ 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 10547 (+) 14447 = 4444 10547 (*) 14447 = 4444
Raku
(or at least, heavily inspired by FreeBasic)
Not limited by integer size. Doesn't rely on twos complement bitwise and.
<lang perl6>sub infix:<⊕> (Int $x, Int $y) { $x +^ $y }
sub infix:<⊗> (Int $x, Int $y) {
return $x × $y if so $x|$y < 2; my $h = exp $x.lsb, 2; return ($h ⊗ $y) ⊕ (($x ⊕ $h) ⊗ $y) if $x > $h; return ($y ⊗ $x) if $y.lsb < $y.msb; return $x × $y unless my $comp = $x.lsb +& $y.lsb; $h = exp $comp.lsb, 2; (($x +> $h) ⊗ ($y +> $h)) ⊗ (3 +< ($h - 1))
}
- TESTING
my $upto = 26;
for <⊕>, &infix:<⊕>,
<⊗>, &infix:<⊗>
-> $op, &f {
put " $op │", ^$upto .fmt('%3s'), "\n───┼", '────' x $upto;
-> $r { put $r.fmt('%2s'), ' │', ^$upto .map: { &f($r, $_).fmt('%3s')} } for ^$upto;
put "\n";
}
put "21508 ⊕ 42689 = ", 21508 ⊕ 42689; put "21508 ⊗ 42689 = ", 21508 ⊗ 42689;
put "2150821508215082150821508 ⊕ 4268942689426894268942689 = ", 2150821508215082150821508 ⊕ 4268942689426894268942689; put "2150821508215082150821508 ⊗ 4268942689426894268942689 = ", 2150821508215082150821508 ⊗ 4268942689426894268942689;</lang>
- Output:
⊕ │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ───┼──────────────────────────────────────────────────────────────────────────────────────────────────────── 0 │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 │ 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24 2 │ 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 18 19 16 17 22 23 20 21 26 27 3 │ 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 19 18 17 16 23 22 21 20 27 26 4 │ 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 20 21 22 23 16 17 18 19 28 29 5 │ 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 21 20 23 22 17 16 19 18 29 28 6 │ 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 22 23 20 21 18 19 16 17 30 31 7 │ 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 21 20 19 18 17 16 31 30 8 │ 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 24 25 26 27 28 29 30 31 16 17 9 │ 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 25 24 27 26 29 28 31 30 17 16 10 │ 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 26 27 24 25 30 31 28 29 18 19 11 │ 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 27 26 25 24 31 30 29 28 19 18 12 │ 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 28 29 30 31 24 25 26 27 20 21 13 │ 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 29 28 31 30 25 24 27 26 21 20 14 │ 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 30 31 28 29 26 27 24 25 22 23 15 │ 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 31 30 29 28 27 26 25 24 23 22 16 │ 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 0 1 2 3 4 5 6 7 8 9 17 │ 17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30 1 0 3 2 5 4 7 6 9 8 18 │ 18 19 16 17 22 23 20 21 26 27 24 25 30 31 28 29 2 3 0 1 6 7 4 5 10 11 19 │ 19 18 17 16 23 22 21 20 27 26 25 24 31 30 29 28 3 2 1 0 7 6 5 4 11 10 20 │ 20 21 22 23 16 17 18 19 28 29 30 31 24 25 26 27 4 5 6 7 0 1 2 3 12 13 21 │ 21 20 23 22 17 16 19 18 29 28 31 30 25 24 27 26 5 4 7 6 1 0 3 2 13 12 22 │ 22 23 20 21 18 19 16 17 30 31 28 29 26 27 24 25 6 7 4 5 2 3 0 1 14 15 23 │ 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 7 6 5 4 3 2 1 0 15 14 24 │ 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 8 9 10 11 12 13 14 15 0 1 25 │ 25 24 27 26 29 28 31 30 17 16 19 18 21 20 23 22 9 8 11 10 13 12 15 14 1 0 ⊗ │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ───┼──────────────────────────────────────────────────────────────────────────────────────────────────────── 0 │ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2 │ 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 32 34 35 33 40 42 43 41 44 46 3 │ 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 48 51 49 50 60 63 61 62 52 55 4 │ 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 64 68 72 76 70 66 78 74 75 79 5 │ 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 80 85 90 95 82 87 88 93 83 86 6 │ 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 96 102 107 109 110 104 101 99 103 97 7 │ 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 112 119 121 126 122 125 115 116 127 120 8 │ 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 128 136 140 132 139 131 135 143 141 133 9 │ 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 144 153 158 151 159 150 145 152 149 156 10 │ 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 160 170 175 165 163 169 172 166 161 171 11 │ 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 176 187 189 182 183 188 186 177 185 178 12 │ 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 192 204 196 200 205 193 201 197 198 202 13 │ 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 208 221 214 219 217 212 223 210 222 211 14 │ 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 224 238 231 233 229 235 226 236 234 228 15 │ 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 240 255 245 250 241 254 244 251 242 253 16 │ 0 16 32 48 64 80 96 112 128 144 160 176 192 208 224 240 24 8 56 40 88 72 120 104 152 136 17 │ 0 17 34 51 68 85 102 119 136 153 170 187 204 221 238 255 8 25 42 59 76 93 110 127 128 145 18 │ 0 18 35 49 72 90 107 121 140 158 175 189 196 214 231 245 56 42 27 9 112 98 83 65 180 166 19 │ 0 19 33 50 76 95 109 126 132 151 165 182 200 219 233 250 40 59 9 26 100 119 69 86 172 191 20 │ 0 20 40 60 70 82 110 122 139 159 163 183 205 217 229 241 88 76 112 100 30 10 54 34 211 199 21 │ 0 21 42 63 66 87 104 125 131 150 169 188 193 212 235 254 72 93 98 119 10 31 32 53 203 222 22 │ 0 22 43 61 78 88 101 115 135 145 172 186 201 223 226 244 120 110 83 69 54 32 29 11 255 233 23 │ 0 23 41 62 74 93 99 116 143 152 166 177 197 210 236 251 104 127 65 86 34 53 11 28 231 240 24 │ 0 24 44 52 75 83 103 127 141 149 161 185 198 222 234 242 152 128 180 172 211 203 255 231 21 13 25 │ 0 25 46 55 79 86 97 120 133 156 171 178 202 211 228 253 136 145 166 191 199 222 233 240 13 20 21508 ⊕ 42689 = 62149 21508 ⊗ 42689 = 35202 2150821508215082150821508 ⊕ 4268942689426894268942689 = 2722732241575131661744101 2150821508215082150821508 ⊗ 4268942689426894268942689 = 221974472829844568827862736061997038065
REXX
This REXX version optimizes the nimber product by using the nimber sum for some of its calculations.
The table size (for nimber sum and nimber products) may be specified on the command line (CL) as well as the
two test numbers.
<lang rexx>/*REXX program performs nimber arithmetic (addition and multiplication); shows a table.*/
numeric digits 40 /*use a big enough number of decimals. */
parse arg sz aa bb . /*obtain optional argument from the CL.*/
if sz== | sz=="," then sz= 15 /*Not specified? Then use the default.*/
if aa== | aa=="," then aa= 21508 /* " " " " " " */
if bb== | bb=="," then bb= 42689 /* " " " " " " */
w= max(4,length(sz)); @.= '+'; @.1= "*"; _= '═' /*calculate the width of the table cols*/
sz1= sz + 1; w1= w-1 /*define the "dash" character for table*/
do am=0 for 2 /*perform sums, then perform multiplies*/
do j=0 for sz1 /*calculate & format a row of the table*/
if j==0 then call top '║'center("("@.am')', w1) /*show title of table. */
$= '║'center(j, w1)"║" /*index for a table row.*/
do k=0 for sz1 /*build a row of table. */
if am then $= $ || right( nprod(j, k), w) /*append to a table row.*/
else $= $ || right( nsum(j, k), w) /* " " " " " */
end /*k*/
say $ '║' /*show a row of a table.*/
end /*j*/
call bot
end /*am*/
say 'nimber sum of ' comma(aa) " and " comma(bb) ' ───► ' comma( nsum(aa, bb)) say 'nimber product of ' comma(aa) " and " comma(bb) ' ───► ' comma(nprod(aa, bb)) exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ hdr: $= ?'║'; do i=0 to sz; $=$ || right(i,w); end; say $ "║"; call sep; return top: $= '╔'copies(_, w1)"╦"copies(copies(_, w), sz1)_; say $'╗'; arg ?; call hdr; return sep: $= '╠'copies(_, w1)"╬"copies(copies(_, w), sz1)_; say $'╣'; return bot: $= '╚'copies(_, w1)"╩"copies(copies(_, w), sz1)_; say $'╝'; say; say; return comma: parse arg ?; do jc=length(?)-3 to 1 by -3; ?= insert(',', ?, jc); end; return ? d2b: procedure; parse arg z; return right( x2b( d2x(z) ), digits(), 0) hpo2: procedure; parse arg z; return 2 ** (length( d2b(z) + 0) - 1) lhpo2: procedure; arg z; m=hpo2(z); q=0; do while m//2==0; m= m%2; q= q+1; end; return q nsum: procedure; parse arg x,y; d= digits() % 8; return c2d(bitxor(d2c(x,d), d2c(y,d))) shl: procedure; parse arg z,h; return z * (2**h) shr: procedure; parse arg z,h; return z % (2**h) /*──────────────────────────────────────────────────────────────────────────────────────*/ nprod: procedure; parse arg x,y; if x<2 | y<2 then return x * y; h= hpo2(x)
if x>h then return nsum( nprod(h, y), nprod( nsum(x, h), y) )
if hpo2(y)<y then return nprod(y, x)
d= digits()%8; ands= c2d( bitand( d2c( lhpo2(x), d), d2c(lhpo2(y), d) ) )
if ands==0 then return x * y
h= hpo2(ands); return nprod( nprod( shr(x,h), shr(y,h) ), shl(3, h-1) )</lang>
- output when using the input of: 25
╔═══╦═════════════════════════════════════════════════════════════════════════════════════════════════════════╗ ║(+)║ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ║ ╠═══╬═════════════════════════════════════════════════════════════════════════════════════════════════════════╣ ║ 0 ║ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ║ ║ 1 ║ 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24 ║ ║ 2 ║ 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 18 19 16 17 22 23 20 21 26 27 ║ ║ 3 ║ 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 19 18 17 16 23 22 21 20 27 26 ║ ║ 4 ║ 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 20 21 22 23 16 17 18 19 28 29 ║ ║ 5 ║ 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 21 20 23 22 17 16 19 18 29 28 ║ ║ 6 ║ 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 22 23 20 21 18 19 16 17 30 31 ║ ║ 7 ║ 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 21 20 19 18 17 16 31 30 ║ ║ 8 ║ 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 24 25 26 27 28 29 30 31 16 17 ║ ║ 9 ║ 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 25 24 27 26 29 28 31 30 17 16 ║ ║10 ║ 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 26 27 24 25 30 31 28 29 18 19 ║ ║11 ║ 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 27 26 25 24 31 30 29 28 19 18 ║ ║12 ║ 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 28 29 30 31 24 25 26 27 20 21 ║ ║13 ║ 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 29 28 31 30 25 24 27 26 21 20 ║ ║14 ║ 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 30 31 28 29 26 27 24 25 22 23 ║ ║15 ║ 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 31 30 29 28 27 26 25 24 23 22 ║ ║16 ║ 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 0 1 2 3 4 5 6 7 8 9 ║ ║17 ║ 17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30 1 0 3 2 5 4 7 6 9 8 ║ ║18 ║ 18 19 16 17 22 23 20 21 26 27 24 25 30 31 28 29 2 3 0 1 6 7 4 5 10 11 ║ ║19 ║ 19 18 17 16 23 22 21 20 27 26 25 24 31 30 29 28 3 2 1 0 7 6 5 4 11 10 ║ ║20 ║ 20 21 22 23 16 17 18 19 28 29 30 31 24 25 26 27 4 5 6 7 0 1 2 3 12 13 ║ ║21 ║ 21 20 23 22 17 16 19 18 29 28 31 30 25 24 27 26 5 4 7 6 1 0 3 2 13 12 ║ ║22 ║ 22 23 20 21 18 19 16 17 30 31 28 29 26 27 24 25 6 7 4 5 2 3 0 1 14 15 ║ ║23 ║ 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 7 6 5 4 3 2 1 0 15 14 ║ ║24 ║ 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 8 9 10 11 12 13 14 15 0 1 ║ ║25 ║ 25 24 27 26 29 28 31 30 17 16 19 18 21 20 23 22 9 8 11 10 13 12 15 14 1 0 ║ ╚═══╩═════════════════════════════════════════════════════════════════════════════════════════════════════════╝ ╔═══╦═════════════════════════════════════════════════════════════════════════════════════════════════════════╗ ║(*)║ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ║ ╠═══╬═════════════════════════════════════════════════════════════════════════════════════════════════════════╣ ║ 0 ║ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ║ ║ 1 ║ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ║ ║ 2 ║ 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 32 34 35 33 40 42 43 41 44 46 ║ ║ 3 ║ 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 48 51 49 50 60 63 61 62 52 55 ║ ║ 4 ║ 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 64 68 72 76 70 66 78 74 75 79 ║ ║ 5 ║ 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 80 85 90 95 82 87 88 93 83 86 ║ ║ 6 ║ 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 96 102 107 109 110 104 101 99 103 97 ║ ║ 7 ║ 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 112 119 121 126 122 125 115 116 127 120 ║ ║ 8 ║ 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 128 136 140 132 139 131 135 143 141 133 ║ ║ 9 ║ 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 144 153 158 151 159 150 145 152 149 156 ║ ║10 ║ 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 160 170 175 165 163 169 172 166 161 171 ║ ║11 ║ 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 176 187 189 182 183 188 186 177 185 178 ║ ║12 ║ 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 192 204 196 200 205 193 201 197 198 202 ║ ║13 ║ 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 208 221 214 219 217 212 223 210 222 211 ║ ║14 ║ 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 224 238 231 233 229 235 226 236 234 228 ║ ║15 ║ 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 240 255 245 250 241 254 244 251 242 253 ║ ║16 ║ 0 16 32 48 64 80 96 112 128 144 160 176 192 208 224 240 24 8 56 40 88 72 120 104 152 136 ║ ║17 ║ 0 17 34 51 68 85 102 119 136 153 170 187 204 221 238 255 8 25 42 59 76 93 110 127 128 145 ║ ║18 ║ 0 18 35 49 72 90 107 121 140 158 175 189 196 214 231 245 56 42 27 9 112 98 83 65 180 166 ║ ║19 ║ 0 19 33 50 76 95 109 126 132 151 165 182 200 219 233 250 40 59 9 26 100 119 69 86 172 191 ║ ║20 ║ 0 20 40 60 70 82 110 122 139 159 163 183 205 217 229 241 88 76 112 100 30 10 54 34 211 199 ║ ║21 ║ 0 21 42 63 66 87 104 125 131 150 169 188 193 212 235 254 72 93 98 119 10 31 32 53 203 222 ║ ║22 ║ 0 22 43 61 78 88 101 115 135 145 172 186 201 223 226 244 120 110 83 69 54 32 29 11 255 233 ║ ║23 ║ 0 23 41 62 74 93 99 116 143 152 166 177 197 210 236 251 104 127 65 86 34 53 11 28 231 240 ║ ║24 ║ 0 24 44 52 75 83 103 127 141 149 161 185 198 222 234 242 152 128 180 172 211 203 255 231 21 13 ║ ║25 ║ 0 25 46 55 79 86 97 120 133 156 171 178 202 211 228 253 136 145 166 191 199 222 233 240 13 20 ║ ╚═══╩═════════════════════════════════════════════════════════════════════════════════════════════════════════╝ nimber sum of 21,508 and 42,689 ───► 62,149 nimber product of 21,508 and 42,689 ───► 35,202
Rust
<lang rust>// highest power of 2 that divides a given number fn hpo2(n: u32) -> u32 {
n & (0xFFFFFFFF - n + 1)
}
// base 2 logarithm of the highest power of 2 dividing a given number fn lhpo2(n: u32) -> u32 {
let mut q: u32 = 0;
let mut m: u32 = hpo2(n);
while m % 2 == 0 {
m >>= 1;
q += 1;
}
q
}
// nim-sum of two numbers fn nimsum(x: u32, y: u32) -> u32 {
x ^ y
}
// nim-product of two numbers fn nimprod(x: u32, y: u32) -> u32 {
if x < 2 || y < 2 {
return x * y;
}
let mut h: u32 = hpo2(x);
if x > h {
return nimprod(h, y) ^ nimprod(x ^ h, y);
}
if hpo2(y) < y {
return nimprod(y, x);
}
let xp: u32 = lhpo2(x);
let yp: u32 = lhpo2(y);
let comp: u32 = xp & yp;
if comp == 0 {
return x * y;
}
h = hpo2(comp);
nimprod(nimprod(x >> h, y >> h), 3 << (h - 1))
}
fn print_table(n: u32, op: char, func: fn(u32, u32) -> u32) {
print!(" {} |", op);
for a in 0..=n {
print!("{:3}", a);
}
print!("\n--- -");
for _ in 0..=n {
print!("---");
}
println!();
for b in 0..=n {
print!("{:2} |", b);
for a in 0..=n {
print!("{:3}", func(a, b));
}
println!();
}
}
fn main() {
print_table(15, '+', nimsum);
println!();
print_table(15, '*', nimprod);
let a: u32 = 21508;
let b: u32 = 42689;
println!("\n{} + {} = {}", a, b, nimsum(a, b));
println!("{} * {} = {}", a, b, nimprod(a, b));
}</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202
Swift
<lang swift>import Foundation
// highest power of 2 that divides a given number func hpo2(_ n: Int) -> Int {
n & -n
}
// base 2 logarithm of the highest power of 2 dividing a given number func lhpo2(_ n: Int) -> Int {
var q: Int = 0
var m: Int = hpo2(n)
while m % 2 == 0 {
m >>= 1
q += 1
}
return q
}
// nim-sum of two numbers func nimSum(x: Int, y: Int) -> Int {
x ^ y
}
// nim-product of two numbers func nimProduct(x: Int, y: Int) -> Int {
if x < 2 || y < 2 {
return x * y
}
var h = hpo2(x);
if x > h {
return nimProduct(x: h, y: y) ^ nimProduct(x: x ^ h, y: y)
}
if hpo2(y) < y {
return nimProduct(x: y, y: x)
}
let xp = lhpo2(x)
let yp = lhpo2(y)
let comp = xp & yp
if comp == 0 {
return x * y
}
h = hpo2(comp)
return nimProduct(x: nimProduct(x: x >> h, y: y >> h), y: 3 << (h - 1))
}
func printTable(n: Int, op: Character, function: (Int, Int) -> Int) {
print(" \(op) |", terminator: "")
for a in 0...n {
print(String(format: "%3d", a), terminator: "")
}
print("\n--- -", terminator: "")
for _ in 0...n {
print("---", terminator: "")
}
print()
for b in 0...n {
print("\(String(format: "%2d", b)) |", terminator: "")
for a in 0...n {
print(String(format: "%3d", function(a, b)), terminator: "")
}
print()
}
}
printTable(n: 15, op: "+", function: nimSum) print() printTable(n: 15, op: "*", function: nimProduct) let a: Int = 21508 let b: Int = 42689 print("\n\(a) + \(b) = \(nimSum(x: a, y: b))") print("\(a) * \(b) = \(nimProduct(x: a, y: b))")</lang>
- Output:
+ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --- ------------------------------------------------- 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202
Wren
<lang ecmascript>import "/fmt" for Fmt
// Highest power of two that divides a given number. var hpo2 = Fn.new { |n| n & (-n) }
// Base 2 logarithm of the highest power of 2 dividing a given number. var lhpo2 = Fn.new { |n|
var q = 0
var m = hpo2.call(n)
while (m%2 == 0) {
m = m >> 1
q = q + 1
}
return q
}
// nim-sum of two numbers. var nimsum = Fn.new { |x, y| x ^ y }
// nim-product of two numbers. var nimprod // recursive nimprod = Fn.new { |x, y|
if (x < 2 || y < 2) return x * y
var h = hpo2.call(x)
System.write("") // fixes VM recursion bug
if (x > h) return nimprod.call(h, y) ^ nimprod.call(x ^ h, y) // break x into powers of 2
if (hpo2.call(y) < y) return nimprod.call(y, x) // break y into powers of 2
var xp = lhpo2.call(x)
var yp = lhpo2.call(y)
var comp = xp & yp
if (comp == 0) return x * y // no Fermat power in common
h = hpo2.call(comp)
// a Fermat number square is its sequimultiple
return nimprod.call(nimprod.call(x >> h, y >> h), 3 << (h-1))
}
var fns = [[nimsum, "⊕"], [nimprod, "⊗"]] for (fn in fns) {
System.write(" %(fn[1]) |")
for (i in 0..15) System.write(Fmt.d(3, i))
System.print("\n---+%("-" * 48)")
for (i in 0..15) {
System.write("%(Fmt.d(2, i)) |")
for (j in 0..15) System.write(Fmt.d(3, fn[0].call(i, j)))
System.print()
}
System.print()
} var a = 21508 var b = 42689 System.print("%(a) + %(b) = %(nimsum.call(a, b))") System.print("%(a) * %(b) = %(nimprod.call(a, b))")</lang>
- Output:
⊕ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ---+------------------------------------------------ 0 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 | 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 | 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 | 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 | 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 | 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 | 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 | 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 | 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 | 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 | 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 | 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 | 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 | 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 | 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 | 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 ⊗ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ---+------------------------------------------------ 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 | 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 | 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 | 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 | 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 | 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 | 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 | 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 | 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 | 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 | 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 | 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 | 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 21508 + 42689 = 62149 21508 * 42689 = 35202