跳至內容

除法算法

維基百科,自由的百科全書

除法器(除法算法)是一類算法。給定兩個整數 N(分子)和 D(分母),計算它們的和(或)餘數。其中某些算法可以通過人工手動計算,而另一些則需要依賴數字電路的設計或軟體。[1]

除法算法主要分為兩類:慢除法快除法。慢除法在每次迭代的過程中給出結果(商)的一位數字。慢除法包括復原法(restoring)、非復原法(non-restoring)和SRT除法等。快除法從商的一個近似估計開始,並且在每次迭代過程中產生有效位數為最終商的兩倍多的中間值。Newton-Raphson和GoldSchmidt屬於這一類。

為接下來的討論的方便,我們有以下標記:

其中

  • N = Numerator (divident) 即「分子」(被除數)
  • D = Denominator (divisor) 即「分母」(除數)

是輸入,而輸出是

  • Q = Quotient 即「商」
  • R = Remainder 即「餘數」

復原的除法器 (restoring)

非復原的除法器 (non-restoring)

SRT演算法的除法器

  1. ^ Division algorithm. Wikipedia. 2018-03-24 [2018-04-14]. (原始內容存檔於2019-08-18) (英語).