1

我想计算 q^k，st q 是 n 位宽，在限制中：

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

我试着成对做这件事；从 q^2 开始，然后是 q^4，等等。第一步的结果需要 2n 位，第二步需要 (2^2)n 位等，最后一步需要 n*2^(logk) (=kn ) 位。我们有 log(k) 步，仔细计算得出：O(log(n)(log(k))^2)。在上述限制中，我很高兴听到更快的方法（或对该算法或类似算法的更好分析）。提前致谢。

4

2 回答 2

0

假设具有n-bit 输出的乘法具有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),

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

于 2013-08-01T19:56:16.357 回答
0

我认为通过 k 位时最好的整数 pow 是O(2*Log2(K))。

  • k 可以写成二进制形式 k = { kn-1,...k3,k2,k1,k0 }

所以方程看起来像这样：

q^k = q^( 1*k0 +2*k1 +4*k2 +8*k3 ... )
q^k = q^k0 * q^(2*k1) * q^(4*k2) ....
  • 所以你只有 n = ceil(log2(k)) 步骤来计算
  • 如果 ki!=0，则每一步乘 q^i 得到结果
  • q(i+1)=qi*qi
  • q0 = q

简化的工作代码（不处理特殊情况 0^k,k^0,0^0,...）：

DWORD pow(DWORD q,DWORD k)
    {
    DWORD s;
    for (s=1;k;k>>=1,q*=q)
     if (k&1) s*=q; 
    return s;
    }

当然，如果你想使用 big q,k 而不是 bigint 算术

  • 我不认为配对低位乘法会有很大帮助
  • 除非用于非常大的数字
  • 因为配对和合并不同的位数子结果通常比较慢
于 2013-09-17T12:57:31.323 回答