a * b / c の計算

a * b / c の計算

特に困っているわけではないのですが、エレガントな方法が見つからないので質問します。

a,c は３２ビット、bは８ビット、0＜a≦cがわかっているとします。
このとき、８ビットの整数計算値 a * b / c を最大３２ビットの範囲で計算する方法、教えてください。
一応C言語で考えていますので、以下の＊＊＊の部分の具体的な計算方法がわかればうれしいです。

int a,c; // 32bit 符号付き整数
char b,d; // ８bit 符号付き整数
if(a<2^(32-8)) d = a * b /c;
else **** ←　この部分のプログラム

一応考えてみて、確信が持てない解は、
c = c/b; d = a/c;
です。気持としては、a,c が十分に大きいので、cで割る代わりにc/bで割ればよいという考えですが、
整数計算なので、本当にそれで合っているのか確信が持てない状態です。

No.1 回答者： stomachman 回答日時： 2017/04/16 22:35

ご質問にお書きの「確信が持てない解」だとどうなるか。

まず
　　q:= [c/b] ([ ] は切り捨て）
とする。すなわち
　　q=c/b-ε　　(0≦ε＜1)
である。これを使って
　　d := [a/q]
とすると
　　d = a/q - δ　　(0≦δ＜1)
つまり
　　d = a/(c/b-ε)-δ
である。
　このdが持つ誤差γ
　　γ= ab/c - d
が (0≦γ＜1)になって欲しい所だが、
　　γ = ab/c - a/(c/b-ε)+δ
　　= δ-εa(b^2)/(c(c-εb))
なので、0≒δ≪ε＜1の場合、γは負になりうる。つまり、このやり方で出した答dは間違っている可能性がある。

この回答へのお礼

回答ありがとうございます。
＞なので、0≒δ≪ε＜1の場合、γは負になりうる。つまり、このやり方で出した答dは間違っている可能性がある。
やっぱり。
a,c が十分に大きい（最低２４ビット）ので大丈夫かと思ったのですが・・・

「余りγが負になりうる」ということは、
　割る数[c/b]が切り捨てによりc/bより小さい値になることにより、
　商a/[c/b]がab/cより１以上大きくなってしまう場合がある
ということですね。

おかげ様で確信が持てない解ではダメなことがわかりましたので、本題である
＞else **** ←　この部分のプログラム
の回答、引き続きお待ちしています。
よろしくお願いします。

お礼日時：2017/04/17 10:56

No.2 回答者： stomachman 回答日時： 2017/04/20 12:25

2^31 ＞ c ≧ a ≧ 2^24

　　2^8 ＞ b ≧ 0
ということのようで。
　　S = (int)(c / 2^8)
　　T= (int)(a / S)
　　d1 = (int)(b * T / 2^8)
　　d2 = (int)(b * (T+1) / 2^8)
とやれば、d1, d2のどっちかは当たる。これを検算して決めたらどうか。すなわちd1 ≠ d2のとき、
　　U = (int)(a / 2^8)
として
　　vn = |dn*S/U-b| 　　(n=1,2)
が小さい方とか。エレガントには程遠いが。

No.3 ベストアンサー 回答者： stomachman 回答日時： 2017/04/20 16:33

No.2の判定の仕方はダメダメでした。

　　V =(int)(d2 * S / U)-b
　　V≧0 なら d=d1, さもなくば d=d2
というのだと良いと思うが、いや、まだ計算間違いしているかもしれないなー。

この回答へのお礼

回答ありがとうございます。
割る数ｃを2^8で割ったSにするときの切り捨ての影響を考慮してd1,d2の２つの解の候補にするというアイデア、理解できました。
まだ、検算部、正直、ついていけてないですが、とりあえずお礼、申し上げます。

本件、軽く考えていましたが、エレガントな方法、見つけるの結構大変ですね。
ありがとうございます。

お礼日時：2017/04/20 22:25