可以的話都要避免
而對於整數的常數除法，有一些方法可以用乘法代換掉
想法很簡單，既然是整數的話只要足夠近似就行了
例如在 gcc 裡面，以下這個東西編譯出來的組合語言相當於 (x*3435973837)>>35
echo "unsigned int f(unsigned int x){return x/10;}" | g++ -S -xc - -o -
主要參考了 libgmp 大數運算 library 的文件
1. 問題定義
以下用 <, <=, >, >=, ^ 符號表示小於、小於等於、大於、大於等於、次方首先我們都知道我們的被除數的範圍，所以我們的問題定義變成：
Given a divisor d
Does there exist a multiplier m and a positive number l
such that floor(nm / (2^(N+l))) = floor(n/d)
for all n, 0 <= n < 2^N?
為了表示方便
我們多定義以下符號
n = qd+r, where q = floor(n/d), so 0 <= r < d
我們的問題定義可以改寫如下
0 <= nm/(2^(N+l)) -q < 1 for all n, 0 <= n < 2^N?
2. 推導
先觀察左邊的不等式，我們這樣變化
0 <= nm/(2^(N+l)) - q
0 <= nmd/(2^(N+l)) - dq
0 <= nmd/(2^(N+l)) - (dq+r) + r
0 <= nmd/(2^(N+l)) - n + r
0 <= n(md/(2^(N+l)) - 1) + r
因為等式裡面有 q 就很難下手，所以就把他乘以 d，並且變成 n
因為 r 恆正，所以 n 後面乘的那串 >=0 就是等式成立的充分條件
md/(2^(N+l)) - 1 >= 0
md >= 2^(N+l)
右邊類似
nm/(2^(N+l)) - q < 1
nmd/(2^(N+l)) - (qd+r) < d-r
n(md/(2^(N+l)) - 1) < d-r
我們知道 d-r >= 1
所以下面這個是充分條件
n(md/(2^(N+l)) - 1) < 1
又 n < 2^N 所以繼續放寬，下面這個也是充分條件
(md/(2^(N+l)) - 1) <= 2^(-N)
左右移項之後
md <= 2^(N+l)+2^(N)
結合兩個式子，我們需要的條件就是
2^(N+l) <= md <= 2^(N+l)+2^(l)
只要滿足這個條件，就可以用 floor(nm/2^(N+l)) 代替 floor(n/d)
我們重新比對 gcc 產生的 x/10 變成 (x*3435973837)>>35
N = 32
l = 3
d = 10
m = 3435973837
34359738368 = (2^35) <= 10*3435973837 <= (2^35) + (2^3) = 34359738376
嗯，真的滿足
3. 如何找 m
原來的文件中為了某些需求
不找 2^(N+l) = md 的（也要 d 是 2 的冪次才找的到）
我們也比照辦理
給定 N, d 的時候要如何找到滿足要求的 l, m 呢？
一個簡單的方法是從 l = 0 往上找
如果不等式的範圍內有 d 的倍數那就是了
另外有一個方法是當 l = ceil(log2(d))
不等式裡面有 2^l >= d 個數字，這個區間一定有 d 的倍數
而且 m = floor((2^(N+l))/d) + 1 （大於 2^(N+l) 被 d 整除的最小倍數）
d>1 的情形下
因為 2^(l-1) < d <= 2^l
所以 2^N < m < 2^(N+1)
這個很重要，因為電腦中的乘法寬度是固定的
而 m 只比原本多了一個 bit，非常實用
沒有留言:
張貼留言