计算 x^2 的算法还是计算数字平方根的算法更有效？

Question

计算 x^2 和 x^(1/2) 的更有效算法是什么？在两者之间最好的是什么更有效率？我要解决的问题在于找到第 n 个 'green' 数字，其中如果 N^2 以 n 结尾，则 N 是 'green' 数字。例如5^2=25、376^2=141376。这是我试过的一些代码，但计算第 10 个数字需要很多时间：

我所做的基本上是取 x 位数中的 i 得到 i 的最后 x 位数字，不求全幂并将最后 x 位数字与 i 进行比较，如果重合则将 1 加到累加器变量。我正在考虑以另一种方式解决这个问题，而不是为每个数字计算 i^2，计算数字的 i^(1/2) 并进行相同的比较可能会改进一点程序，因为只需要接受计算以 0、1、4、9、6、5 结尾的数字。但我知道真正的改进来自于换一种方式思考问题，对此我一无所知。

def special_multiply(sa):
reverse_num = reversed(sa)
accumulator = 0
for i, digit in enumerate(reverse_num):
    temp_chunk = sa[i:]
    temp_pow = "".join(['1', '0' * i])
    accumulator += int(digit) * int(temp_chunk) * int(temp_pow)
return accumulator % int("".join(['1', '0' * (i + 1)]))

def green(n):
count = 0
i = 0
while count <= n:
    i += 1
    si = str(i)
    if si == str(special_multiply(si)):
        count += 1
return i

Answer 1

首先，计算 x^2 的算法非常简单——只需计算 x*x 即可。假设 x ~ 2^n 然后 x * x 的计算在 O(n) 中（2^n 可以用 n 位表示，多路复用是 O(1) 因为如果我们对 n 位进行多路复用它将是 O (n)). 相反，x^(1/2) 是非常复杂的计算并且包括迭代次数，当然-您实际上需要编写一个算法而不是行 x*x.

Answer 2

换句话说，一个 k 位的数字 x 如果满足

则为绿色

 2           k
x  = x mod 10 .

Chinese remainder theorem表示这个等式等价于两个等式

 2          k
x  = x mod 2

 2          k
x  = x mod 5 .

求解这些方程等同于求多项式 x^2 - x = x (x - 1) mod 的根 2 或 5 的幂。 Mod2和mod5，有两个解，分别是x = 0和x = 1。由于多项式的导数 2x - 1 是非零的 mod 2 和 mod 5 对于两个解，Hensel's lemma 意味着 0 和 1 实际上是唯一的解 mod 素数幂。

因此有四个解mod10^k，其中有残数0或1mod2^k和5^k.例如，376 mod 5^3 = 1 和 376 mod 2^3 = 0。对于每个 k，我们可以使用中国余数定理来找到四个解（其中一个将为零，因此不合格）。

计算 x^2 的算法还是计算数字平方根的算法更有效？

What is more efficient, an algorithm to calculate x^2 or one to calculate the square root of a number?

algorithm

root

square