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

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

ただいまの
回答率

90.49%

  • アーキテクチャ

    82questions

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

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

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 6
  • VIEW 6,277

strike1217

score 554

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

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

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

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

桁数が増えると割り算の演算速度が極端に遅くなる理由がわかりません。

以下のサイトを参考にしました。

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

ソフトウェアでの工夫

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

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

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

教えてください。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

checkベストアンサー

+16

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

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/02 17:21

    >乗算が高速化できるから相対的に遅くなってしまう
    そうなんですか!

    割り算が遅いわけではないんですね。

    キャンセル

  • 2017/03/02 17:59

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

    キャンセル

  • 2017/03/03 18:56

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

    キャンセル

  • 2017/03/03 18:59

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

    キャンセル

+4

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/02 17:21

    >「P≠NP予想」という数学における未解決問題の一つとなっています

    調べてみます。
    割り算が遅いのではないのですね!

    キャンセル

+2

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/02 17:24

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

    キャンセル

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 90.49%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • アーキテクチャ

    82questions

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