大きな整数の場合
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/26 11:07 UTC 版)
「除算 (デジタル)」の記事における「大きな整数の場合」の解説
ハードウェアの実装に使われている設計技法は、一般に数千桁から数百万桁の十進数値での除算（任意精度演算）には適していない。そのような除算は例えば、RSA暗号の合同式の計算などでよく見られる。大きな整数での効率的除算アルゴリズムは、まず問題をいくつかの乗算に変換し、それに漸近的に効率的な（つまり桁数が大きいほど効率がよい）乗算アルゴリズム（英語版）を適用する。例えば、トム・クック乗算（英語版）やショーンハーゲ・ストラッセン法がある。乗算への変換としては、上述したニュートン法を使った例や、それより若干高速な Barrett reduction アルゴリズムがある。ニュートン法は同じ除数で複数の被除数に対して除算を行う場合に特に効率的で、除数の逆数を1度計算しておくと、毎回それを流用できる。
※この「大きな整数の場合」の解説は、「除算 (デジタル)」の解説の一部です。
「大きな整数の場合」を含む「除算 (デジタル)」の記事については、「除算 (デジタル)」の概要を参照ください。
ウィキペディア小見出し辞書の「大きな整数の場合」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 大きな整数の場合のページへのリンク
