Nimber arithmetic: Difference between revisions
→{{header|Phix}}
(Added Rust solution) |
|||
Line 371:
21508 + 42689 = 62149
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>
| |||