Nimber arithmetic: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Alextretyak (talk | contribs) (Added 11l) |
m (→{{header|Wren}}: Minor tidy) |
||
| (5 intermediate revisions by 4 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 27:
{{trans|Python}}
<
R n [&] (-n)
Line 70:
V (a, b) = (21508, 42689)
print(a‘ + ’b‘ = ’nimsum(a, b))
print(a‘ * ’b‘ = ’nimprod(a, b))</
{{out}}
Line 118:
=={{header|C}}==
{{trans|FreeBASIC}}
<
#include <stdint.h>
Line 179:
printf("%d * %d = %d\n", a, b, nimprod(a, b));
return 0;
}</
{{out}}
Line 227:
=={{header|C++}}==
{{trans|FreeBASIC}}
<
#include <functional>
#include <iomanip>
Line 291:
std::cout << a << " * " << b << " = " << nimprod(a, b) << '\n';
return 0;
}</
{{out}}
Line 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 385 ⟶ 504:
33333 77777
[ 2dup nim-sum "%d + %d = %d\n" printf ]
[ 2dup nim-prod "%d * %d = %d\n" printf ] 2bi</
{{out}}
<pre>
Line 431 ⟶ 550:
=={{header|FreeBASIC}}==
<
'highest power of 2 that divides a given number
return n and -n
Line 505 ⟶ 624:
print using "##### + ##### = ##########"; a; b; nimsum(a,b)
print using "##### * ##### = ##########"; a; b; nimprod(a,b)</
{{out}}
<pre>
Line 552 ⟶ 671:
=={{header|Go}}==
{{trans|FreeBASIC}}
<
import (
Line 624 ⟶ 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 669 ⟶ 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 735 ⟶ 936:
}
}
}</
{{out}}
Line 783 ⟶ 984:
=={{header|Julia}}==
{{trans|FreeBASIC}}
<
hpo2(n) = n & -n
Line 823 ⟶ 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 869 ⟶ 1,070:
=={{header|Nim}}==
{{trans|FreeBASIC}}
<
type Nimber = Natural
Line 920 ⟶ 1,121:
const B = 42689
echo "$1 ⊕ $2 = $3".format(A, B, ⊕(A, B))
echo "$1 ⊗ $2 = $3".format(A, B, ⊗(A, B))</
{{out}}
Line 966 ⟶ 1,167:
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 1,015 ⟶ 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 1,062 ⟶ 1,263:
=={{header|Phix}}==
{{trans|FreeBASIC}}
<!--<
<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>
Line 1,119 ⟶ 1,320:
<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>
<!--</
{{out}}
<pre>
Line 1,187 ⟶ 1,388:
{{trans|FreeBASIC}}
{{works with|SWI Prolog}}
<
hpo2(N, P):-
P is N /\ -N.
Line 1,264 ⟶ 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,312 ⟶ 1,513:
=={{header|Python}}==
{{trans|Go}}
<
def hpo2(n): return n & (-n)
Line 1,357 ⟶ 1,558:
a, b = 21508, 42689
print(f"{a} + {b} = {nimsum(a,b)}")
print(f"{a} * {b} = {nimprod(a,b)}")</
{{out}}
<pre>
Line 1,404 ⟶ 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,468 ⟶ 1,669:
say " 10547 (+) 14447 = " 10547 14447 nim+ echo cr
say " 10547 (*) 14447 = " 10547 14447 nim* echo cr
</syntaxhighlight>
{{Out}}
<pre>
Line 1,521 ⟶ 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,550 ⟶ 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,625 ⟶ 1,826:
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.
<
numeric digits 40; d= digits() % 8 /*use a big enough number of decimals. */
parse arg sz aa bb . /*obtain optional argument from the CL.*/
Line 1,665 ⟶ 1,866:
if hpo2(y)<y then return nprod(y, x)
ands= c2d(bitand(d2c(lhpo2(x), d), d2c(lhpo2(y), d))); if ands==0 then return x*y
h= hpo2(ands); return nprod( nprod( shr(x,h), shr(y,h) ), shl(3, h-1) )</
{{out|output|text= when using the input of: <tt> 25 </tt>}}
<pre>
Line 1,738 ⟶ 1,939:
=={{header|Rust}}==
{{trans|FreeBASIC}}
<
fn hpo2(n: u32) -> u32 {
n & (0xFFFFFFFF - n + 1)
Line 1,808 ⟶ 2,009:
println!("\n{} + {} = {}", a, b, nimsum(a, b));
println!("{} * {} = {}", a, b, nimprod(a, b));
}</
{{out}}
Line 1,856 ⟶ 2,057:
=={{header|Swift}}==
{{trans|Rust}}
<
// highest power of 2 that divides a given number
Line 1,926 ⟶ 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,975 ⟶ 2,176:
{{trans|FreeBASIC}}
{{libheader|Wren-fmt}}
<
// Highest power of two that divides a given number.
Line 2,026 ⟶ 2,227:
var b = 42689
System.print("%(a) + %(b) = %(nimsum.call(a, b))")
System.print("%(a) * %(b) = %(nimprod.call(a, b))")</
{{out}}
Line 2,070 ⟶ 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>
| |||