Nimber arithmetic: Difference between revisions
m Removed unnecessary braces |
Added Rust solution |
||
Line 352: | Line 352: | ||
* | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
* | 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|Rust}}== |
|||
{{trans|FreeBASIC}} |
|||
<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> |
|||
{{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 |
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 |
1 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Revision as of 16:24, 26 May 2020
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
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