快速整数 sqrt 上限近似

Question

这是一个关于我的家庭作业的问题，特别是 NASM。

我正在编写一个算法来查找数字的最小整数因子。（大于 1）

用伪代码可以概括为：

if(n%2==0)
    return 2;
for(i=3; i <= n/2; i+=2)
    if(n%i==0)
        return i;
return n;

程序只是比大数的要求稍慢。 (n > 1 000 000 000)

（对我而言）最明显的改进是将 n/2 替换为 sqrt(n)。但是，我不应该知道如何使用浮点数，并且通过牛顿法找到整数 sqrt 似乎有点矫枉过正。（因为我实际上不需要知道确切的值，虽然我没有测试过，但我想找到 isqrt recursively/iteratively 会很慢）

所以我想知道是否有一些函数的快速算法，例如sqrt(n) < f(n) < n/2。 "fast" 我的意思是最好是常数时间，f(n) < n/2 我的意思是大 n.

的时间要少得多

我正在考虑的一些选项是：

检查 i <= min(sqrt(2^32), n/2)，其中 sqrt(2^32) = 2^16 是常数。
用i <= (2^p)替换i <= n/2，其中p = ⌈log_2(n)/2⌉什么的。（p 是 n 最高有效位的一半）

Answer 1

将 i 替换为 i*i:

 if (n % 2 == 0)
    return 2;
for (int i = 3; i * i <= n; i += 2)
    if (n % i == 0)
        return i;
return n

Answer 2

最后我选择了⌈log_2(n)/2⌉版本。自 sqrt(n) = 2^(log_2(n)/2)。所以对于任何有需要的人来说，这是我的解决方案。 sqrt(n) 上限近似为 O(1)。整个算法是O(sqrt(n))（我认为）。

mov esi,ebx     ;ebx = N
shr esi,1       ;esi = N/2
cmovnc esi,2    ;if no remainder RETURN 2
jnc RETURN
mov edi,2       ;edi is max counter
bsr eax,ebx     ;eax is most significant set bit of ebx (log_2(eax))
shr eax,1       ;eax/=2
mov cl,al
shl edi,cl      ;max counter is 2^(log_2(N)/2 + 1) >= sqrt(N)
mov esi,1       ;default answer is 1
mov ecx,3       ;start counter is 3
START:
mov edx,0
mov eax,ebx
div ecx         ;divide N by counter
test edx,edx    ;if no remainder RETURN counter
cmovz esi,ecx
jz RETURN
add ecx,2       ;else counter += 2
cmp ecx,edi
jb START        ;if counter <= max counter try agian with new divisor
RETURN:
                ;the answer is in (esi)

P.S。如果您想知道我为什么不检查 i*i <= N。它实际上比这个版本慢得多。只是在循环中添加一个 mul 不应该减慢它的速度，所以我怀疑它每次迭代都会破坏分支预测算法。 cmp ecx,edi 将计数器与常量进行比较，因此大多数时候它可能会被预测正确，而 cmp 'ecx*ecx',ebx 将比较计数器的平方，这对处理器来说可能不是那么明显.

Answer 3

找到平方根有一个迭代过程：

def approximate_sqrt(number, depth, start_val):
    for i in range(depth):
        start_val=(start_val+number/start_val)/2
    return start_val

初始猜测 (start_val) 越好，收敛到合理解的速度就越快。

If start_val>sqrt(number) 

then every iterative value>sqrt(number)

因此它提供了一个上限（类似于 start_val < sqrt(number)）。如果您的初始猜测非常接近，您可以将迭代深度减少到 1 或 2。因此，为了迭代地猜测素数候选的上限，例如你可以调用

sqrt_appr=approximate_sqrt(i, 1, sqrt_appr+1)

为下一个素数候选者提供先前对 sqrt_appr 平方根的估计，并得到误差约为 10E-6 的上限。（虽然每次我检查近似值的接近程度时，这是针对 300 万个数字的间隔，我设置 sqrt_appr=sqrt(number)+1 来重置过程。）

快速整数 sqrt 上限近似

Fast integer sqrt upper bound approximation

nasm

approximation

sqrt

square-root

upperbound