a * b / c の計算
特に困っているわけではないのですが、エレガントな方法が見つからないので質問します。
a,c は32ビット、bは8ビット、0<a≦cがわかっているとします。
このとき、8ビットの整数計算値 a * b / c を最大32ビットの範囲で計算する方法、教えてください。
一応C言語で考えていますので、以下の***の部分の具体的な計算方法がわかればうれしいです。
int a,c; // 32bit 符号付き整数
char b,d; // 8bit 符号付き整数
if(a<2^(32-8)) d = a * b /c;
else **** ← この部分のプログラム
一応考えてみて、確信が持てない解は、
c = c/b; d = a/c;
です。気持としては、a,c が十分に大きいので、cで割る代わりにc/bで割ればよいという考えですが、
整数計算なので、本当にそれで合っているのか確信が持てない状態です。
No.3ベストアンサー
- 回答日時:
No.2の判定の仕方はダメダメでした。
V =(int)(d2 * S / U)-b
V≧0 なら d=d1, さもなくば d=d2
というのだと良いと思うが、いや、まだ計算間違いしているかもしれないなー。
回答ありがとうございます。
割る数cを2^8で割ったSにするときの切り捨ての影響を考慮してd1,d2の2つの解の候補にするというアイデア、理解できました。
まだ、検算部、正直、ついていけてないですが、とりあえずお礼、申し上げます。
本件、軽く考えていましたが、エレガントな方法、見つけるの結構大変ですね。
ありがとうございます。
No.2
- 回答日時:
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.1
- 回答日時:
ご質問にお書きの「確信が持てない解」だとどうなるか。
まず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 が十分に大きい(最低24ビット)ので大丈夫かと思ったのですが・・・
「余りγが負になりうる」ということは、
割る数[c/b]が切り捨てによりc/bより小さい値になることにより、
商a/[c/b]がab/cより1以上大きくなってしまう場合がある
ということですね。
おかげ様で確信が持てない解ではダメなことがわかりましたので、本題である
>else **** ← この部分のプログラム
の回答、引き続きお待ちしています。
よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「割る」と「割りかえす」の違い
-
eのマイナス無限大乗
-
30パーセントオフで371円だった...
-
楕円の円周の長さの計算の仕方...
-
面積から辺の長さを出す計算式
-
中学生の数学を習う順番に並べ...
-
10進法で時間の計算で30分が0.5...
-
分数の計算で分子が0になったら...
-
普及率の計算方法について
-
エクセル関数IFの解を再度、別...
-
袋のサイズから容量を計算する方法
-
2割負担の計算。
-
z=(x+y)lnyの偏微分を教えてく...
-
公共工事の現場管理費率(%)...
-
一個当たり15秒の製品を1時間で...
-
積分のエクセル計算式を教えて...
-
写真の積分計算を、1/6公式を使...
-
tan の区分求積法
-
EXCEL ゴールシークの関数?
-
パーセントの算出のしかたを教...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「割る」と「割りかえす」の違い
-
30パーセントオフで371円だった...
-
面積から辺の長さを出す計算式
-
分数の計算で分子が0になったら...
-
10進法で時間の計算で30分が0.5...
-
eのマイナス無限大乗
-
映画を1.3倍速で見た時の時間計...
-
中学生の数学を習う順番に並べ...
-
楕円の円周の長さの計算の仕方...
-
一個当たり15秒の製品を1時間で...
-
袋のサイズから容量を計算する方法
-
公共工事の現場管理費率(%)...
-
プール計算って何ですか?
-
ある物を作るのに3%材料が必要...
-
半径の計算方法を教えてください。
-
積分のエクセル計算式を教えて...
-
2割負担の計算。
-
青で囲んだやり方だと計算が合...
-
冪乗の計算について教えてください
-
2と3以外の素数は6の倍数±1です...
おすすめ情報