![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
特に困っているわけではないのですが、エレガントな方法が見つからないので質問します。
a,c は32ビット、bは8ビット、0<a≦c、0<b がわかっているとします。
このとき、8ビットの整数計算値 a * b / c を「最大32ビットの範囲」で計算する方法、教えてください。
一応C言語で考えていますので、以下の***の部分の具体的な計算方法がわかればうれしいです。
int a,c; // 32bit 符号付き整数
signed char b,d; // 8bit 符号付き整数
if(a<2^(32-8)) d = a * b /c;
else **** ← この部分のプログラム
No.3ベストアンサー
- 回答日時:
決してエレガントではありませんが、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しかない時代の発想で、歳がばれますね・・・
回答に年齢には関係ないですよ。
本件、何気なく思いついた知的好奇心の道楽の質問ですが、意外と難しい、エレガントな解法が見つからないようです。
引き続き、何か思いついたら、よろしくお願いします。
No.4
- 回答日時:
No.3です。
ですから、それを「一時変数からcを引き去る」と表現したつもりです。お礼文に記載いただいたコードがまさにそれですね。
ところで、いわゆる「エレガントなコード」っていったい何なんでしょうね?ソースコードの短さは確かに可読性を向上させるという意味ではエレガントかもしれませんが、必ずしもコンピュータにとって最適化といわれるとそうではないと思います。
実際のところ、No.3の回答では最初からCを志向したアルゴリズムは考えていません(なので、敢えてコードは書かずに言葉だけで説明しました)。今も昔も、メモリアクセスと条件分岐(ループもそうです)は高コストのため、できるだけこれらを避けた方が短時間で演算ができます。現代では「ステップ数」がコーディングにおけるコストとみなされているのですが、この考え方が支配的だと、せっかく半導体技術やコンピュータアーキテクチャ技術が向上してもその性能を十分に引き出せないような気がして、とても残念に感じているのです。この辺が計算機工学とソフトウェア工学の対極する一面だと思いますが、私は計算機工学が専門だったので、どちらかというとそちら寄りの考えが強いようです。
k-841 さん再度、回答ありがとうございます。
>ですから、それを「一時変数からcを引き去る」と表現したつもりです。
>お礼文に記載いただいたコードがまさにそれですね。
失礼しました。
>ところで、いわゆる「エレガントなコード」っていったい何なんでしょうね?
正直なところわかりません。
今回の質問での「エレガントな方法」は、簡単な短い手順で解が得られ、結果ステップ数も処理時間も短くなるアルゴリズムといった感じでしょうか。わかりやすいというより、
あれ、何でこれで計算できるの? といった意外性がある解を期待しています。
自分では思いつかない意外なアルゴリズムに出会えると、何となく嬉しくなるので質問しています。
とりあえず、
d = a / (c/b);
で求めたdあるいはd-1 が求める値 [a * b /c] になることまではわかっています。
2つのどちらが解なのかを判断するアルゴリズムで止まっています。
No.2
- 回答日時:
ざんねんながら「(long long)が32+8ビット以上という保証」はあるのだよ.
さておき, まあとりあえず上位 24ビットで処理してあとで補正, くらいかなぁ.
Tacosanさん、今回も回答ありがとうございます。
>ざんねんながら「(long long)が32+8ビット以上という保証」はあるのだよ.
本当だ!
----------
C99互換として、long long整数型が追加された。
この整数型は、64ビット以上の値を表現できる。
https://cpprefjp.github.io/lang/cpp11/long_long_ …
-----------
>さておき, まあとりあえず上位 24ビットで処理してあとで補正, くらいかなぁ.
質問のメインはここです。
0<a≦c、0<b の条件がうまく使って、何かエレガントな方法がありそうな気がしているのですが、思いつかないのです。
上位24ビットではありませんが、私はとりあえず、
c = c/b; d = a/c;
でかなり近いdが求まると考えたのですが、さて、cの切り捨てによる影響をどのように修正したらよいのか、悩んでいるところです。
もちろん、悩んでいるといっても楽しみ・趣味で悩んでいるのですけど・・・
No.1
- 回答日時:
多分気付かれてないバグ...
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)が32+8ビット以上という保証はありません
「最大32ビットの範囲」で計算するという題意に反します
という突っ込みもありますが、横に置いておいて、
初めに記したように、本件、特に困っているわけではありません。
知的好奇心の道楽におつきあいいただきたいだけです。
8ビットの整数計算値 a * b / c を「最大32ビットの範囲」で計算する方法
が知りたいだけです。
よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# C言語 プログラミング 4 2022/05/22 11:53
- C言語・C++・C# C言語階乗の総和を求める 2 2023/03/04 23:31
- C言語・C++・C# このプログラミング誰か教えてくれませんか 1 2022/06/02 15:27
- C言語・C++・C# C言語でファクト関数を使わずに階乗を計算する方法はありますか?できれば教えてください 4 2023/06/07 11:45
- その他(自然科学) 科学技術計算の仕事について 2 2023/02/04 18:09
- 数学 数学I 因数分解について 因数分解の答えが (c-b)(a-b)(a-c)となりましたが、解答では輪 7 2023/04/06 14:38
- Excel(エクセル) Excel(エクセル)でフィルター抽出後、非表示の行を計算しないで、合計を算出する方法 【内容】 添 4 2023/01/30 17:17
- Visual Basic(VBA) vba 等間隔の列に対しての計算 6 2022/05/17 20:15
- 数学 パーセントの計算 増減 5 2023/08/01 22:39
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
プログラムで関数は使わない方...
-
UWSCにてある一定の動作を無限...
-
PHPの否定文
-
if文の中にfor文なのか、for文...
-
超初心者です。HowTo本"独習C"...
-
break文でループを一気に抜ける...
-
整定時間
-
プログラミングで質問です。言...
-
制御に関するプログラム
-
C言語 a * b / c の計算
-
どうしてもわからないC言語の問題
-
プログラムの解説をお願いします。
-
c言語のリダイレクトによる円...
-
吸湿性のあるものを天秤で秤量...
-
2÷3などの余りについて
-
プログラミング初心者です。 Py...
-
printf で二進表示を行いたい。
-
マイナスからプラスへ転じた時...
-
【C言語教えてください】sin波...
-
O(n log n)について2
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
break文でループを一気に抜ける...
-
入力した文字列から母音だけを...
-
ループを途中で抜けたいのですが。
-
do-while文が禁止される理由
-
入力した数値を倍々するプログラム
-
C言語forループが完結した場合...
-
if文の中にfor文なのか、for文...
-
プログラミングC言語についての...
-
エクセルVBAで Do While (1)って?
-
For文の終了値を関数にしても問...
-
エクセルでC言語のfor文と同じ...
-
Delphiで・・・
-
ループの特定入力終了
-
UWSCにてある一定の動作を無限...
-
C言語、自己参照構造体のプログ...
-
C言語 数字を削除する関数
-
Excel VBAで年度をまたぐ期間の...
-
プログラムで関数は使わない方...
-
Cプログラムが終了しない
-
VBScriptでSQLに接続し、CSV出...
おすすめ情報