2

在简单的素数检查中，通常的做法是检查从 2 到 的除数max = floor(sqrt(n))。

在 IEEE 定义的浮点算术中（比如 32 位和 64 位数字），浮点错误是否会导致您错过一个略大于 的因子max？

例如，max = floor(sqrt(REALLY_BIG_N))，但是(max + 1) * something = REALLY_BIG_N。

如果我的问题不完全清楚，请发表评论。

（请注意，我对这里的素数检查替代方案或避免sqrt使用不感兴趣x * x < n- 我的问题实际上是关于它是否适用于 IEEE 浮点算术。）

4

3 回答 3

3

不。

我假设它max+1可以表示为一个浮点值（它并没有太大以至于超出了浮点格式可以表示区间中所有整数的区间）。

我还假设something您的 in(max+1) * something是大于 的整数max。否则，它（或较小的因子）会在之前搜索除数时找到。这意味着n ≤ ( max +1)•( max +1)。

正确实现sqrt的返回最接近其参数平方根的可表示值。因此，如果 的数学平方根n至少为x+1，则sqrt(n)必须返回x+1或更大；它不能返回x，因为x它离平方根远x+1。因此，结果max = floor(sqrt(n))不小于 floor(sqrt( n )) 的数学值。

对于 IEEE-754 64 位二进制（以下简称double），最多 2 53的所有整数都是可表示的。2 53 +1 是第一个不可表示的整数。因此，上面的内容告诉我们，对于 (2 53 +1) 2sqrt(n)之前的所有人都足够n了，但不包括在内。当然，许多这么大的整数无论如何都不能完全表示，所以你一开始就不能将它们传递给它们。doublesqrt

于 2013-10-16T19:41:57.697 回答
3

为了补充 Eric Postpischil 的回答：是的，然后又不是。这取决于我们在非常大floor(sqrt(n))的情况下将如何解释。n

正如在 Eric 的回答中，让我们假设 IEEE 754 binary64 格式浮点和正确舍入sqrt的 ，通常的舍入到偶数舍入模式有效。我还假设可以访问任意精度的整数类型n。

第一种解释：假设n可以取任何整数值，那floor(sqrt(n))将被解释为floor(sqrt(convert_to_double(n)))。然后立即出现问题n >= 2^1024 - 2^970，因为convert_to_double此时会溢出。（我假设它convert_to_double也是正确四舍五入的。）从另一端开始，Eric 的回答已经表明我们擅长但不包括n = (2^53 + 1)^2，正如他所建议的那样，n = (2^53 + 1)^2这是一个问题案例：有convert_to_double(n)value 2^106 + 2^54，小于真实值，并将sqrt(convert_to_double(n))向下舍入为2^53，这意味着您的试用除法函数将错过因子2^53 + 1。但是，鉴于它2^53 + 1可以被3和整除107，到那时，审判部门可能已经发现了其他因素，因此失踪2^53+1可能不是问题。在那种情况下，n = (2^53 + 5)^2应该被认为是第一个问题案例。（2^53 + 5是素数。）

第二种解释：假设它n被限制为一个正整数，可以精确地表示为双精度数。那么一个简洁的事实是，任何除数n也必须精确地表示为双精度： n可以写成m•2^e一些非负指数e和奇整数m的形式m < 2^53，并且任何除数n都可以写成d•2^f一些除数和指数d的形式. 但是现在 if的除数小于 的精确平方根,完全可以表示为双精度数，因此最接近的可表示双精度数 的平方根mf0 <= f <= exnnxn必须大于或等于x。所以上来的试师套路floor(sqrt(n))不能错过x。

只是为了好玩：这里我们只担心nfor whichfloor(sqrt(n))给出的值太小。如果您还对floor(sqrt(n))给出的值太大的情况感兴趣，第一个示例出现得更早，在n = (2^26 + 1)^2 - 1. （证明留作练习。）

当然，这都是相当学术性的：如果你正在用大于 的数字进行试除法2^106，那么你将等待很长时间才能得到任何结果......

于 2013-10-17T15:32:35.327 回答
1

在处理素数时没有理由使用浮点运算。曾经！而不是计算max，你应该只循环直到d * d > n，d试验除数和n被测试的数字在哪里。如果您必须计算平方根，请编写您自己的仅使用整数运算的函数；牛顿的方法非常适用于整数。

编辑：这是一个计算整数平方根的简单函数：给定一个整数n，返回不超过的isqrt(n)最大整数*x；所有除法都是截断任何小数余数的整数除法：x * xn

function isqrt(n)
    x := n
    y := (x + n // x) // 2
    while y < x
        x := y
        y := (x + n // x) // 2
    return x
于 2013-10-16T23:57:21.053 回答