[VBA] 合同式を用いて除算の余りを求めるアルゴリズム

ベキ乗の除算の余りを求める手順

 たとえば VBA の Mod 演算子で $2^{100}$ を $13$ で割ったときの余りを求めようと思って

 Sub Residue()

  Dim x As Long

  Debug.Print x = 2 ^ 100 Mod 13

 End Sub

というようなマクロを実行するとオーバーフローとなってしまいます。$2^{100}$ という巨大数の演算が VBA の処理能力を遥かに超えてしまうからです。しかし数論の合同式を上手く活用すると、$a^k$ のような整数のベキ乗を除算したときの余りはたった数行のコードで計算させることができます。アルゴリズムの流れを確認するために、例として $5^8$ を $7$ で割ったときの余りを合同式で求めてみます。計算には合同式の基本公式
 
\[a\equiv b,\:\:c\equiv d\quad\Longrightarrow\quad ab\equiv cd\quad (\mathrm{mod}\:m)\]
を用います。
 
\[5\equiv 5\quad (\mathrm{mod}\:7)\]
はもちろん成り立ちます。両辺に $5$ を掛けると
 
\[5^2\equiv 25\equiv 4\quad (\mathrm{mod}\:7)\]
となります。以下同様に両辺に $5$ を掛け続けます。
 
\[\begin{align*}&5^3\equiv 20\equiv 6&\quad (\mathrm{mod}\:7)\\[6pt]
&5^4\equiv 30\equiv 2&\quad (\mathrm{mod}\:7)\\[6pt]
&5^5\equiv 10\equiv 3&\quad (\mathrm{mod}\:7)\\[6pt]
&5^6\equiv 15\equiv 1&\quad (\mathrm{mod}\:7)\\[6pt]
&5^7\equiv 5&\quad (\mathrm{mod}\:7)\\[6pt]
&5^8\equiv 25\equiv 4&\quad (\mathrm{mod}\:7)\end{align*}\]
 よって余りは $4$ となります。
 

合同式を用いて巨大数の割り算の余りを計算するマクロ

 上の方法で $a^k$ を除算したときの余りを計算するユーザー定義関数です。

 'a^k を m で割ったときの余りを計算します

 Function PMOD(a As Long, k As Long, m As Long)

  Dim i As Long, x As Long

  x = 1

  For i = 1 To k
   'x に a を掛けて m で割って余りを求めます
   x = a * x Mod m
  Next i

  PMOD = x

 End Function

 この関数をワークシートで使用するときは

=PMOD(a,k,m)

と入力します。たとえば $5^8$ を $7$ で割ったときの余りを計算させるときは

=PMOD(5,8,7)

と入力すると「4」が返ります。もっと大きな数で試してみましょう。 $2^{100}$ を $13$ で割ったときの余りを計算させてみます。

=PMOD(2,100,13)

と入力すると「3」が返ります。 ≫ VBA 数値計算トップページ

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。