通過只添加來計算指數

Question

我們正在編寫一個非常簡單的程序，以便在我們爲一個班級構建的處理器上執行。它不具備乘法或除法的能力。然而，我們確實支持循環控制的加法，減法和（或）和分支（如果你熟悉MIPS，就像分支一樣）。我們認爲一個整潔的程序運行在它上面會是某種x^n程序。當然，這些數字將不得不進行硬編碼，但考慮到我們的處理器的侷限性，這是否現實？

對指數是否只有加法計算？ 謝謝。

Answer 1

對於小整數，爲什麼不呢？

首先，使用重複加法實現乘法。然後，使用重複乘法實現pow（）。它會很慢，但它會正常工作。

指數運算有一個更快的算法，稱爲Exponentiation by Squaring。但是，鑑於您沒有快速乘法，我不確定它是否值得 - 您可能需要先實施快速乘法算法。

Answer 2

在使用C風格的語法dmazzoni的線路輸入反應：

int mulitply(int x, int y) 
{ 
    int product; 

    for (int i = 0; i<y; i++) 
     product += x; 

    return product; 
} 

int power(int x, int exponent) 
{ 
    int result = 1; 

    for (int i = 0; i < exponent; i++) 
     result = multiply(result, x); 

    return result; 
} 

Answer 3

這是非常現實的。不用多年，處理器就沒有一個可以進行諸如乘法和除法等高級操作的ALU。

乘法通常使用移位和加法完成。下面是一些僞彙編：

; multiply registers a and b 

; use c as high b 
mov c,#0 
; use d as low result 
mov d,#0 
; use e as high result 
mov e,#0 
.nextbit: 
    ; shift low bit out of a 
    shr a 
    ; skip if zero 
    bcc .noadd 
    ; add b to result 
    add d,b 
    adc e,c 
    .noadd: 
    ; double b 
    shl b 
    rcl c 
    ; test a 
    cmp a,#0 
bne .nextbit 

（需要注意的是相乘雙字節值的結果是一個雙字節值）

一旦你有一個乘法，你可以循環來計算功率。使用

說明：

mov x,y = move y into x 
shr x = shift right one bit 
shl x = shift left one bit 
rcl x = rotate left one bit with carry inserted 
add x,y = add y to x 
adc x,y = add y to x with carry 
cmp x,y = compare x to y 
bcc = branch on carry clear 
bne = branch on not equal 
#0 = literal number zero (as opposed to 0, which would be the address zero) 

Answer 4

像Aequitarum的解決方案，但反覆使用的平方權力和反覆加倍的乘法。應該快了大型X，Y：

int multiply(int x, int y) { 
    int product = 0; 
    int bitmask = 1; 

    while (y >= bitmask) { 
    if (y & bitmask) product += x; 
    x += x; 
    bitmask += bitmask; 
    } 
    return product; 
} 

int power(int x, int exponent) 
{ 
    int result = 1; 
    int bitmask = 1; 

    while (exponent >= bitmask) { 
    if (exponent & bitmask) result = multiply(result, x); 
    x = multiply(x, x); 
    bitmask += bitmask; 
    } 
    return result; 
} 

Answer 5

您可能會發現在Multiplication ALU有關維基百科的文章。使用加法和按位運算（和和），可以每比特一步執行乘法，而不必像小操作符的大小那樣加倍。

Answer 6

指數n k的功率：

exponent(n,k) { 
    for(x=1..n) 
     x = x + exponent(x,k-1) 
}