Nimber arithmetic: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: factored out print_table(), as per Julia) |
m (→{{header|Phix}}: %5d) |
||
| Line 515: | Line 515: | ||
print_table(15, '*') |
print_table(15, '*') |
||
constant a = 21508, b = 42689 |
constant a = 21508, b = 42689 |
||
printf(1,"%5d + %5d = % |
printf(1,"%5d + %5d = %5d\n",{a,b,nimsum(a,b)}) |
||
printf(1,"%5d * %5d = % |
printf(1,"%5d * %5d = %5d\n",{a,b,nimprod(a,b)})</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
| Line 557: | Line 557: | ||
15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 |
15 | 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9 |
||
21508 + 42689 = |
21508 + 42689 = 62149 |
||
21508 * 42689 = |
21508 * 42689 = 35202 |
||
</pre> |
</pre> |
||
Revision as of 13:55, 28 May 2020
Nimber arithmetic is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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
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
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
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("%2d",n+1))&"\n",op&tagset(n,0))
printf(1,"--- -%s\n",repeat('-',(n+1)*3))
for j=0 to n do
printf(1,"%2d |",j)
for i=0 to n do
printf(1,"%3d",iff(op='+' ? nimsum(i, j) : nimprod(i, j)))
end for
printf(1,"\n")
end for
printf(1,"\n")
end procedure
print_table(15, '+') print_table(15, '*') 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 --- ------------------------------------------------- 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
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
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