优化哥德巴赫猜想的算法

pscc0001

pmerofc 对谭浩强的《C程序设计》以及《C程序设计伴侣》的批评，除开少量吹毛求疵之处以及语文上的问
题，基本是赞同的。这里表示敬意。

对 pmerofc 上面贴的 "问题11 似是而非的k=sqrt(n)" 中关于 sqrt 的说法，有些不同看法。

>>> 而不是像数学那样一定可以得到一个精 确值

数学上的 sqrt(n) 也不存在所谓的精确值，而只是存在一个概念，我们可以使用 "n 的平方根" 这个概
念，它具有性质 "n 的平方根" 的平方 = n，如此而已，

在 c 语言范畴内，整数的平方根 sqrt(n) 的结果是浮点数。应当怎样取舍到相近的整数，不存在数学上
较优的答案，而是由实际需求决定的。

为达到 "题目：输入一个大于3的整数n，判定它是否为素数(prime，又称质数)" 的目的，要避免类似 sqrt(9.0)
计算出 2.99..。然后舍入到 2 导致"循环次数就会产生错误" 的问题，需要做的无非是算法改为

k = sqrt(n) + 1;

这就确保了即使特殊的边界条件下 k 也一定大于 (int)(sqrt(n)) 的理论值,同时不增加太大的运算量.

>>> 那么此时应该如何求n的平方根或其整数部分呢？实际上可以利用下面的数学常识轻易求得：

这算法完全是无用功，pmerofc 暂时性退化到 MVP 一个档次了。

>>> 由于只需进行   次整数的加减法运算，其效率方面也必定高于浮点运算的k=sqrt(n)。

我看到的 "进行" 和 "次整数" 中间没有数字,不知道是什么缘故。但 n 稍大的情况下，sqrt(n) 肯定
是效率较高的。

pmerofc 提供的算法是随 N 递增的，比如 n 若为 1,000,000,000，则
while( n_ >=  odd ) { n_ -= odd  ; ...} 那个循环会运行 31622 次。

sqrt(n) 本身是 O(1) 算法，优越太多。

另外 x86 处理器有 sqrt 的硬件指令的，x87 浮点部件支持 FSQRT 指令，SSE 支持双精度的 SQRTSD
单精度的 SQRTSS。

在 ICC / GCC 上都有 intrinsic 指令直接对应硬件指令的，比如在 Visual Studio C++ 上就是

__m128 _mm_sqrt_ss(__m128 a);

其效率是非常高的。

根据 <<Intel® 64 and IA-32 Architectures Optimization Reference Manual>>

不同的 Intel 处理器上 SQRTSS 指令的 latency 在 23 ~ 32，throughput 也在 23 ~ 32.
加法指令 ADDSS 的 latency 在 4 ~ 5，throughput 为 2。

但即使 sqrt(n) 被编译成调用 C 库函数使加减乘除指令计算级数来逼近的方式，仍然是远超 pmerofc
的方法的。

下面是一些风格上的看法，这种东西没有定论，作为另一种选择提出来吧：

>>> printf("%d%s是素数\n" ，n ，(i > k)?"":"不");

我个人对这种视情况添加完全改变语义的 "不" 字的做法深恶痛绝。不要用把不相干的东西强行拉扯到
一起，总有一天会受到惩罚的。

if (i>k) {
    printf("%d是素数\n" ，n);
} else {
    printf("%d不是素数\n" ，n);
}

清晰明了，符合直觉，一望而知，也容易国际化，不好吗？

>>> n，k，n_

这种要看代码才知道其作用的变量命名非常可恶。建议：

n  -> num
n_ -> tmpNum
k  -> theSqrtOfNum

最后，对于整数/实数在表示为浮点数时产生的误差，是通过算法的收敛性来控制的，而不是采用避开浮点
算法的消极对策，大多数情况也避不开。

pscc0001

回复 9# zooyo

我也只是随便扯扯，没有深入讨论的能力。

你这方法个人觉得没什么大问题，只要不是循环中反复执行的部分，完全可以接受啊。

这里只想说一点，存在专用于 float 类型的 sqrtf(); 函数，比用于 double 类型的 sqrt() 更合适。

我记得最早 c 语言做浮点运算是一律先转换成 double 的（所以做数值计算的人对这个特性非常头疼）。

后来改掉了。

至于这个 sqrtf() 函数 究竟在什么条件下可用，要请教标准方面的高人了。

另外前面对 sqrt 函数的性能的讨论不是很准确，对付着看吧。

另外顺便说一句 1/sqrt() 在 x86 上也是有硬件指令的。