这是一个关于我的家庭作业的问题,特别是关于 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)
.但是,我不应该知道如何使用 float ,并且通过牛顿法找到整数 sqrt 似乎有点矫枉过正。 (因为我实际上不需要知道确切的值,虽然我没有测试过它,但我想递归/迭代地找到 isqrt 会很慢)
所以我想知道,是否有一些函数的快速算法,例如 sqrt(n) < f(n) < n/2
.我所说的“快”是指最好是常数时间,而 f(n) < n/2
我的意思是大 n
明显更少.
我正在考虑的一些选项是:
检查
i <= min(sqrt(2^32), n/2)
, 其中sqrt(2^32) = 2^16
是常数。替换
i <= n/2
与i <= (2^p)
, 其中p = ⌈log_2(n)/2⌉
或者其他的东西。 (p
是n
最高有效位的一半)
最佳答案
有一个寻找平方根的迭代过程:
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
的上限.
(虽然每次我检查近似值的接近程度时,我都会设置 sqrt_appr=sqrt(number)+1
来重置过程。)
关于nasm - 快速整数 sqrt 上限近似,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42732225/