以低複雜度的方式求冪

我想計算q^k，s.t. q是n位寬，在侷限中：以低複雜度的方式求冪

最終結果將是n * k位寬。
對於計算的每一步，乘以x，y s.t.的結果。 x是| x |位寬，y是| y |位寬是| x | * | y |位寬。

我試着做成對;第一步結果取2n位，第二步取（2^2）n位等，最後一步取n * 2 ^（logk）（= kn）位。我們有log（k）個步驟，仔細計算使我們得到： O（log（n）（log（k））^ 2）。在上述限制條件下，我很樂意聽到更快速的方法（或更好地分析此算法或類似方法）。在此先感謝。

來源

2013-08-01 Alfred

http://www.google.com/search?q=exponentiation+by+squaring –

HTTP：/ /en.wikipedia。org/wiki/Exponentiation_by_squaring＃Alternatives_and_generalizations –

@SargeBorsch最好鏈接到一個特定的結果，而不是Google –

假設與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),

這是最後的乘法的成本的兩倍。其他乘法可以類似地進行分析。

來源

2013-08-01 19:56:16

我認爲最好的整數pow是O（2 * Log2（K））當經過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 =小區（LOG2（k））的步驟，以計算
每個步驟乘法C 1-4 i到的結果，如果き！= 0
q（I + 1）=氣*齊
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; 
    }

當然

如果你想用大q，改爲需要

我不認爲配對低位乘法將有很大幫助
除非使用FOķ比BIGINT算術[R真正的大數字
因爲配對和合並不同的比特數子的結果通常是慢

來源

2013-09-17 12:57:31 Spektre

以低複雜度的方式求冪

回答

相關問題