Nimber arithmetic: Difference between revisions
Content deleted Content added
→{{header|REXX}}: added the computer programming language REXX. |
m →{{header|Wren}}: Minor tidy |
||
(14 intermediate revisions by 10 users not shown) | |||
Line 1:
{{Draft task}}
The '''nimbers''', also known as '''Grundy''' numbers, are the values of the heaps in the game of [https://en.wikipedia.org/wiki/Nim Nim]. They have '''addition''' and '''multiplication''' operations, unrelated to the addition and multiplication of the integers. Both operations are defined recursively:
Line 19:
# 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
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F hpo2(n)
R n [&] (-n)
F lhpo2(n)
V q = 0
V m = hpo2(n)
L m % 2 == 0
m = m >> 1
q++
R q
F nimsum(Int x, Int y)
R x (+) y
F nimprod(Int x, Int y)
I x < 2 | y < 2
R x * y
V h = hpo2(x)
I x > h
R nimprod(h, y) (+) nimprod(x (+) h, y)
I hpo2(y) < y
R nimprod(y, x)
V (xp, yp) = (lhpo2(x), lhpo2(y))
V comp = xp [&] yp
I comp == 0
R x * y
h = hpo2(comp)
R nimprod(nimprod(x >> h, y >> h), 3 << (h - 1))
L(f, op) ((nimsum, ‘+’), (nimprod, ‘*’))
print(‘ ’op‘ |’, end' ‘’)
L(i) 16
print(‘#3’.format(i), end' ‘’)
print("\n--- "(‘-’ * 48))
L(i) 16
print(‘#2 |’.format(i), end' ‘’)
L(j) 16
print(‘#3’.format(f(i, j)), end' ‘’)
print()
print()
V (a, b) = (21508, 42689)
print(a‘ + ’b‘ = ’nimsum(a, b))
print(a‘ * ’b‘ = ’nimprod(a, b))</syntaxhighlight>
{{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|C}}==
{{trans|FreeBASIC}}
<
#include <stdint.h>
Line 87 ⟶ 179:
printf("%d * %d = %d\n", a, b, nimprod(a, b));
return 0;
}</
{{out}}
Line 135 ⟶ 227:
=={{header|C++}}==
{{trans|FreeBASIC}}
<
#include <functional>
#include <iomanip>
Line 199 ⟶ 291:
std::cout << a << " * " << b << " = " << nimprod(a, b) << '\n';
return 0;
}</
{{out}}
Line 244 ⟶ 336:
21508 * 42689 = 35202
</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| System.Math}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
program Nimber_arithmetic;
uses
System.SysUtils, System.Math;
Type
TFnop = record
fn: TFunc<Cardinal, Cardinal, Cardinal>;
op: string;
end;
// Highest power of two that divides a given number.
function hpo2(n: Cardinal): Cardinal;
begin
Result := n and (-n)
end;
// Base 2 logarithm of the highest power of 2 dividing a given number.
function lhpo2(n: Cardinal): Cardinal;
var
m: Cardinal;
begin
Result := 0;
m := hpo2(n);
while m mod 2 = 0 do
begin
m := m shr 1;
inc(Result);
end;
end;
// nim-sum of two numbers.
function nimsum(x, y: Cardinal): Cardinal;
begin
Result := x xor y;
end;
function nimprod(x, y: Cardinal): Cardinal;
var
h, xp, yp, comp: Cardinal;
begin
if (x < 2) or (y < 2) then
exit(x * y);
h := hpo2(x);
if x > h then
exit((nimprod(h, y) xor nimprod((x xor h), y)));
if hpo2(y) < y then
exit(nimprod(y, x)); // break y into powers of 2 by flipping operands
xp := lhpo2(x);
yp := lhpo2(y);
comp := xp and yp;
if comp = 0 then
exit(x * y); // no Fermat power in common
h := hpo2(comp);
// a Fermat number square is its sequimultiple
Result := nimprod(nimprod(x shr h, y shr h), 3 shl (h - 1));
end;
var
fnop: array [0 .. 1] of TFnop;
f: TFnop;
i, j, a, b: Cardinal;
begin
with fnop[0] do
begin
fn := nimsum;
op := '+';
end;
with fnop[1] do
begin
fn := nimprod;
op := '*';
end;
for f in fnop do
begin
write(' ', f.op, ' |');
for i := 0 to 15 do
Write(i:3);
Writeln;
Writeln('--- ', string.Create('-', 48));
for i := 0 to 15 do
begin
write(i:2, ' |');
for j := 0 to 15 do
write(f.fn(i, j):3);
Writeln;
end;
Writeln;
end;
a := 21508;
b := 42689;
Writeln(Format('%d + %d = %d', [a, b, nimsum(a, b)]));
Writeln(Format('%d * %d = %d', [a, b, nimprod(a, b)]));
readln;
end.</syntaxhighlight>
=={{header|Factor}}==
{{trans|FreeBASIC}}
{{works with|Factor|0.99 2020-07-03}}
<
! highest power of 2 that divides a given number
Line 293 ⟶ 504:
33333 77777
[ 2dup nim-sum "%d + %d = %d\n" printf ]
[ 2dup nim-prod "%d * %d = %d\n" printf ] 2bi</
{{out}}
<pre>
Line 339 ⟶ 550:
=={{header|FreeBASIC}}==
<
'highest power of 2 that divides a given number
return n and -n
Line 413 ⟶ 624:
print using "##### + ##### = ##########"; a; b; nimsum(a,b)
print using "##### * ##### = ##########"; a; b; nimprod(a,b)</
{{out}}
<pre>
Line 460 ⟶ 671:
=={{header|Go}}==
{{trans|FreeBASIC}}
<
import (
Line 532 ⟶ 743:
fmt.Printf("%d + %d = %d\n", a, b, nimsum(a, b))
fmt.Printf("%d * %d = %d\n", a, b, nimprod(a, b))
}</
{{out}}
Line 577 ⟶ 788:
21508 * 42689 = 35202
</pre>
=={{header|J}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="j">nadd=: 22 b. NB. bitwise exclusive or on integers
and=: 17 b. NB. bitwise exclusive or on integers
nmul=: {{
if. x +.&(2&>) y do.
x*y
elseif. 1 < #_ q: x do.
h=. (and-) x
(h nmul y) nadd y nmul h nadd x
elseif. 1 < #_ q: y do.
y nmul x
else.
comp=. x and&(0 { 1 q: ]) y
if. 0=comp do.
x*y
else.
p=. 2^(and-) comp
(3*p%2) nmul x nmul&(%&p) y
end.
end.
}}M."0</syntaxhighlight>
Task examples:
<syntaxhighlight lang="j"> nadd table _4+i.20
┌────┬───────────────────────────────────────────────────────────────────────┐
│nadd│ _4 _3 _2 _1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15│
├────┼───────────────────────────────────────────────────────────────────────┤
│_4 │ 0 1 2 3 _4 _3 _2 _1 _8 _7 _6 _5 _12 _11 _10 _9 _16 _15 _14 _13│
│_3 │ 1 0 3 2 _3 _4 _1 _2 _7 _8 _5 _6 _11 _12 _9 _10 _15 _16 _13 _14│
│_2 │ 2 3 0 1 _2 _1 _4 _3 _6 _5 _8 _7 _10 _9 _12 _11 _14 _13 _16 _15│
│_1 │ 3 2 1 0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _10 _11 _12 _13 _14 _15 _16│
│ 0 │ _4 _3 _2 _1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15│
│ 1 │ _3 _4 _1 _2 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14│
│ 2 │ _2 _1 _4 _3 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13│
│ 3 │ _1 _2 _3 _4 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12│
│ 4 │ _8 _7 _6 _5 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11│
│ 5 │ _7 _8 _5 _6 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10│
│ 6 │ _6 _5 _8 _7 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9│
│ 7 │ _5 _6 _7 _8 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8│
│ 8 │_12 _11 _10 _9 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7│
│ 9 │_11 _12 _9 _10 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6│
│10 │_10 _9 _12 _11 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5│
│11 │ _9 _10 _11 _12 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4│
│12 │_16 _15 _14 _13 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3│
│13 │_15 _16 _13 _14 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2│
│14 │_14 _13 _16 _15 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1│
│15 │_13 _14 _15 _16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0│
└────┴───────────────────────────────────────────────────────────────────────┘
nmul table _4+i.20
┌────┬───────────────────────────────────────────────────────────────────────────┐
│nmul│ _4 _3 _2 _1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15│
├────┼───────────────────────────────────────────────────────────────────────────┤
│_4 │ 16 12 8 4 0 _4 _8 _12 _16 _20 _24 _28 _32 _36 _40 _44 _48 _52 _56 _60│
│_3 │ 12 9 6 3 0 _3 _6 _9 _12 _15 _18 _21 _24 _27 _30 _33 _36 _39 _42 _45│
│_2 │ 8 6 4 2 0 _2 _4 _6 _8 _10 _12 _14 _16 _18 _20 _22 _24 _26 _28 _30│
│_1 │ 4 3 2 1 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│
│ 1 │ _4 _3 _2 _1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15│
│ 2 │ _8 _6 _4 _2 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5│
│ 3 │_12 _9 _6 _3 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10│
│ 4 │_16 _12 _8 _4 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1│
│ 5 │_20 _15 _10 _5 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14│
│ 6 │_24 _18 _12 _6 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4│
│ 7 │_28 _21 _14 _7 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11│
│ 8 │_32 _24 _16 _8 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2│
│ 9 │_36 _27 _18 _9 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13│
│10 │_40 _30 _20 _10 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7│
│11 │_44 _33 _22 _11 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8│
│12 │_48 _36 _24 _12 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3│
│13 │_52 _39 _26 _13 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12│
│14 │_56 _42 _28 _14 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6│
│15 │_60 _45 _30 _15 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9│
└────┴───────────────────────────────────────────────────────────────────────────┘
12345 nadd 67890
80139
12345 nmul 67890
809054384</syntaxhighlight>
=={{header|Java}}==
{{trans|FreeBASIC}}
<
public class Nimber {
Line 631 ⟶ 924:
System.out.print(" " + op + " |");
for (int a = 0; a <= n; ++a)
System.out.
System.out.print("\n--- -");
for (int a = 0; a <= n; ++a)
Line 637 ⟶ 930:
System.out.println();
for (int b = 0; b <= n; ++b) {
System.out.
for (int a = 0; a <= n; ++a)
System.out.
System.out.println();
}
}
}</
{{out}}
Line 691 ⟶ 984:
=={{header|Julia}}==
{{trans|FreeBASIC}}
<
hpo2(n) = n & -n
Line 731 ⟶ 1,024:
println("nim-sum: $a ⊕ $b = $(nimsum(a, b))")
println("nim-product: $a ⊗ $b = $(nimprod(a, b))")
</
<pre>
⊕ | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Line 774 ⟶ 1,067:
nim-product: 21508 ⊗ 42689 = 35202
</pre>
=={{header|Nim}}==
{{trans|FreeBASIC}}
<syntaxhighlight 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))</syntaxhighlight>
{{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}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 826 ⟶ 1,216:
say nim_prod(21508, 42689);
say nim_sum(2150821508215082150821508, 4268942689426894268942689);
say nim_prod(2150821508215082150821508, 4268942689426894268942689); # pretty slow</
{{out}}
<pre> + │ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Line 873 ⟶ 1,263:
=={{header|Phix}}==
{{trans|FreeBASIC}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">hpo2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- highest power of 2 that divides a given number</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">lhpo2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- base 2 logarithm of the highest power of 2 dividing a given number</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">hpo2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">q</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">q</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">nimsum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- nim-sum of two numbers</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">xor_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">nimprod</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- nim-product of two numbers</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">2</span> <span style="color: #008080;">or</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">*</span><span style="color: #000000;">y</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">hpo2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">h</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">xor_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nimprod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">),</span><span style="color: #000000;">nimprod</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">xor_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- recursively break x into its powers of 2</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">hpo2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">y</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">nimprod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- recursively break y into its powers of 2 by flipping the operands</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- now both x and y are powers of two</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">xp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lhpo2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">yp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lhpo2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">comp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yp</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">comp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">*</span><span style="color: #000000;">y</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- we have no fermat power in common</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">hpo2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">comp</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">nimprod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nimprod</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">/</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)),</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">/</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">))),</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- a fermat number square is its sequimultiple</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">print_table</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- print a table of nim-sums or nim-products</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %c | "</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"---+%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d |"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d"</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'+'</span> <span style="color: #0000FF;">?</span> <span style="color: #000000;">nimsum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">:</span> <span style="color: #000000;">nimprod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">print_table</span><span style="color: #0000FF;">(</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">'+'</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">print_table</span><span style="color: #0000FF;">(</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">'*'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">21508</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">42689</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%5d + %5d = %5d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nimsum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%5d * %5d = %5d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nimprod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 995 ⟶ 1,388:
{{trans|FreeBASIC}}
{{works with|SWI Prolog}}
<
hpo2(N, P):-
P is N /\ -N.
Line 1,072 ⟶ 1,465:
nimprod(A, B, Product),
writef('%w + %w = %w\n', [A, B, Sum]),
writef('%w * %w = %w\n', [A, B, Product]).</
{{out}}
Line 1,113 ⟶ 1,506:
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|Python}}==
{{trans|Go}}
<syntaxhighlight lang="python"># Highest power of two that divides a given number.
def hpo2(n): return n & (-n)
# Base 2 logarithm of the highest power of 2 dividing a given number.
def lhpo2(n):
q = 0
m = hpo2(n)
while m%2 == 0:
m = m >> 1
q += 1
return q
def nimsum(x,y): return x ^ y
def nimprod(x,y):
if x < 2 or 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))
if __name__ == '__main__':
for f, op in ((nimsum, '+'), (nimprod, '*')):
print(f" {op} |", end='')
for i in range(16):
print(f"{i:3d}", end='')
print("\n--- " + "-"*48)
for i in range(16):
print(f"{i:2d} |", end='')
for j in range(16):
print(f"{f(i,j):3d}", end='')
print()
print()
a, b = 21508, 42689
print(f"{a} + {b} = {nimsum(a,b)}")
print(f"{a} * {b} = {nimprod(a,b)}")</syntaxhighlight>
{{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
Line 1,120 ⟶ 1,605:
=={{header|Quackery}}==
{{trans|Julia}} (Mostly translated from Julia, although 'translated' doesn't do the process justice.)
<syntaxhighlight lang="quackery">
[ dup negate & ] is hpo2 ( n --> n )
Line 1,184 ⟶ 1,669:
say " 10547 (+) 14447 = " 10547 14447 nim+ echo cr
say " 10547 (*) 14447 = " 10547 14447 nim* echo cr
</syntaxhighlight>
{{Out}}
<pre>
Line 1,237 ⟶ 1,722:
Not limited by integer size. Doesn't rely on twos complement bitwise and.
<syntaxhighlight lang="raku"
sub infix:<⊗> (Int $x, Int $y) {
Line 1,266 ⟶ 1,751:
put "2150821508215082150821508 ⊕ 4268942689426894268942689 = ", 2150821508215082150821508 ⊕ 4268942689426894268942689;
put "2150821508215082150821508 ⊗ 4268942689426894268942689 = ", 2150821508215082150821508 ⊗ 4268942689426894268942689;</
{{out}}
<pre> ⊕ │ 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
Line 1,338 ⟶ 1,823:
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 <u>c</u>ommand <u>l</u>ine ('''CL''') as well as the
<br>two test numbers.
<syntaxhighlight lang="rexx">/*REXX program performs nimber arithmetic (addition and multiplication); shows a table.*/
numeric digits 40; d= digits() % 8 /*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,
call top ! || center("("@.am')',
do k=0 for sz1
say $ !
end
call bot
end
say 'nimber sum of ' comma(aa) " and " comma(bb) ' ───► ' comma( nsum(aa, bb))
Line 1,364 ⟶ 1,850:
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
hdr: $= ?
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 expose d; parse arg x,y; return c2d( bitxor( d2c(x,
shl: procedure; parse arg z,h;
shr: procedure; parse arg z,h;
/*──────────────────────────────────────────────────────────────────────────────────────*/
nprod: procedure expose d; parse arg x,y;
if x>h then return nsum( nprod(h, y), nprod( nsum(x, h), y) )
if hpo2(y)<y then return nprod(y, x)
ands= c2d(
{{out|output|text= when using the input of: <tt> 25 </tt>}}
<pre>
╔═══╦═════════════════════════════════════════════════════════════════════════════════════════════════════════╗
║(+)
╠═══╬═════════════════════════════════════════════════════════════════════════════════════════════════════════╣
║ 0
║ 1
║ 2
║ 3
║ 4
║ 5
║ 6
║ 7
║ 8
║ 9
╚═══╩═════════════════════════════════════════════════════════════════════════════════════════════════════════╝
╔═══╦═════════════════════════════════════════════════════════════════════════════════════════════════════════╗
║(*)
╠═══╬═════════════════════════════════════════════════════════════════════════════════════════════════════════╣
║ 0
║ 1
║ 2
║ 3
║ 4
║ 5
║ 6
║ 7
║ 8
║ 9
╚═══╩═════════════════════════════════════════════════════════════════════════════════════════════════════════╝
Line 1,454 ⟶ 1,939:
=={{header|Rust}}==
{{trans|FreeBASIC}}
<
fn hpo2(n: u32) -> u32 {
n & (0xFFFFFFFF - n + 1)
Line 1,524 ⟶ 2,009:
println!("\n{} + {} = {}", a, b, nimsum(a, b));
println!("{} * {} = {}", a, b, nimprod(a, b));
}</
{{out}}
Line 1,572 ⟶ 2,057:
=={{header|Swift}}==
{{trans|Rust}}
<
// highest power of 2 that divides a given number
Line 1,642 ⟶ 2,127:
let b: Int = 42689
print("\n\(a) + \(b) = \(nimSum(x: a, y: b))")
print("\(a) * \(b) = \(nimProduct(x: a, y: b))")</
{{out}}
Line 1,691 ⟶ 2,176:
{{trans|FreeBASIC}}
{{libheader|Wren-fmt}}
<
// Highest power of two that divides a given number.
Line 1,742 ⟶ 2,227:
var b = 42689
System.print("%(a) + %(b) = %(nimsum.call(a, b))")
System.print("%(a) * %(b) = %(nimprod.call(a, b))")</
{{out}}
Line 1,786 ⟶ 2,271:
21508 + 42689 = 62149
21508 * 42689 = 35202
</pre>
=={{header|XPL0}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang "XPL0">include xpllib; \for Print
function HPo2(N); \Highest power of 2 that divides a given number
integer N;
return N and -N;
function LHPo2(N);
\Base 2 logarithm of the highest power of 2 dividing a given number
integer N, Q, M;
[Q:= 0; M:= HPo2(N);
while (M and 1) = 0 do
[M:= M >> 1;
Q:= Q+1;
];
return Q;
];
function NimSum(X, Y); \Nim-sum of two numbers
integer X, Y;
return X xor Y;
function NimProd(X, Y); \Nim-product of two numbers
integer X, Y, H, XP, YP, Comp;
[if X < 2 or Y < 2 then return X*Y;
H:= HPo2(X);
\Recursively break X into its powers of 2
if X > H then return NimProd(H, Y) xor NimProd(X xor H, Y);
\Recursively break Y into its powers of 2 by flipping its operands
if HPo2(Y) < Y then return NimProd(Y, X);
\Now both X and Y are powers of two
XP:= LHPo2(X); YP:= LHPo2(Y); Comp:= XP and YP;
if Comp = 0 then return X*Y; \there is 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));
];
integer A, B;
[Format(3, 0);
Print(" + |");
for A:= 0 to 15 do RlOut(0, float(A));
Print("\n --- -------------------------------------------------\n");
for B:= 0 to 15 do
[RlOut(0, float(B));
Print(" |");
for A:= 0 to 15 do
RlOut(0, float(NimSum(A,B)));
Print("\n");
];
Print("\n * |");
for A:= 0 to 15 do RlOut(0, float(A));
Print("\n --- -------------------------------------------------\n");
for B:= 0 to 15 do
[RlOut(0, float(B));
Print(" |");
for A:= 0 to 15 do
RlOut(0, float(NimProd(A,B)));
Print("\n");
];
A:= 21508;
B:= 42689;
Print("\n%5d + %5d = %10d\n", A, B, NimSum(A,B));
Print("%5d + %5d = %10d\n", A, B, NimProd(A,B));
]</syntaxhighlight>
{{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>
|