12-11-2020, 05:17 PM
书上的一道习题，本人按照作者的提示，利用前N个奇数之和等于N^2这一关系，迭代找到这样一个N值，使得前N个奇数之和，即1+3+...+(2N-1)刚好大于或者等于2*10^40，则N等于sqrt(2)精确到小数点后20位的近似值乘以10^20。本人将大数按照8个十进制位进行分段，程序写出来大概是这个样子（变量及函数名用汉语拼音表示）：
如果是计算sqrt(2)精确到小数点后8位的近似值，上述程序尚可在合理的时间内完成，本人尝试达到小数点后12位的精度，耗时大约一天左右。如果想要达到20位的精度，假设总耗时和迭代步数呈线性关系，总共耗时大约是十万年左右。感兴趣的可以尝试编译一下上述程序，但是不要去运行它。如有更高效的算法（高效到可以在合理的时间内达到要求的精度）可以讨论。正确答案是1.41421356237309504880
代码:
#include<stdio.h>
#define YI 100000000
int jinwei(int*);
int main(void)
{
int he[6] = {0};
int jishu[6] = {1};
int xushu[6] = {1};
while(1)
{
for(int i = 0; i <= 2; i++)
{
he[i] += jishu[i];
}
jinwei(he);
if(he[5] >= 2)
{
break;
}
jishu[0] += 2;
xushu[0]++;
jinwei(jishu);
jinwei(xushu);
}
for(int i = 5; i >= 0; i--)
{
printf("%08d", xushu[i]);
}
puts("");
return 0;
}
int jinwei(int *p)
{
for(int i = 0; i <= 4; i++)
{
if(p[i] >= YI)
{
p[i + 1] += p[i] / YI;
p[i] %= YI;
}
}
}