使用蒙特卡罗查找 PI 数字
我尝试过许多使用蒙特卡罗求 π 的算法。 解决方案之一(在Python中)是这样的:
def calc_PI():
n_points = 1000000
hits = 0
for i in range(1, n_points):
x, y = uniform(0.0, 1.0), uniform(0.0, 1.0)
if (x**2 + y**2) <= 1.0:
hits += 1
print "Calc2: PI result", 4.0 * float(hits) / n_points
可悲的是,即使有1000000000,精度也非常糟糕(3.141...)。
这是该方法可以提供的最大精度吗? 我选择蒙特卡洛的原因是它很容易将其分解为并行部分。 是否有另一种易于分解和计算的 π 算法?
I have tried many algorithms for finding π using Monte Carlo.
One of the solutions (in Python) is this:
def calc_PI():
n_points = 1000000
hits = 0
for i in range(1, n_points):
x, y = uniform(0.0, 1.0), uniform(0.0, 1.0)
if (x**2 + y**2) <= 1.0:
hits += 1
print "Calc2: PI result", 4.0 * float(hits) / n_points
The sad part is that even with 1000000000 the precision is VERY bad (3.141...).
Is this the maximum precision this method can offer?
The reason I choose Monte Carlo was that it's very easy to break it in parallel parts.
Is there another algorithm for π that is easy to break into pieces and calculate?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
使用准随机数生成器 (http://www.nag.co.uk/IndustryArticles /introduction_to_quasi_random_numbers.pdf)而不是标准的伪 RNG。 准随机数比伪随机数更均匀地覆盖积分区域(您正在做的是 MC 积分),从而提供更好的收敛性。
Use a quasi random number generator (http://www.nag.co.uk/IndustryArticles/introduction_to_quasi_random_numbers.pdf) instead of a standard pseudo RNG. Quasi random numbers cover the integration area (what you're doing is a MC integration) more evenly than pseudo random numbers, giving better convergence.
这是蒙特卡罗的一个经典例子。 但是,如果您尝试将 pi 的计算分解为并行部分,为什么不直接使用无限级数并让每个核心取一个范围,然后对结果进行求和呢?
http://mathworld.wolfram.com/PiFormulas.html
This is a classic example of Monte Carlo. But if you're trying to break the calculation of pi into parallel parts, why not just use an infinite series and let each core take a range, then sum the results as you go?
http://mathworld.wolfram.com/PiFormulas.html
您的小数误差为
sqrt(N)/N = 1/sqrt(N)
,因此这是获得精确估计的非常低效的方法。 该限制是由测量的统计性质决定的,无法突破。对于
N
次抛出,您应该能够获得大约floor(log_10(N))/2-1
位的良好精度。 也许-2
只是为了安全起见......即使如此,它也假设您使用的是真正的 RNG 或足够好的 PRNG。
Your fractional error goes by
sqrt(N)/N = 1/sqrt(N)
, So this is a very inefficient way to get a precise estimate. This limit is set by the statistical nature of the measurement and can't be beaten.You should be able to get about
floor(log_10(N))/2-1
digits of good precision forN
throws. Maybe-2
just to be safe...Even at that it assumes that you are using a real RNG or a good enough PRNG.