質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アーキテクチャ

アーキテクチャとは、情報システム(ハードウェア、OS、アプリケーション、ネットワーク等)の設計方法、設計思想、設計思想に基づいて構築されたシステム構造をアーキテクチャと呼びます

Q&A

解決済

4回答

22331閲覧

現代のコンピュータってどうして割り算が苦手なのでしょうか??

strike1217

総合スコア651

アーキテクチャ

アーキテクチャとは、情報システム(ハードウェア、OS、アプリケーション、ネットワーク等)の設計方法、設計思想、設計思想に基づいて構築されたシステム構造をアーキテクチャと呼びます

6グッド

9クリップ

投稿2017/03/02 05:13

編集2017/03/02 05:16

掛け算と違って桁数が増えると割り算は遅くなる。

除算(割り算)も一番簡単で分かりやすい方法は、割り算の基本理念に基づいて、割られる数から割る数を引いていき、商が[1]以下になるまで何回引いたかをカウントする方法です。

2進数を右にSビット論理シフトすると、2-s倍すること(2sで割ること)に相当

現代のCPUには「割り算用の回路」が組み込まれているそうですが・・・
どこかで「200桁くらいの割り算をやるとかなりの年数がかかる」みたいな情報を見かけたことがあります。

#桁数が増えると割り算の演算速度が極端に遅くなる理由がわかりません。
以下のサイトを参考にしました。

実は足し算しかできない!?
あなたは論理演算がわかりますか?

#ソフトウェアでの工夫
C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか??
桁を減らし、回数を増やした方がはやくなるかな?と思いました。

1/(x-2)(x-5) → 1/3(1/x-5 - 1/x-2) みたいに?

面白いサイトを見つけましたので、載せておきます。
プログラムによる数値演算のベンチマーク

教えてください。

hsk, bracket_i, 5o5o_wagon, k_fujimoto, 7968, moc0311👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

ベストアンサー

乗算に関しては、Karatsuba法では半分の桁の掛け算を、4つではなく3つに減らすことができるので、「両方の桁数の積」より速く計算することができます(n桁×n桁の掛け算ででO(n^1.59)程度)し、3つの乗算のうち2つは並列実行できます。さらに桁数が増えれば、高速フーリエ変換を使ったアルゴリズムがあって、O(n log n)より少し大きいぐらいのオーダーで処理できます。

これに対して、除算の場合、「分けて計算する」という方法が使えないので、O(n^2)のオーダーから減らすことができません(「割る数の桁数に比例した処理」を「割られる数の桁数に比例した回数」だけ繰り返すことになります)。上の桁が決まらないと下の桁の計算に入れないので、並列実行にも向きません。

結論:除算が遅い、というより、乗算が高速化できるから相対的に遅くなってしまう

なお、「素因数分解で割る数を小さくする」というアイデアは、素因数分解の手間自体が莫大となるため、一般の数に対する割り算の高速化にはほぼ使えません(「素因数分解がおいそれとできない」ことそのものがRSA暗号の安全性の鍵となっている、というように、本質的に困難な問題です)。

投稿2017/03/02 05:40

編集2017/03/02 05:42
maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

strike1217

2017/03/02 08:21

>乗算が高速化できるから相対的に遅くなってしまう そうなんですか! 割り算が遅いわけではないんですね。
strike1217

2017/03/02 08:59

yubaさんのURLの「一般的にコンピュータの除算は、他の演算に比べて非常に遅いです。」 やはり、割り算自体が遅いというわけではないようですね。
tacsheaven

2017/03/03 09:56

もうすでに終わってるから余談ですが、除算を速くするために「予め除算結果のテーブルを用意していてそれを参照する」というのを、CPU レベルでやっています。 で……もうIT業界でははるか昔のこと(1994年10月ですから22年前)、Intel の Pentium プロセッサで、この表を誤ったために特定の除算の場合に結果が正しくない、というエラッタを出しました。世にいう「Pentium FDIV バグ」です。このときはまあいろいろ言われましたねえ…(当時のキャッチコピー、「Intel 入ってる」に引っかけてまあいろいろとパロディが…)
strike1217

2017/03/03 09:59

除算を速くするためのテーブルというものが存在するんですか!! なるほどです!
guest

0

もしかして極端に時間がかかる、とは、現代暗号である公開鍵暗号方式の基本となる、RSA 暗号における素因数分解の困難さにまつわる話でしょうか?

割り算が遅いのではなく、素因数分解に近道がない(解くための公式がないため、愚直に試すしかない)ことを示すものです。

※この「近道がない」ことはまだ数学的には証明されておらず、「P≠NP予想」という数学における未解決問題の一つとなっています。

投稿2017/03/02 05:34

tacsheaven

総合スコア13703

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

strike1217

2017/03/02 08:21

>「P≠NP予想」という数学における未解決問題の一つとなっています 調べてみます。 割り算が遅いのではないのですね!
guest

0

C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか??

桁を減らし、回数を増やした方がはやくなるかな?と思いました。

除算を高速化する工夫ということであればもっと効率的なものがあります。
整数の除算は、1回の乗算に変換することができるのです。
http://www.emit.jp/prog/prog_div.html
もちろん、その変換作業に除算が必要なのですが。

ということは、Cのプログラム上で除数が定数であれば、コンパイルの時点でこの乗算への変換作業をやってしまえば実行時の効率が上がります。
そして、ここまで言えば気付かれていることかもしれませんが、コンパイラにはまず間違いなくこの最適化が実装済みです。

投稿2017/03/02 08:14

yuba

総合スコア5568

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

strike1217

2017/03/02 08:24

整数除算の高速化のための最適化が備わっているのですね! ありがとうございます。
guest

0

C言語で割り算の桁が増えないように、割り算を複数回に分解して計算したら、速度は向上しますか??

桁を減らし、回数を増やした方がはやくなるかな?と思いました。

基本実行環境での測定(プロファイル)がいちばんの早道です。
また、下手に人間が最適化を行うよりも、コンパイラに任せるのが吉だと思います。
もちろん、大局的な最適化は人間が行った方が良いでしょうけれど。

投稿2017/03/02 06:56

t_obara

総合スコア5488

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問