C LANGUAGE TECHNOLOGY

【C言語】べき乗と累乗を高速に計算

悩んでいる人

C言語でべき乗と累乗を高速に計算する方法を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

べき乗と累乗を高速に計算

\(a^n\)におけるべき乗と累乗の違いは以下になります.(本記事ではaとnを自然数と仮定します.)

  • べき乗:\(a^n\)(aをn - 1回乗算)
  • 累乗:\(a^n\)(nが自然数の場合)

べき乗と累乗の計算でaを繰り返し乗算する場合,上記のaのn乗ではn - 1回の乗算が必要になります.

つまり,計算量は \(\mathcal{O}(n)\)になります.

べき乗と累乗を高速に計算する方法では,乗算の回数を減らすことを目標とします.

その分,加算,ビット演算やシフト演算の回数は増えますが,一般的には乗算の方が処理時間が長いので,全体として高速に計算できることができます.

べき乗と累乗をpow関数で実装するコードを知りたいあなたはこちらからどうぞ.

C言語 べき乗
【C言語】pow関数と自作関数でべき乗,累乗,2乗の計算

こういった悩みにお答えします. こういった私から学べます. 目次1 べき乗,累乗,2乗とは1.1 2乗の自作コード1.2 累乗の自作コード1.3 べき乗の自作コード2 pow関数でべき乗の計算3 自作 ...

続きを見る

べき乗と累乗を高速に計算する方法は,仮想通貨の技術である暗号理論でよく利用されます.

仮想通貨のイーサリアムを知りたいあなたはこちらからどうぞ.

イーサリアム
元東大教員/アメリカ企業CTOから学ぶイーサリアム(Ethereum)

こういった私から学べます. 元東大教員/アメリカ企業CTOの私が,イーサリアム(Ethereum)について解説します. イーサリアムで取引,NFTの売買,ゲーム,プログラミングをしたいあなたにおすすめ ...

続きを見る

本記事では,コードを読みやすくするためにunsigned long型を採用していますが,べき乗と累乗の計算では算術オーバーフローが発生しやすいです.

C言語の任意精度算術ライブラリGMPを利用することで,算術オーバーフローを回避できます.

算術オーバーフローと回避方法を知りたいあなたはこちらからどうぞ.

C言語 算術オーバーフロー
【C言語】算術オーバーフローと回避方法

こういった悩みにお答えします. こういった私から学べます. 目次1 算術オーバーフロー2 整数オーバーフロー3 C言語で符号ありデータ型を使う理由4 符号エラー5 切り捨てエラー6 不完全な範囲チェッ ...

続きを見る

繰り返し2乗法(バイナリ法)

繰り返し2乗法(バイナリ法:binary method)とは,べき乗を高速に計算するアルゴリズムです.

\((a^{x})^2 = a^{2x}\)となる性質を利用します.

つまり,\(a^1\),\(a^2\),\(a^4\),...,の中で適切なものを選べば良いことがわかります.

例えば,\(a^9 = a^{8 + 1} = a^8 * a^1\)になります.

\(a^9\)をバイナリ法で計算すると以下のように4回の乗算になり,aを繰り返し8回乗算するより少ないことがわかります.

  • \(a^2 = a^1 * a^1\)
  • \(a^4 = a^2 * a^2\)
  • \(a^8 = a^4 * a^4\)
  • \(a^9 = a^8 * a^1\)

バイナリ法で\(a^n\)を求める計算量は\(\mathcal{O}(\log n)\)になります.

バイナリ法のコードは以下になります.

バイナリ法には,上位ビットから計算する右向きバイナリ法(left-to-right binary method)と下位ビットから計算する左向きバイナリ法(right-to-left binary method)があります.

右向きバイナリ法はleft2right_binary関数,左向きバイナリ法はright2left_binary関数になります.

実行結果は以下になります.

3行目の行末で「2 5」を入力したら,\(2^5 = 32\)と正しく計算できていることがわかります.

バイナリ法はサイドチャネル攻撃に弱いという欠点があります.

この理由として,コード\(n_i\)(nのi番目のビット)が1の時だけ発生する処理(28,45行目)があるので,終了までの処理時間が変わるからです.

nの値によって出力までの処理時間が変わるということは,サイドチャネル攻撃のタイミング攻撃によってnの値が露呈する恐れがあります.

モンゴメリべき乗法

モンゴメリべき乗法(Montgomery's ladder)は,バイナリ法とは異なり,サイドチャネル攻撃に強いアルゴリズムです.

この理由として,モンゴメリべき乗法では,nのi番目のビット\(n_i\)が1か0かで同等の計算を実行するからです.

モンゴメリべき乗法のコードは以下になります.

25~31行目で,ビットが1か0に関わらず同等の計算を行っていることがわかります.

実行結果は以下になります.

上記のモンゴメリべき乗法のコードは,サイドチャネル攻撃の中のキャッシュによるタイミング攻撃に対応していません.

キャッシュによりタイミング攻撃に対応したモンゴメリべき乗法の擬似コードはこちらにあります.

\(2^k\)-ary法

\(2^k\)-ary法は,\(a^2\),\(a^3\),\(a^4\),...,\(a^{{2^d} - 1}\)(dは自然数)の計算結果を配列(テーブル)に保持して利用することで,乗算の回数を減らすアルゴリズムです.

d = 3の場合の\(2^k\)-ary法のコードは以下になります.

実行結果は以下になります.

スライディングウィンドウ法

スライディングウィンドウ法(Sliding Window Method)は,\(2^k\)-ary法を拡張したもので,最長dビットの1または0が連続するビット列をウィンドウと定義して,まとめて計算するアルゴリズムです.

\(2^k\)-ary法とは異なり,スライディングウィンドウ法は\(a^3\),\(a^5\),\(a^7\),...,\(a^{{2^d} - 1}\)(dは自然数)の計算結果を配列(テーブル)に保持して利用します.

この理由は,1が連続するウィンドウの最下位ビットは必ず1(つまり奇数)になるためです.

0が連続するウィンドウの処理は,\(a = a^{2^d}\)を計算するのみです.(1が連続するウィンドウでも同様の処理を行います.)

d=3の場合のスライディングウィンドウ法を利用するコードは以下になります.

実行結果は以下になります.

まとめ

C言語でべき乗と累乗を高速に計算する方法を紹介しました.

具体的には,以下のアルゴリズムのコードを解説しました.

  • 繰り返し2乗法(バイナリ法)
  • モンゴメリべき乗法
  • \(2^k\)-ary法
  • スライディングウィンドウ法

べき乗と累乗における乗算の回数を減らせるので,確かめてみましょう.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , ,