Integer roots: Difference between revisions
Content added Content deleted
(Go solution) |
(→{{header|Go}}: add big.Int version, document interesting differences) |
||
Line 10: | Line 10: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
===int=== |
|||
<lang go>package main |
<lang go>package main |
||
Line 21: | Line 22: | ||
func root(N, X int) int { |
func root(N, X int) int { |
||
// adapted from https://en.wikipedia.org/wiki/Nth_root_algorithm |
|||
for r := 1; ; { |
for r := 1; ; { |
||
x := X |
x := X |
||
Line 27: | Line 29: | ||
} |
} |
||
x -= r |
x -= r |
||
// A small complication here is that Go performs truncated integer |
|||
// division but for negative values of x, Δr in the line below needs |
|||
// to be computed as the floor of x / N. The following % test and |
|||
// correction completes the floor division operation (for positive N.) |
|||
Δr := x / N |
Δr := x / N |
||
if x%N < 0 { |
if x%N < 0 { |
||
Line 42: | Line 48: | ||
2 |
2 |
||
1414213562 |
1414213562 |
||
</pre> |
|||
===big.Int=== |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"math/big" |
|||
) |
|||
func main() { |
|||
fmt.Println(root(3, "8")) |
|||
fmt.Println(root(3, "9")) |
|||
fmt.Println(root(2, "2000000000000000000")) |
|||
fmt.Println(root(2, "200000000000000000000000000000000000000000000000000")) |
|||
} |
|||
var one = big.NewInt(1) |
|||
func root(N int, X string) *big.Int { |
|||
var xx, x, Δr big.Int |
|||
xx.SetString(X, 10) |
|||
nn := big.NewInt(int64(N)) |
|||
for r := big.NewInt(1); ; { |
|||
x.Set(&xx) |
|||
for i := 1; i < N; i++ { |
|||
x.Quo(&x, r) |
|||
} |
|||
// big.Quo performs Go-like truncated division and would allow direct |
|||
// translation of the int-based solution, but package big also provides |
|||
// Div which performs Euclidean rather than truncated division. |
|||
// This gives the desired result for negative x so the int-based |
|||
// correction is no longer needed and the code here can more directly |
|||
// follow the Wikipedia article. |
|||
Δr.Div(x.Sub(&x, r), nn) |
|||
if len(Δr.Bits()) == 0 { |
|||
return r |
|||
} |
|||
r.Add(r, &Δr) |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
2 |
|||
2 |
|||
1414213562 |
|||
14142135623730950488016887 |
|||
</pre> |
</pre> |
||