Golang中小数平方根的任意精度

Question

我正在寻找一种计算任意精度平方根的方法（例如小数点后50位）。

在Python中，可以使用Decimal轻松访问它：

from decimal import *
getcontext().prec = 50
Decimal(2).sqrt() # and here you go my 50 digits

在看到了 math/big 的强大之后，我浏览了一下 文档，但没有找到类似的内容。

那么我的唯一选择是编写某种数值计算方法，尝试迭代计算答案吗？

- Salvador Dali

---

问题很糟糕吗？我不会咬人，也能适当接受批评。 - Salvador Dali

您可以使用以下链接：https://golang.org/pkg/math/big/#Rat.FloatString - user4651282

@Atomic_alarm，问题是在这种情况下，我已经需要知道答案了（因为你的方法只是将有理数转换为字符串）。 - Salvador Dali

Answer 1

这是我自己实现的求平方根的方法。在等待答案时，我决定尝试一下计算平方根的方法。它有很多方法，但最后我找到了一个减法求平方根的pdf链接，我真的很喜欢，因为算法的描述只有几行（与牛顿迭代法相比，我之前没有见过它）。

所以这是我的实现（在go语言中使用bigint不太好）。

func square(n int64, precision int64) string{
    ans_int := strconv.Itoa(int(math.Sqrt(float64(n))))

    limit   := new(big.Int).Exp(big.NewInt(10), big.NewInt(precision + 1), nil)
    a       := big.NewInt(5 * n)
    b       := big.NewInt(5)
    five    := big.NewInt(5)
    ten     := big.NewInt(10)
    hundred := big.NewInt(100)

    for b.Cmp(limit) < 0{
        if a.Cmp(b) < 0{
                a.Mul(a, hundred)
            tmp := new(big.Int).Div(b, ten)
            tmp.Mul(tmp, hundred)
            b.Add(tmp, five)
        } else {
            a.Sub(a, b)
            b.Add(b, ten)
        }
    }
    b.Div(b, hundred)

    ans_dec := b.String()

    return ans_dec[:len(ans_int)] + "." + ans_dec[len(ans_int):]
}

附言：感谢Nick Craig-Wood的精彩评论，使代码更加完善。

使用它，可以发现square(8537341, 50)为：

2921.8728582879851242173838229735693053765773170487

这只与 Python 的最后一位数字有关。

getcontext().prec = 50
print str(Decimal(8537341).sqrt())

2921.8728582879851242173838229735693053765773170488

这个数字有误差，因为最后一位并不是非常精确。

像往常一样，前往 Playground。

附言：如果有人能找到一种本地方法来解决这个问题，我将非常乐意接受并点赞。

- Salvador Dali

---

以下是一些使使用 math/big 更自然的方法。不要写成 b.Cmp(limit) == -1，而应该写成 b.Cmp(limit) < 0，这样你就知道你正在测试什么，即 b < limit。不要写成 a = new(big.Int).Mul(a, hundred)，而应该写成 a.Mul(a, hundred)，这样可以避免创建一些新的大整数。 - Nick Craig-Wood

@NickCraig-Wood 谢谢您的建议。我会测试它们并更新我的答案。 - Salvador Dali

太棒了。在1.5版本中，math/big.Float将消除使用整数作为浮点数的额外步骤，但看起来你仍然需要根据算术函数编写自己的sqrt。 - twotwotwo

Answer 2

提高精度

虽然 Go 可能有解决方案，但由于我不会编写 Go 代码，这里提供一般的解决方案。

例如，如果您选择的语言没有提供处理浮点数精度的解决方案（我曾经遇到过这种情况）：

如果您的语言在小数点后提供了 N 位数字，则在求平方根的情况下，可以将输入值（此处为 2）乘以 10^(2*number_of_extra_digits)。

例如，如果 Go 只给出 1.41 作为答案，但您想要 1.4142，那么您需要求解 2*10^(2*2) = 2*10000 的平方根，然后得到 141.42 作为答案。现在，您需要自己调整小数点的位置。

说明：这背后有一些数学魔法。

如果您想要增加简单除法的精度，只需要将输入乘以 10^number_of_extra_digits。

这个技巧就是通过将输入乘以一个因子来增加精度，因为我们无法对输出进行乘法运算（精度已经丢失）。它之所以有效，是因为大多数语言在小数点后面截断的数字比前面少。

因此，我们只需要将 输出方程式 更改为输入方程式（如果可能）：

对于简单除法：(a/b) * 10 = (a*10)/b

对于平方根：sqrt(a) * 10 = sqrt(a) * sqrt(100) = sqrt(a*100)

降低精度

如果需要，也可以进行类似的调整来降低精度。

例如，如果您正在尝试计算下载进度的百分比并保留两位小数。

假设我们已经下载了 1 个文件中的 3 个，那么 1/3 * 100 将给出 33.33333333。

如果不能控制浮点数的精度，则可以执行 cast_to_an_int(1/3 * 100 * 100) / 100 来返回 33.33。

- jeromej

---

哇，这真的是一种不错的方式来增加精度 +1。我的几个测试显示它基本上是有效的（将尝试证明这一点）。 - Salvador Dali

@SalvadorDali 我在其中加入了一些解释，说明了它的工作原理以及如何继续查找如何为某个给定的操作集添加精度。 - jeromej