エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント1件
- 注目コメント
- 新着コメント
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
11章 数論的アルゴリズム
2.べき乗 pnの計算 べき乗計算のためのアルゴリズムを素直に書けば、以下のようになる。 w=1 for i=... 2.べき乗 pnの計算 べき乗計算のためのアルゴリズムを素直に書けば、以下のようになる。 w=1 for i=1 to n w=w*p next i print w もちろん、これでまちがっていない。 しかし、このアルゴリズムの処理時間はnの値に比例する。 従って、nが極端に大きい場合、例えば、n=10100のような場合には、完全にお手上げである。 このループの回数を減らす方法を考える。 例えば、2100の計算を考えてみる。 上のやり方なら、掛算を100回やらなければならない。 しかし、 2100=(250)2 であるから、250を上の方法で計算してやると、掛算回数は50回。 よって、2100は51回の掛算回数で求められる。 これは、最初の100回に比べて、ほぼ半分の回数である。 ならば、250自体についても同じようにやってみる。 250=(225)2 だから、掛算回数は、27回となる。
2009/02/22 リンク