C++优化PI函数估计 [英] Optimize estimating Pi function C++

查看:50
本文介绍了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_circlennum_point_total。对它们使用intlonglong long


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


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


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

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

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

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆