1. 首頁
  2. 問答
  3. 具有32/16位分區的處理器上的64/32位分區

具有32/16位分區的處理器上的64/32位分區

2011-01-23 104 views
18

My processor，無FPU和整數數學的小型16位微控制器僅具有16/16分區和32/16分區，均需要18個週期。目前我正在使用非常緩慢的軟件程序（約7,500個週期）來執行64/32分割。有沒有辦法使用這些分割引擎來計算64/32分割？類似於我已經使用16x16乘法器和加法器來計算32x32乘法？我使用C，但可以使用任何一般的解釋如何可以完成...我希望目標< 200個週期（如果它是所有可能的話）。具有32/16位分區的處理器上的64/32位分區

來源

2011-01-23 Thomas O

+0

是什麼語言？在大多數（如果不是全部的話）語言中，double/single與FPU一起工作並且速度非常快......除非我在這裏丟失了某些東西 – 2011-01-23 02:12:51

+0

他正在談論整數除法，而不是浮點除法 – 2011-01-23 02:13:24

+0

我們是否在談論某些特定語言（C，asm）？該機器是否具有FPU或只能在整數寄存器上運行？ – 2011-01-23 02:13:25

回答

8

請參閱多詞分部的「Hacker's Delight」（第140-145頁）。

基本概念（回去Knuth）是基於65536條款來思考你的問題。然後你有一個4位數字和2位數字的劃分問題，以2/1數字劃分作爲一個基元。

C代碼是在這裏：http://www.hackersdelight.org/hdcodetxt/divmnu.c.txt

來源

2011-01-23 05:00:55 payne

3

我的Knuth（The Art of計算機編程）正在工作，所以直到星期一才能檢查它，但這將是我的第一個來源。它有一個關於算術的全部部分。

編輯：你的帖子關於「16/16師和32/16師都需要18個週期。」 - dsPIC在彙編中有一個條件減法操作。考慮使用這個作爲你的計算基元。

還要注意的是，如果X = XH * 2 + XL和d = DH * 2 + DL，則如果你正在尋找

（Q，R）= X/d，其中X = Q * d + R

其中Q = QH * 2 + QL，R = RH * 2 + RL，然後

XH * 2 + XL = DH * QH * 2 +（DL * QH + DH * QL）* 2 +（DL * QL）+ RH * 2 + RL

這提示（通過查看屬於高32位的術語），以使用下面的過程，類似於長除法：

  1. （QH，R0）= XH /（DH + 1） - > XH = QH *（DH + 1）+ R0 [32/16除法]
  2. R1 = X - （QH * 2 ）* D [需要16 * 32乘，左移16和64位減]
  3. 計算R1' = R1 - d * 2
  4. 而R1' > = 0，調整QH向上加1，設定R1 = R1' ，和轉到步驟3
  5. （QL，R2）=（R1 >> 16）/（DH + 1）→R1 = QL *（DH + 1）+ R2 [32/16劃分]
  6. R3 = R1-（QL * D）[需要16 * 32乘法和48位減法]
  7. 計算R3' = R 3 - d
  8. 而R3' > = 0，調整QL向上加1，設定R3 = R3' ，和轉到步驟7

你的32位商是對（QH，QL），而32位餘數是R3。

（這裏假定商不超過32位，您需要提前瞭解大，可以很容易地檢查的時間提前。）

來源

2011-01-23 02:26:06

-1

我只能建議通過連續的減法並得到結果結果寄存器增量。嘗試將64位寄存器拆分爲2或4個部分並將其分開分開是一種不可行的方法，因爲整數除法引入了錯誤。

來源

2011-01-23 02:26:39

1

起點是： D.克努特，計算機程序設計2卷，第4.3.1節的藝術，算法d

不過，我想你可能需要優化的算法。

來源

2011-01-23 04:14:35 bestsss

1

你可能想看看Booth's Algorithm（http://www.scribd.com/doc/3132888/Booths-Algorithm-Multiplication-Division）。

你想要的部分大約是頁面的1/2。

自從我的VLSI類以來，我還沒有看過這個，但是，這可能是你最好的選擇，如果可能的話，你可能想在彙編中做到這一點，儘可能優化它，如果你打電話給這個經常。

基本上涉及移位和增加或減少。

來源

2011-01-23 04:23:06

相關問題

 相關問題