收敛阶与效率

测试环境:
OS:FreeBSD6.0
CPU:AMD AlthonXP 2400+
Memory: 256x2
代码为:
2阶

FloatType sqrt_2(const FloatType& value,const IntType& n){ 
    ACE_TRACE("sqrt_2"); 
    FloatType retval(value); 
    for(IntType i=0;i!=n;++i){ 
        retval=(retval+value/retval)/2; 
    } 
    return retval; 
}

3阶

FloatType sqrt_3(FloatType value,IntType n){ 
    ACE_TRACE("sqrt_3"); 
    FloatType retval(value); 
    for(IntType i=0;i!=n;++i){ 
        FloatType x2=retval*retval; //x^2 
        FloatType x3=retval*x2; //x^3 
        x2*=3; //3x^2 
        retval*=3*value; //3xa 
        retval=(x3+retval)/(x2+value); 
    } 
    return retval; 
}

4阶

FloatType sqrt_4(FloatType a,IntType n){ 
    ACE_TRACE("sqrt_4"); 
    FloatType x(a); 
    for(IntType i=0;i!=n;++i){ 
        FloatType t=x*x+a; 
        x=t/(4*x)+a*x/t; 
    } 
    return x; 
}

第一组测试
被测数据
785544846554235596499070744180589750691109482706911662586613515463842050815959
用bc在100位精度下算出的平方根为886309678698272817467466386261572628735.995718
利用gmp采用
1048576位的精度计算,要求相对误差小于e-1024

收敛阶 用户态消耗时间 内核态消耗时间 elapsed time CPU使用率 数据/栈 (非共享)内存使用量 迭代次数 相对误差
2 30.105 1.355 0:32.09 98.0% 3043k 140 2.3538e-1366
3 27.644 1.431 0:29.67 97.9% 3697k 89 1.4070e-2851
4 32.756 1.263 0:34.55 98.4% 3676k 70 2.3538e-1366

被测数据:
35380725297329716015114063545317729537886309678698272817467466386261572628736169703782995871148670588879065676176396629715686184475733959934854482592265912
用bc在100位精度下算
出的平方根为
18809764830355991459012140810861155850185053524473725080763732144640\
9307543610.766394489551320795510077960216933711717384445153161540505\
4174048567062508923329530468259757553133571
利用gmp采用
1048576位的精度计算,要求相对误差能尽可能小

收敛阶 用户态消耗时间 内核态消耗时间 elapsed time CPU使用率 数据/栈 (非共享)内存使用量 迭代次数 相对误差
2 59.146 2.493 1:02.87 98.0% 3022k 275(*) 5.436e-280337
3 54.182 3.077 0:58.61 97.6% 3681k 175 1.804e-315655
4 64.309 3.087 1:09.11 97.4% 3686k 138 2.056e-315655

如果采用276次迭代,则计算出来的相对误差为0。可能是因为恰好gmp的sqrt也采用的是这个算法

这里的相对误差最小就停留在e-315655了,再继续迭代由于精度限制无法获得更精确的结果

有一个巧合,4阶收敛迭代一次相当于2阶收敛迭代2次。也许不仅仅是恰和。
这次测试比较失败的是,无论是几阶收敛,效率相差都不是很大,但是略微还是可以看出3阶最快,其次是2阶,4阶。
如果能再找别的系统测试下就好了。

目前我还没有找到比较好的误差估计公式。找到一个在知道精确值的方式下预估计相对误差的式子

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥