在Go语言中对小数进行任意精度的平方根计算

huangapple go评论92阅读模式
英文:

Arbitrary precision for decimals square roots in golang

问题

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

在Python中,可以很容易地使用Decimal来实现:

from decimal import *
getcontext().prec = 50
Decimal(2).sqrt() # 这样就可以得到50位的平方根了

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

所以,我唯一的选择是编写一种数值计算方法,通过迭代尝试计算答案吗?

英文:

I am looking for a way to calculate a square root with an arbitrary precision (something like 50 digits after the dot).

In python, it is easily accessible with Decimal:

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

After seeing the power of math/big I skimmed through the documentation but have not found anything similar.

So is my only option is to write some sort of numerical computing method which will iteratively try to compute the answer?

答案1

得分: 6

这是我自己实现的平方根计算方法。在等待答案的时候,我决定尝试一下计算平方根的方法。它有很多方法,但最后我找到了一个通过减法计算平方根的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):]
}

P.S. 感谢Nick Craig-Wood通过他惊人的评论使代码更好。

使用这个函数,可以找到 square(8537341, 50) 的结果是:

2921.8728582879851242173838229735693053765773170487

与Python的结果相差仅一位数字:

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

> 2921.8728582879851242173838229735693053765773170488

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

如常地,Go Playground

P.S. 如果有人找到一种原生的方法来做到这一点,我将非常乐意接受并点赞。

英文:

This is my own implementation of square root calculation. While waiting for answers, I decided to give methods of computing square roots a try. It has a whole bunch of methods but at the very end I found a link to a Square roots by subtraction pdf, which I really liked because the description of the algorithm is only a couple of lines (and I have not seen it before in comparison to Newton's method).

So here is my implementation (bigint is not really nice to work with in go):

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) &lt; 0{
		if a.Cmp(b) &lt; 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)] + &quot;.&quot; + ans_dec[len(ans_int):]
}

P.S. thank you Nick Craig-Wood for making the code better with your amazing comment.

And using it, one can find that square(8537341, 50) is:

> 2921.8728582879851242173838229735693053765773170487

which is only by one last digit of from python's

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

> 2921.8728582879851242173838229735693053765773170488

This one digit is off because the last digit is not really precise.

As always <kbd>Go Playground</kbd>.

P.S. if someone would find a native way to do this, I would gladly give my accept and upvote.

答案2

得分: 3

增加精度

如果你选择的语言没有提供处理浮点数精度的解决方案(我之前遇到过这种情况),可能在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)

减少精度

如果需要的话,也可以进行类似的调整来减少精度。

例如,如果你想要计算下载进度的百分比,保留两位小数。

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

如果没有办法控制这个浮点数的精度,那么你可以使用 cast_to_an_int(1/3 * 100 * 100) / 100 来返回 33.33

英文:

Adding precision

There is probably a solution in go but as I don't code in go, here is a general solution.

For instance if your selected language doesn't provide a solution to handle the precision of floats (already happened to me):

If your language provides you N digits after the dot, you can, in the case of the square root, multiply the input, here 2, by 10^(2*number_of_extra_digits).

For instance if go would give you only 1.41 as an answer but you would want 1.4142, then you ask it the square root of 2*10^(2*2) = 2*10000 instead and you get 141.42 as an answer. Now I leave it up to you to rectify the placement of the dot.

Explanation: There is some math magic behind it.

If you were to want to add some precision to a simple division, you would just need to multiply the input by 10^number_of_extra_digits.

The trick is to multiply the input to get more precision as we can't multiply the output (the lost of precision already happened). It does work because most languages cut more decimals after the dot, than before it.

So we just need to change the output equation to the input equation (when possible):

For simple division: (a/b) * 10 = (a*10)/b

For square root: sqrt(a) * 10 = sqrt(a) * sqrt(100) = sqrt(a*100)

Reducing precision

Some similar tinkering can also help to reduce the precision if needed.

For instance if you were trying to calculate the progression of a download in percent, two digits after the dot.

Let's say we downloaded 1 file on 3, then 1/3 * 100 would give us 33.33333333.

If there is no way to control the precision of this float, then you could do cast_to_an_int(1/3 * 100 * 100) / 100 to return 33.33.

huangapple
  • 本文由 发表于 2015年5月19日 12:12:27
  • 转载请务必保留本文链接:https://go.coder-hub.com/30316639.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定