C言語 a * b / c の計算

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

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

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

No.3 ベストアンサー 回答者： k-841 回答日時： 2017/04/22 04:34

決してエレガントではありませんが、a, cは正でありしかし符号付の型だという前提で a * b / c の整数の商を求めるのであれば、最初にa - cを求めて一時変数に代入しておき、bの数だけループし、ループ中に一時変数にaを加え、それがc以上になったらdを1加えて一時変数からcを引き去ることを繰り返せば、間違いなくすべての数値は32ビット以内に収まると思います。

CPUにALUしかない時代の発想で、歳がばれますね・・・

この回答へのお礼

回答ありがとうございます。
＞間違いなくすべての数値は32ビット以内に収まると思います
よさそうに思えますが、たとえば、
　a = 0x7F00,0000 c=0x7F00,0001 3<b のとき、
a-c, 2a-c まではOKですが、3a-cの計算段階でオーバーフローしてしまいませんか？

「ループ中に一時変数にaを加え、それがc以上になったらdを1加え」の部分は、
「ループ中に一時変数にaを加えてもそれがc以上にならないならaを加え、c以上になるならば(a-c)を加えてdを1加え」となり

if(x <(c-a)) {
　x += a;
} else {
　x += (a-c); d++;
}
とすればOKですね。

＞CPUにALUしかない時代の発想で、歳がばれますね・・・
回答に年齢には関係ないですよ。
本件、何気なく思いついた知的好奇心の道楽の質問ですが、意外と難しい、エレガントな解法が見つからないようです。
引き続き、何か思いついたら、よろしくお願いします。

お礼日時：2017/04/22 09:26

No.4 回答者： k-841 回答日時： 2017/04/22 23:27

No.3です。

ですから、それを「一時変数からcを引き去る」と表現したつもりです。お礼文に記載いただいたコードがまさにそれですね。

ところで、いわゆる「エレガントなコード」っていったい何なんでしょうね？ソースコードの短さは確かに可読性を向上させるという意味ではエレガントかもしれませんが、必ずしもコンピュータにとって最適化といわれるとそうではないと思います。
実際のところ、No.3の回答では最初からCを志向したアルゴリズムは考えていません（なので、敢えてコードは書かずに言葉だけで説明しました）。今も昔も、メモリアクセスと条件分岐（ループもそうです）は高コストのため、できるだけこれらを避けた方が短時間で演算ができます。現代では「ステップ数」がコーディングにおけるコストとみなされているのですが、この考え方が支配的だと、せっかく半導体技術やコンピュータアーキテクチャ技術が向上してもその性能を十分に引き出せないような気がして、とても残念に感じているのです。この辺が計算機工学とソフトウェア工学の対極する一面だと思いますが、私は計算機工学が専門だったので、どちらかというとそちら寄りの考えが強いようです。

この回答へのお礼

k-841 さん再度、回答ありがとうございます。

＞ですから、それを「一時変数からcを引き去る」と表現したつもりです。
＞お礼文に記載いただいたコードがまさにそれですね。
失礼しました。

＞ところで、いわゆる「エレガントなコード」っていったい何なんでしょうね？
正直なところわかりません。

今回の質問での「エレガントな方法」は、簡単な短い手順で解が得られ、結果ステップ数も処理時間も短くなるアルゴリズムといった感じでしょうか。わかりやすいというより、
あれ、何でこれで計算できるの？　といった意外性がある解を期待しています。
自分では思いつかない意外なアルゴリズムに出会えると、何となく嬉しくなるので質問しています。

とりあえず、
d = a / (c/b);
で求めたｄあるいはd-1 が求める値 [a * b /c]　になることまではわかっています。
２つのどちらが解なのかを判断するアルゴリズムで止まっています。

お礼日時：2017/04/23 00:42

No.2 回答者： Tacosan 回答日時： 2017/04/18 01:39

ざんねんながら「(long long)が３２＋８ビット以上という保証」はあるのだよ.

さておき, まあとりあえず上位 24ビットで処理してあとで補正, くらいかなぁ.

この回答へのお礼

Tacosanさん、今回も回答ありがとうございます。

＞ざんねんながら「(long long)が３２＋８ビット以上という保証」はあるのだよ.
本当だ！
----------
C99互換として、long long整数型が追加された。
この整数型は、64ビット以上の値を表現できる。
https://cpprefjp.github.io/lang/cpp11/long_long_ …
-----------

＞さておき, まあとりあえず上位 24ビットで処理してあとで補正, くらいかなぁ.
質問のメインはここです。
0＜a≦c、0<b の条件がうまく使って、何かエレガントな方法がありそうな気がしているのですが、思いつかないのです。
上位２４ビットではありませんが、私はとりあえず、
c = c/b; d = a/c;
でかなり近いｄが求まると考えたのですが、さて、ｃの切り捨てによる影響をどのように修正したらよいのか、悩んでいるところです。
もちろん、悩んでいるといっても楽しみ・趣味で悩んでいるのですけど・・・

お礼日時：2017/04/18 09:34

No.1 回答者： お茶碗持つ方 回答日時： 2017/04/17 18:03

多分気付かれてないバグ...

if(a<2^(32-8)) ...

をコンパイルすると

if(a<26) ...

となります。"^" 演算子はC言語の場合「排他的論理和 (xor)」です。恐らく、

if(a<(1<<(32-8))) ...

としたかったんだと思いますけど、こんな場合分けしなくても

d = (int)((long long)a * b / c);

の一行でいいのではないでしょうか? もし、オーバーフローの処理をしたいのであれば、

int a, c; // 32bit 符号付き整数
signed char b, d; // 8bit 符号付き整数
long long e; // 64bit 符号付き整数

e = (long long)a * b / c;
if(abs(e)<(1<<((sizeof(d)*8)-1))) d = (signed char)e;
else longjmp(OVERFLOW);

かな?

OVERFLOW はエラー処理の飛び先です。

この回答へのお礼

「お茶碗持つ方」さん、回答ありがとうございます。
https://oshiete.goo.ne.jp/qa/9714006.htmlでは、お世話になりました。

＞多分気付かれてないバグ...
ご指摘ありがとうございます。

＞こんな場合分けしなくても
＞d = (int)((long long)a * b / c);
＞の一行でいいのではないでしょうか?
　(long long)が３２＋８ビット以上という保証はありません
　「最大３２ビットの範囲」で計算するという題意に反します
という突っ込みもありますが、横に置いておいて、
初めに記したように、本件、特に困っているわけではありません。
知的好奇心の道楽におつきあいいただきたいだけです。

８ビットの整数計算値 a * b / c を「最大３２ビットの範囲」で計算する方法

が知りたいだけです。
よろしくお願いします。

お礼日時：2017/04/17 20:02