分页： 1 / 1
有趣的近似公式
发表于 ： 2023年 7月 7日 22:27
由 （ツ）
sqrt(x^2 + y^2) ≈ 0.96x + 0.4y (原0.94 x + 0.4 y)
假设x >= y >= 0
精度(最大误差)在4%
还有哪些类似的近似公式？Doom的fast 1/sqrt(x)算最著名的吧
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 02:33
由 YWY
When x = 1 and y = 0, then sqrt(x^2 + y^2) = 0 but 0.94 x + 0.4 y = 0.94, which is off by 6%.
When x = 1 and y = 1, then sqrt(x^2 + y^2) = sqrt(2) but 0.94 x + 0.4 y = 1.34, which is off by more than 5%.
I would rather use sqrt(x^2 + y^2) ≈ x + 0.4 y, where x >= y >= 0. Or maybe 1.1 x + 0.4 y is even better?
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 09:33
由 （ツ）
YWY 写了： 2023年 7月 8日 02:33
When x = 1 and y = 0, then sqrt(x^2 + y^2) = 0 but 0.94 x + 0.4 y = 0.94, which is off by 6%.
When x = 1 and y = 1, then sqrt(x^2 + y^2) = sqrt(2) but 0.94 x + 0.4 y = 1.34, which is off by more than 5%.
I would rather use sqrt(x^2 + y^2) ≈ x + 0.4 y, where x >= y >= 0. Or maybe 1.1 x + 0.4 y is even better?
原文写错了，应该是0.96x + 0.4y
x的系数应该是一个(0,1)之间接近1的一个数，y的系数应该是应该小一些也在(0,1)之间
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 11:47
由 YWY
（ツ） 写了： 2023年 7月 8日 09:33
原文写错了，应该是0.96x + 0.4y
x的系数应该是一个(0,1)之间接近1的一个数，y的系数应该是应该小一些也在(0,1)之间
画一下图能看出，x + 0.4 y比0.96x + 0.4y更靠近sqrt(x^2 + y^2), where x >= y >= 0。
因为考虑的是%误差，我们可以把近似式的两边同除以x，得到sqrt(1^2 + (y/x)^2) ≈ 1 + 0.4 y/x, where 1 >= y/x >=0。你给的近似式就是sqrt(1^2 + (y/x)^2) ≈ 0.96 + 0.4 y/x, where 1 >= y/x >=0。把y/x换成x，我们来对比下面两个近似表达
sqrt(1 + x^2) ≈ 1 + 0.4 x 和 sqrt(1 + x^2) ≈ 0.96 + 0.4 x, where 1 >= x >= 0.
通过在[0, 1]区间画sqrt(1 + x^2)，1 + 0.4 x 和 0.96 + 0.4 x 这三个函数的图，能看出1 + 0.4 x更靠近sqrt(1 + x^2)。如果我们用稍大于1的数，误差%会更小，这也是sqrt(x^2 + y^2) ≈ 1.1 x + 0.4 y可能会更好的原因；当然1.1只是随手一写，可能1.06或1.12会更好一些。
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 11:51
由 YWY
（ツ） 写了： 2023年 7月 7日 22:27
Doom的fast 1/sqrt(x)算最著名的吧
好奇Doom的fast 1/sqrt(x)是怎么表述的。。。
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 12:22
由 （ツ）
YWY 写了： 2023年 7月 8日 11:47
画一下图能看出，x + 0.4 y比0.96x + 0.4y更靠近sqrt(x^2 + y^2), where x >= y >= 0。
因为考虑的是%误差，我们可以把近似式的两边同除以x，得到sqrt(1^2 + (y/x)^2) ≈ 1 + 0.4 y/x, where 1 >= y/x >=0。你给的近似式就是sqrt(1^2 + (y/x)^2) ≈ 0.96 + 0.4 y/x, where 1 >= y/x >=0。把y/x换成x，我们来对比下面两个近似表达
sqrt(1 + x^2) ≈ 1 + 0.4 x 和 sqrt(1 + x^2) ≈ 0.96 + 0.4 x, where 1 >= x >= 0.
通过在[0, 1]区间画sqrt(1 + x^2)，1 + 0.4 x 和 0.96 + 0.4 x 这三个函数的图，能看出1 + 0.4 x更靠近sqrt(1 + x^2)。如果我们用稍大于1的数，误差%会更小，这也是sqrt(x^2 + y^2) ≈ 1.1 x + 0.4 y
可能会更好的原因；当然1.1只是随手一写，可能1.06或1.12会更好一些。
我用desmos画了，x + 0.4y当x = 1, y = 0.4的时候，sqrt(1+0.4^2) = 1.077, 1 + 0.4*0.4 = 1.16,相差7%
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 12:22
由 （ツ）
YWY 写了： 2023年 7月 8日 11:51
好奇Doom的fast 1/sqrt(x)是怎么表述的。。。
可以参考
https://en.wikipedia.org/wiki/Fast_inverse_square_root
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 12:30
由 YWY
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 12:32
由 （ツ）
YWY 写了： 2023年 7月 8日 12:30
好的，我看看。
要算这个的原因是经常需要做归一化处理，(x, y, z) -> (x / sqrt(x^2 + y^2 + z^2), y / sqrt(x^2 + y^2 + z^2), z / sqrt(x^2 + y^2 + z^2))
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 12:39
由 YWY
（ツ） 写了： 2023年 7月 8日 12:22
我用desmos画了，x + 0.4y当x = 1, y = 0.4的时候，sqrt(1+0.4^2) = 1.077, 1 + 0.4*0.4 = 1.16,相差7%
谢画图解释！你是对的
我只是在心里画了下图，没仔细画，误以为sqrt(1 + x^2)的图像是concave down 的（二阶导数为负的那种）。或者说，我心里想的其实是sqrt(1 + x)的图像，这是concave down的。换句话说，sqrt(1 + x) ≈ 1.1 + 0.4 x 应该差不多。
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 12:41
由 nk
看了一下， 大知识用 x^{1/2} = 2^{log_2(x)/2}, 由于用的2,很多操作可以用 bit 的操作来实现。 当然为了避免数的溢出，需要做一些特殊处理。
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 13:19
由 YWY
（ツ） 写了： 2023年 7月 7日 22:27
sqrt(x^2 + y^2) ≈ 0.96x + 0.4y (原0.94 x + 0.4 y)
假设x >= y >= 0
精度(最大误差)在4%
还有哪些类似的近似公式？Doom的fast 1/sqrt(x)算最著名的吧
还以为Doom的fast 1/sqrt(x)是一个类似于sqrt(x^2 + y^2) ≈ 0.96x + 0.4y 的近似表达式，原来是个程序。看来人们为了避免根号和除法发明了很多手段，学习了。
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 13:30
由 nk
（ツ） 写了： 2023年 7月 8日 12:32
要算这个的原因是经常需要做归一化处理，(x, y, z) -> (x / sqrt(x^2 + y^2 + z^2), y / sqrt(x^2 + y^2 + z^2), z / sqrt(x^2 + y^2 + z^2))
好像你是需要速度，对精度要求不高
这个可以用分段（两段或者三段）函数来计算，会快很多，而且精度比直线会好的多。
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 16:57
由 Caravel
（ツ） 写了： 2023年 7月 7日 22:27
sqrt(x^2 + y^2) ≈ 0.96x + 0.4y (原0.94 x + 0.4 y)
假设x >= y >= 0
精度(最大误差)在4%
还有哪些类似的近似公式？Doom的fast 1/sqrt(x)算最著名的吧
这个感觉不对劲，对 x y 不对称
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 17:01
由 （ツ）
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 17:04
由 （ツ）
Caravel 写了： 2023年 7月 8日 16:57
这个感觉不对劲，对 x y 不对称
就是不失一般性假设。这样可以把整个\R^2平面上的定义域缩小到[0,1]\subset\R，方便讨论
Re: 有趣的近似公式
发表于 ： 2023年 7月 8日 17:18
由 YWY
Caravel 写了： 2023年 7月 8日 16:57
这个感觉不对劲，对 x y 不对称
假设x >= y >= 0