C++优化PI函数估计

问题描述

我已经编写了一个程序，它使用蒙特卡罗方法近似PI。它工作得很好，但我想知道我是否可以让它工作得更好、更快，因为当插入~n = 100000000或更大的内容时，需要一些时间来进行计算和打印结果。

我想过如何通过对n结果进行中值运算来更好地逼近它，但考虑到我的算法对大数的运算速度太慢，我决定不这样做。

基本上，问题是：如何才能使此函数更快地工作？

以下是我到目前为止得到的代码：

double estimate_pi(double n)
{
    int i;
    double x,y, distance;
    srand( (unsigned)time(0));
    double num_point_circle = 0;
    double num_point_total = 0;
    double final;

    for (i=0; i<n; i++)
    {
        x = (double)rand()/RAND_MAX;
        y = (double)rand()/RAND_MAX;
        distance = sqrt(x*x + y*y);
        if (distance <= 1)
        {
            num_point_circle+=1;
        }
        num_point_total+=1;
    }
    final = ((4 * num_point_circle) / num_point_total);
    return final;
}

推荐答案

一个明显(很小)的加速是取消平方根运算。sqrt(x*x + y*y)正好小于1，当x*x + y*y也小于1时。因此，您可以只写：

double distance2 = x*x + y*y;
if (distance2 <= 1) {
    ...
}

这可能会有所收获，因为计算平方根是一种昂贵的操作，并且需要更多的时间(大约比一次加法慢4-20倍，具体取决于CPU、体系结构、优化水平等)。

您还应该对变量使用整数值，如num_point_circle、n和num_point_total。对它们使用int、long或long long。

---

蒙特卡罗算法的并行性也令人尴尬。因此，一个加快速度的想法是用多个线程运行算法，每个线程处理n的一小部分，然后在结束时计算出圆内的点数。

---

此外，您还可以尝试使用SIMD指令提高速度。

---

和最后一样，有更有效的方法来计算PI。使用蒙特卡罗方法，你可以进行数百万次迭代，但只得到几位数的精度。有了更好的算法，就有可能计算数千、数百万或数十亿位数字。

例如，您可以在网站上阅读https://www.i4cy.com/pi/

这篇关于C++优化PI函数估计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！