Nimber arithmetic: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: %5d) |
(Added Prolog Solution) |
||
Line 556: | Line 556: | ||
14 | 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 |
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 |
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|Prolog}}== |
|||
{{trans|FreeBASIC}} |
|||
{{works with|SWI Prolog}} |
|||
<lang prolog>% highest power of 2 that divides a given number |
|||
hpo2(N, P):- |
|||
P is N /\ -N. |
|||
% base 2 logarithm of the highest power of 2 dividing a given number |
|||
lhpo2(N, Q):- |
|||
hpo2(N, M), |
|||
lhpo2_(M, 0, Q). |
|||
lhpo2_(M, Q, Q):- |
|||
1 is M mod 2, |
|||
!. |
|||
lhpo2_(M, Q1, Q):- |
|||
M1 is M >> 1, |
|||
Q2 is Q1 + 1, |
|||
lhpo2_(M1, Q2, Q). |
|||
% nim-sum of two numbers |
|||
nimsum(X, Y, Sum):- |
|||
Sum is X xor Y. |
|||
% nim-product of twp numbers |
|||
nimprod(X, Y, Product):- |
|||
(X < 2 ; Y < 2), |
|||
!, |
|||
Product is X * Y. |
|||
nimprod(X, Y, Product):- |
|||
hpo2(X, H), |
|||
X > H, |
|||
!, |
|||
nimprod(H, Y, P1), |
|||
X1 is X xor H, |
|||
nimprod(X1, Y, P2), |
|||
Product is P1 xor P2. |
|||
nimprod(X, Y, Product):- |
|||
hpo2(Y, H), |
|||
H < Y, |
|||
!, |
|||
nimprod(Y, X, Product). |
|||
nimprod(X, Y, Product):- |
|||
lhpo2(X, Xp), |
|||
lhpo2(Y, Yp), |
|||
Comp is Xp /\ Yp, |
|||
(Comp == 0 -> |
|||
Product is X * Y |
|||
; |
|||
hpo2(Comp, H), |
|||
X1 is X >> H, |
|||
Y1 is Y >> H, |
|||
Z is 3 << (H - 1), |
|||
nimprod(X1, Y1, P), |
|||
nimprod(P, Z, Product) |
|||
). |
|||
print_row(N, B, Function):- |
|||
writef('%3r |', [B]), |
|||
Goal =.. [Function, A, B, C], |
|||
forall(between(0, N, A), (call(Goal), writef('%3r', [C]))), |
|||
nl. |
|||
print_table(N, Operator, Function):- |
|||
writef(' %w |', [Operator]), |
|||
forall(between(0, N, A), writef('%3r', [A])), |
|||
writef('\n --- -', []), |
|||
forall(between(0, N, _), writef('---', [])), |
|||
nl, |
|||
forall(between(0, N, A), print_row(N, A, Function)). |
|||
main:- |
|||
print_table(15, '+', nimsum), |
|||
nl, |
|||
print_table(15, '*', nimprod), |
|||
nl, |
|||
A = 21508, B = 42689, |
|||
nimsum(A, B, Sum), |
|||
nimprod(A, B, Product), |
|||
writef('%w + %w = %w\n', [A, B, Sum]), |
|||
writef('%w * %w = %w\n', [A, B, Product]).</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 = 62149 |