Nimber arithmetic: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added Rust solution)
Line 371: Line 371:
21508 + 42689 = 62149
21508 + 42689 = 62149
21508 * 42689 = 35202
21508 * 42689 = 35202
</pre>

=={{header|Phix}}==
{{trans|FreeBASIC}}
<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
integer a, b
string outstr = " + | "
for a = 0 to 15 do
outstr &= sprintf("%2d ",a)
end for
constant hdrfmt = "%s\n--- -------------------------------------------------\n"
printf(1, hdrfmt, outstr)
for b = 0 to 15 do
outstr = sprintf("%2d | ", b)
for a = 0 to 15 do
outstr &= sprintf("%2d ", nimsum(a,b))
end for
printf(1,"%s\n", outstr)
end for
printf(1,"\n")
outstr = " * | "
for a = 0 to 15 do
outstr &= sprintf("%2d ", a)
end for
printf(1, hdrfmt, outstr)
for b = 0 to 15 do
outstr = sprintf("%2d | ", b)
for a = 0 to 15 do
outstr &= sprintf("%2d ", nimprod(a,b))
end for
printf(1,"%s\n", outstr)
end for
printf(1,"\n")
a = 21508
b = 42689
printf(1,"%5d + %5d = %10d\n",{a,b,nimsum(a,b)})
printf(1,"%5d * %5d = %10d\n",{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
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>
</pre>


Revision as of 03:42, 27 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:

  1. Create nimber addition and multiplication tables up to at least 15
  2. Find the nim-sum and nim-product of two five digit integers of your choice

C

Translation of: FreeBASIC

<lang c>#include <stdio.h>

  1. 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

Translation of: FreeBASIC

<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

Phix

Translation of: FreeBASIC

<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

integer a, b string outstr = " + | " for a = 0 to 15 do 

   outstr &= sprintf("%2d ",a)

end for constant hdrfmt = "%s\n--- -------------------------------------------------\n" printf(1, hdrfmt, outstr) for b = 0 to 15 do 

   outstr = sprintf("%2d | ", b)
   for a = 0 to 15 do
       outstr &= sprintf("%2d ", nimsum(a,b))
   end for
   printf(1,"%s\n", outstr)

end for printf(1,"\n") outstr = " * | " for a = 0 to 15 do 

   outstr &= sprintf("%2d ", a)

end for printf(1, hdrfmt, outstr) for b = 0 to 15 do 

   outstr = sprintf("%2d | ", b)
   for a = 0 to 15 do
       outstr &= sprintf("%2d ", nimprod(a,b))
   end for
   printf(1,"%s\n", outstr)

end for printf(1,"\n") a = 21508 b = 42689

printf(1,"%5d + %5d = %10d\n",{a,b,nimsum(a,b)}) printf(1,"%5d * %5d = %10d\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

Translation of: 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>

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

Translation of: FreeBASIC
Library: Wren-fmt

<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
Retrieved from "https://rosettacode.org/wiki/Nimber_arithmetic?oldid=300347"