前言：
在數學上，關於帶符號整數的除法，大家一定不知道，其實有兩種的。第一種叫做 Symmetric Division，中文稱作「對稱除法」。第二種叫做 Floored Division，中文稱作「向下取整數除法」。
這兩種除法，當它們在正整數時沒什們分別。但用在負整數時，兩個就有一些差異囉。對稱除法常用在處理器上，而向下取整數除法則被廣泛的使用在各種不同的程式語言中。所以當接觸一個新的程式語言時，通常必須先搞清楚它們用的是對稱除法，還是向下取整數除法。否則會得到錯誤的結果。
然後是我們的Arduino的Flash FORTH，對於一些混合算術的計算指令，居然只提供了不帶符號的雙整數運算。一些 ANSI FORTH 標準所規定的指令都付之闕如。有一些筆者認為是還蠻常用且十分重要的，沒有了還蠻不方便的。所以來補上這塊空缺吧，讓我們把這些缺少的指令一一補上。同時也搞清楚何謂「對稱除法」(Symmetric Division) 跟「向下取整數除法」(Floored Division)。兩者的性質跟差異在哪裡，跟它們的邏輯到底是什麼。
對稱除法 (Symmetric Division) ：
其定義如下，
這裡 A 是被除數 (Dividend), B 是除數 (Divisor), Qm 是商, Rm 是餘數
(1) 當 A/B > 0 的時候， 這時候 Qm = A/B 後的數字向下(朝零)取整數。 例如如果 A/B = 2.756, 取整數後的結果會是 2
(2) 當 A=0 的時候，自然 A/B = 0/B = 0
(3) 當 A/B < 0 的時候，這時候 Qm = A/B 後的數字向上(朝零)取整數。例如如果 A/B = -2.756, 取整數後的結果會是 -2
除法一定要滿足它們最原始的數學定義關係式的: A = B*Q + R
所以商 Qm 求出來後，餘數等於 Rm = A-B*Qm
這裡用除數 B = 3 (Divisor) 來做範例，改變不同的被除數A (Dividend) 所作圖出來結果如下
這裡可以看得很清楚它的 Qm, Rm 對原點有對稱性，這也是對稱除法名稱的由來。
這種整數的除法大量被使用在一般的微處理器上面，原因是因為對稱性的關係，使得它的商不管是正數或是負數，結果只會差上一個負號。
舉例：
+45678 / 123 = +317
-45678 / 123 = -317
這樣的結果比較符合一般對數學的期待，除出來商的絕對數值應該跟正負號無關。-45678 / 123 * (-1) = 317 = 45678 /123。
但是問題來自於餘數，當被除數<0時，除數是正的，卻會跑出負數的餘數。除數跟餘數符號相反，在某些應用的狀況下，這會是個奇怪的結果。
(此種除法，餘數的符號會跟被除數相同)
向下取整數除法 (Floored Division)：
其定義如下，
這裡 A 是被除數 (Dividend), B 是除數 (Divisor), Qf 是商, Rf 是餘數
(1) 當 A不為零的時候， 這時候 Qm = A/B 後的數字向下(朝負無窮大)取整數。 例如如果 A/B = 2.756, 取整數後的結果會是 2。如果 A/B = -2.756, 取整數後的結果會是 -3。
(2) 當 A=0 的時候，自然 A/B = 0/B = 0
除法一定要滿足它們最原始的數學定義關係式的: A = B*Q + R
所以商 Qf 求出來後，餘數等於 Rf = A-B*Qf
這裡用除數 B = 3 (Divisor) 來做範例，改變不同的被除數A (Dividend) 所作圖出來結果如下
這裡可以看得很清楚它的 Qm 永遠向下(朝負無窮大)取整數，這是向下取整數除法 Floored Division 名稱的由來。
跟對稱除法不太一樣的，這個除法在被除數是正負的時候，結果會不太一樣。這時候再乘上負數時，兩個不會相等。
舉例：
+45678 / 123 = +317
-45678 / 123 = -318
這時候去掉正負號兩個並不會相等。-45678 / 123 * (-1) = 318 ，45678 /123 = 317， 兩個不相等！
這種除法的優點來自於餘數，當被除數<0時，除數是正的，餘數也會是正的。除數跟餘數符號永遠相同，在某些應用的狀況下，這會是個重要的使用需求。
(此種除法，餘數的符號會跟除數相同)
兩個除法間的關係式，
這兩個除法在 A/B < 0 的區域存在一個關係式，其結果可以相互轉換。
很容易驗證，只要將 Qm, Rm帶入如下的除法定義式，可以發現它們是相等的。
ANSI FORTH 的規範
關於算數運算， 規定要有下列指令
*/ (n1 n2 n3 -- n4)
比例算數縮放的指令，n4 = n1 * n2/n3，將 n1 以 n2/n3 的比例縮放。重點是中間會以雙整數來暫存結果，所以最後結果不會因為超過單整數的範圍而爆掉。
*/mod ( n1 n2 n3 -- nr nq)
比例算數縮放的指令且取餘數， nq = n1 * n2/n3，nr = 餘數。且中間會以雙整數來暫存結果，所以最後結果不會因為超過單整數的範圍而爆掉。
/mod ( n1 n2 -- nr nq)
取商跟餘數， nq = n1 / n2，nq = n1 - n2*nq
fm/mod ( d n -- nr nq)
向下取整數雙整數除法 (Floored Division)：對雙整數 d 為被除數，n 為除數，以向下取整數除法 Floored Division 取其單整數商 nq 跟單整數餘數 nr
sm/rem ( d n -- nr nq)
對稱雙整數除法 (Symmetric Division)：對雙整數 d 為被除數，n 為除數，以對稱除法 Floored Division 取其單整數商 nq 跟單整數餘數 nr
m* ( n1 n2 -- d)
混合乘法， d = n1 * n2 ，將兩單整數相乘，送回雙整數結果 d
m*/ ( d1 n1 n2 -- d2)
混合比例算數縮放的指令，將一個雙整數 d1 以兩個單整數所組成 n1/n2 的比例進行縮放。 所以 d2 = d1 * n1/n2
m/ ( d n1 -- n2)
混合除法， n2 = d/n1。將一個雙整數 d 除以單整數 n1 ，結果為單整數 n2。
um/mod ( ud u -- ur uq) - Arduino Flash FORTH 已內建
不帶符號混合除法：不帶符號雙整數對一單整數相除且取餘數。 uq = ud / u ， ur = ud - uq*u
um* ( u1 u2 -- ud) - Arduino Flash FORTH 已內建
不帶符號混合乘法：不帶符號兩單整數相乘，結果為不帶符號之雙整數。 ud = u1 * u2
這些指令，正常來說為了執行上的速度考量，應該用組合語言來進行撰寫。但如果為了轉移性，也可以用高階的 FORTH 語言來定義它們。
這麼多指令中，最重要的是 um/mod 及 um* 這兩個不帶符號的整數相除跟相乘，因為其他的所有指令都可以用這兩個基礎指令組合出來。
可能是因為這樣，所以 Flash FORTH 在 Arduino 上居然只提供了 um/mod 及 um* 這兩個基礎乘法指令。所以接下來，我們的目的就是要利用這兩個指令，把其他 ANSI FORTH 標準所規定的所有指令給完整的定義出來。(這次 m*/ m/ 這兩個指令暫時放棄，留到下一篇 BLOG)
正負號處理的技巧
兩個有符號數字的相乘或相除，必須在程式中實作大家所耳熟能詳的規則：
(+) (+) --> (+)
(+) (-) --> (-)
(-) (+) --> (-)
(-) (-) --> (+)
咦，這個似乎有點眼熟，好像在哪裡看過喲。呵呵，原來這跟邏輯運算裡面的互斥 xor 是一樣的！
False False --xor--> False
False True --xor--> True
True False --xor--> True
True True --xor--> False
在現今的程式語言系統裡面，我們習慣以2的補數來當當負數。2的補數就是把一個正的數字的所有 bit 反向後加一。所以當看到一個不管是 I8, I16, I32, I64的整數，只要這個整數的 MSB = 1 ，則這個一定是負數。
舉例，假如現在我們有兩個整數 n1, n2 試問他們相乘或相除後符號會是正的還是負的呢？
簡單，就 n1 n2 xor 就搞定囉，假如xor後的數字結果為正 (MSB=1) 則相乘或相除後結果為正。假如xor後的數字結果為負 (MSB=0) 則相乘或相除後結果為負。
這時候再利用好用的 ?negate (n1 n2 -- n3) 或是 ?dnegate (d1 n -- d2) 來根據剛剛 xor 的結果，對後面的最終結果給上正負號，這樣就全部搞定啦！
程式碼解說
混合乘法：給定 n1 n2 兩個整數相乘，得到雙整數結果 d
: m* ( n1 n2 -- d )
2dup xor >r 將n1 n2 xor 一下，得到相乘後的正負號
abs swap abs um* 將n1 n2取絕對值後相乘，得到相乘後的數值
r> ?dnegate 根據剛剛xor的正負號，賦予結果正確的正負號
;
對稱除法：給定雙整數被除數d ，單整數除數n，利用對稱除法求得單整數餘數r 跟商數q
: sm/rem ( d n -- r q )
2dup xor >r 將d-msb n xor 一下，得到相除後的正負號
over >r 將d-msb 暫存一下
abs >r
dabs r> um/mod 將d n取絕對值，計算相除後的餘數跟商
swap r> ?negate 根據d-msb，對餘數賦予正確的正負號
swap r> ?negate 根據剛剛xor的正負號，對商賦予正確的正負號
;
向下取整數除法：給定雙整數被除數d ，單整數除數n，利用向下取整數除法求得單整數餘數r 跟商數q
: fm/mod ( d n -- r q)
dup >r 將n暫存一下
sm/rem 對稱除法
r> over 0< 商小於零嗎？
if 商小於零
rot + Rf=Rm+B
swap 1- Qf=Qm-1
else drop then 商大於等於零
;
接下來是比例乘除 */ */mod 跟 /mod mod
這裡要說一下的， gFORTH 的除法/是採用向下取整數除法(Floored Division)的，所以全部 gFORTH 的除法都是向下取整數除法。
可是 Flash FORTH，經過測試它的除法/是採用對稱除法(Symmetric Division)。為了求一致性，所以我們的比例乘除一率採用對稱除法 sm/rem。
就核心採用 sm/rem 來運算，再把用不到的數字丟掉即可。
: */mod ( n1 n2 n3 -- r q )
>r m* r> sm/rem
;
: */ ( n1 n2 n3 -- n4 )
*/mod nip
;
: /mod ( n1 n2 -- n3 n4 )
>r s>d r> sm/rem
;
: mod ( n1 n2 -- n3 )
/mod drop
;
最後，原始程式碼列表：
\
\ Arduino Flash Forth Math ANSI Core
\ 2021.4.4 Frank Lin
\
: m* ( n1 n2 -- d )
2dup xor >r ( R:sign)
abs swap abs um* ( d R:sign)
r> ?dnegate
;
: sm/rem ( d n -- r q )
2dup xor >r ( R: sign)
over >r ( R: sign d-sign)
abs >r
dabs r> um/mod ( ur uq R: sign d-sign)
swap r> ?negate ( r-sign is by d-sign)
swap r> ?negate ( q-sign is by xor-sign)
;
: /mod ( n1 n2 -- n3 n4 )
>r s>d r> sm/rem
;
: mod ( n1 n2 -- n3 )
/mod drop
;
: */mod ( n1 n2 n3 -- r q )
>r m* r> sm/rem
;
: */ ( n1 n2 n3 -- n4 )
*/mod nip
;
\ Qf = Qm - 1
\ Rf = Rm + B
: fm/mod ( d n -- r q)
dup >r ( n)
sm/rem ( r q)
r> over 0< ( q<0?)
if ( r q n)
rot + ( q r')
swap 1-
else drop then
;
XXX
留言列表
