巨大な数の掛け算

本物のページはこちら→huge-number-multiply

Included page "huge-number-multiply" does not exist (create it now)

n桁の数字を、n/2桁に分割して解く。
2つの整数を

(1)
\begin{align} X=A2^{\frac{n}{2}}+B, Y=C2^{\frac{n}{2}}+D \end{align}

と書き、積を以下のように表現する

(2)
\begin{align} XY=(A2^{\frac{n}{2}}+B)(C2^{\frac{n}{2}}+D)\\ =AC2^{n}+(AD+BC)2^{\frac{n}{2}}+BD \end{align}

この場合には、n桁同士の掛け算をn/2桁の掛け算4つに分解していることになるので、必要な掛け算をT(n)とすると、

(3)
\begin{align} T(n)=4T(\frac{n}{2}) \end{align}

と書ける。
これを再帰的に代入していくと、

(4)
\begin{align} T(n)=4T(\frac{n}{2})=4^2T(\frac{n}{4})\\ =...=4^{log_{2}n}T(1)\\ =n^{log_{2}3}T(1)\\ =n^{2}T(1) \end{align}

となり、
1桁同士の掛け算を$n^{2}$回行うことになり、筆算するときみたいな単純な方法と同じ計算量になる。

サポートサイト Wikidot.com divide-and-conquer