algorithm - 以低复杂度方式求幂

Question

我想计算 q^k, s.t. q 是 n 位宽，在限制条件下:

1. 最终结果将是 n*k 位宽。
2. 对于计算的每一步，将 x,y s.t. 相乘的结果。 x 是 |x|位宽，y 是 |y|位宽为 |x|*|y|位宽。

我试着两人一组做；从 q^2 开始，然后是 q^4，等等。第一步结果占用 2n 位，第二步占用 (2^2)n 位，依此类推，最后一步占用 n*2^(logk) (=kn) 位。我们有 log(k) 个步骤，仔细计算可以得出:O(日志(n)(日志(k))^ 2)。我很高兴听到在上述限制中有一种更快的方法(或对该算法或类似算法的更好分析)。提前致谢。

Answer 1

假设 n 位输出的乘法成本为 n f(n) 对于某些正且非递减的函数 f，最终乘法的成本渐近地不低于其余工作。为 q^k 准备正方形，其中 q 有 n 位成本

   2 n f(2 n) + 4 n f(4 n) + ... + 2^floor(lg(k)) f(2^floor(lg(k)) n)
<= (2 n + 4 n + ... + 2^floor(lg(k)) n) f(2^floor(lg(k)) n)
<= 2 (2^floor(lg(k)) n) f(2^floor(lg(k)) n)
<= 2 k n f(k n),

这是最终乘法成本的两倍。其他乘法可以类似分析。