Nimber arithmetic: Difference between revisions
Content added Content deleted
(Added Wren) |
(Added Go) |
||
Line 142: | Line 142: | ||
21508 + 42689 = 62149 |
21508 + 42689 = 62149 |
||
21508 * 42689 = 35202 |
21508 * 42689 = 35202 |
||
</pre> |
|||
=={{header|Go}}== |
|||
{{trans|FreeBASIC}} |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"strings" |
|||
) |
|||
// Highest power of two that divides a given number. |
|||
func hpo2(n uint) uint { return n & (-n) } |
|||
// Base 2 logarithm of the highest power of 2 dividing a given number. |
|||
func lhpo2(n uint) uint { |
|||
q := uint(0) |
|||
m := hpo2(n) |
|||
for m%2 == 0 { |
|||
m = m >> 1 |
|||
q++ |
|||
} |
|||
return q |
|||
} |
|||
// nim-sum of two numbers. |
|||
func nimsum(x, y uint) uint { return x ^ y } |
|||
// nim-product of two numbers. |
|||
func nimprod(x, y uint) uint { |
|||
if x < 2 || 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)) |
|||
} |
|||
type fnop struct { |
|||
fn func(x, y uint) uint |
|||
op string |
|||
} |
|||
func main() { |
|||
for _, f := range []fnop{{nimsum, "+"}, {nimprod, "*"}} { |
|||
fmt.Printf(" %s |", f.op) |
|||
for i := 0; i <= 15; i++ { |
|||
fmt.Printf("%3d", i) |
|||
} |
|||
fmt.Println("\n--- " + strings.Repeat("-", 48)) |
|||
for i := uint(0); i <= 15; i++ { |
|||
fmt.Printf("%2d |", i) |
|||
for j := uint(0); j <= 15; j++ { |
|||
fmt.Printf("%3d", f.fn(i, j)) |
|||
} |
|||
fmt.Println() |
|||
} |
|||
fmt.Println() |
|||
} |
|||
a := uint(21508) |
|||
b := uint(42689) |
|||
fmt.Printf("%d + %d = %d\n", a, b, nimsum(a, b)) |
|||
fmt.Printf("%d * %d = %d\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> |
</pre> |
||