Nimber arithmetic: Difference between revisions
Content added Content deleted
m (Minor edit to Java code) |
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
||
| Line 970: | Line 970: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
-- highest power of 2 that divides a given number |
|||
<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> |
|||
return and_bits(n,-n) |
|||
<span style="color: #000080;font-style:italic;">-- highest power of 2 that divides a given number</span> |
|||
end function |
|||
<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> |
|||
function lhpo2(integer n) |
|||
-- base 2 logarithm of the highest power of 2 dividing a given number |
|||
<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> |
|||
integer q = 0, m = hpo2(n) |
|||
<span style="color: #000080;font-style:italic;">-- base 2 logarithm of the highest power of 2 dividing a given number</span> |
|||
while remainder(m,2)=0 do |
|||
<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> |
|||
m = floor(m/2) |
|||
<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> |
|||
q += 1 |
|||
<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> |
|||
end while |
|||
<span style="color: #000000;">q</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
return q |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">q</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function nimsum(integer x, y) |
|||
-- nim-sum of two numbers |
|||
<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> |
|||
return xor_bits(x,y) |
|||
<span style="color: #000080;font-style:italic;">-- nim-sum of two numbers</span> |
|||
end function |
|||
<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> |
|||
function nimprod(integer x, y) |
|||
-- nim-product of two numbers |
|||
<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> |
|||
if x < 2 or y < 2 then return x*y end if |
|||
<span style="color: #000080;font-style:italic;">-- nim-product of two numbers</span> |
|||
integer h = hpo2(x) |
|||
<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> |
|||
if x > h then |
|||
<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> |
|||
return xor_bits(nimprod(h, y),nimprod(xor_bits(x,h), y)) -- recursively break x into its powers of 2 |
|||
<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> |
|||
elsif hpo2(y) < y then |
|||
<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> |
|||
return nimprod(y, x) -- recursively break y into its powers of 2 by flipping the operands |
|||
<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> |
|||
end if |
|||
<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> |
|||
-- now both x and y are powers of two |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
integer xp = lhpo2(x), yp = lhpo2(y), comp = and_bits(xp,yp) |
|||
<span style="color: #000080;font-style:italic;">-- now both x and y are powers of two</span> |
|||
if comp = 0 then return x*y end if -- we have no fermat power in common |
|||
<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> |
|||
h = hpo2(comp) |
|||
<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> |
|||
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 |
|||
<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> |
|||
end function |
|||
<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> |
|||
procedure print_table(integer n, op) |
|||
-- print a table of nim-sums or nim-products |
|||
<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> |
|||
printf(1," %c | "&join(repeat("%3d",n+1))&"\n",op&tagset(n,0)) |
|||
<span style="color: #000080;font-style:italic;">-- print a table of nim-sums or nim-products</span> |
|||
printf(1,"---+%s\n",repeat('-',(n+1)*4)) |
|||
<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> |
|||
for j=0 to n do |
|||
<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> |
|||
printf(1,"%2d |",j) |
|||
<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> |
|||
for i=0 to n do |
|||
<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> |
|||
printf(1,"%4d",iff(op='+' ? nimsum(i, j) : nimprod(i, j))) |
|||
<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> |
|||
end for |
|||
<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> |
|||
printf(1,"\n") |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<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> |
|||
printf(1,"\n") |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end procedure |
|||
<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> |
|||
print_table(25, '+') |
|||
print_table(25, '*') |
|||
<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> |
|||
constant a = 21508, b = 42689 |
|||
<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> |
|||
printf(1,"%5d + %5d = %5d\n",{a,b,nimsum(a,b)}) |
|||
<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> |
|||
printf(1,"%5d * %5d = %5d\n",{a,b,nimprod(a,b)})</lang> |
|||
<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> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||