分治法の経典の問題——大きい整数の乗算
2つのnビットの大きい整数の乗算を行う有効なアルゴリズムを設計してください.
参考解答
XとYの両方がnビットの2進整数であるとして、それらの積XYを計算します.小学校で学んだ方法で積XYを計算するアルゴリズムを設計することができるが,計算手順が多すぎて効率が低いように見える.この方法は、2個当たり1桁の乗算または加算を1ステップ演算と見なす場合、O(n 2)ステップ演算をしてこそ、積XYを求めることができる.次に,より効率的な大整数積アルゴリズムを分治法で設計した.
図6-3大整数XとYのセグメント
図6−3に示すように、nビットのバイナリ整数XとYをそれぞれ2セグメントに分け、各セグメントの長さはn/2ビット(単純化のため、nを2のべき乗と仮定する)である.
これにより、X=A 2 n/2+B、Y=C 2 n/2+Dとなる.このように、XとYの積は、
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)
式(1)でXYを計算すると,n/2ビットの整数の乗算(AC,AD,BC,BD)を4回,nビットを超えない整数の加算(式(1)のプラス記号にそれぞれ対応)を3回,シフト(式(1)の2 nと2 n/2にそれぞれ対応)を2回行う必要がある.これらの加算とシフトはすべてO(n)ステップ演算を共用する.T(n)を2つのnビット整数に乗算するために必要な演算総数とすると、式(1)により、
(2)
これによりT(n)=O(n 2)となる.したがって,(1)式でXとYの積を計算することは小学生の方法よりも有効ではない.アルゴリズムの計算の複雑さを改善するには,乗算回数を減らす必要がある.そのため、XYを別の形式に書きます.
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)
式(3)は式(1)より複雑に見えるが,n/2ビット整数の乗算(AC,BDおよび(A−B)(D−C))を3回,加算,減算,および2回シフトするだけである.これにより、
(4)
再帰方程式を解くスイート式法を用いて,T(n)=O(nlog 3)=O(n 1.59)とすぐに解くことができる.式(3)を用い,結果に及ぼすXとYの符号の影響を考慮して,大整数乗算の完全アルゴリズムMULTを以下のように与えた.
上記の2進数大整数乗算は、乗算の効率を向上させ、乗算回数を減少させるために、10進数大整数の乗算にも適用することができる.次の例では、アルゴリズムの計算プロセスを示します.
X=314 l、Y=5327とし、上記のアルゴリズムでXYを計算する計算過程を以下のようにリストすることができる.ここで、'番号付きの数値は、AC、BD、および(A-B)(D-C)の計算が完了した後に記入される.
X=3141 A=31 B=41 A-B=-10
Y=5327 C=53 D=27 D-C=-26
AC=(1643)'
BD=(1107)'
(A-B)(D-C)=(260)'
XY=(1643)'104+[(1643)'+(260)'+(1107)']102+(1107)'
=(16732107)'
A=31 A1=3 B1=1 A1-B1=2
C=53 C1=5 D1=3 D1-C1=-2
A1C1=15 B1D1=3 (A1-B1)(D1-C1)=-4
AC=1500+(15+3-4)10+3=1643
B=41 A2=4 B2=1 A2-B2=3
D=27 C2=2 D2=7 D2-C2=5
A2C2=8 B2D2=7 (A2-B2)(D2-C2)=15
BD=800+(8+7+15)10+7=1107
|A-B|=10 A3=1 B3=0 A3-B3=1
|D-C|=26 C3=2 D3=6 D3-C3=4
A3C3=2 B3D3=0 (A3-B3)(D3-C3)=4
(A-B)(D-C)=200+(2+0+4)10+0=260
大きな整数を3つまたは4つに分けて乗算すると、計算の複雑さはどのように変化しますか?2段に分かれた乗算より優れていますか?この問題はみんなで考えてください.
コードの実装
/****************************************************************************//関数機能:分治法2つのNが整数の積を求める//入力パラメータ:X,Yはそれぞれ2つのNが整数//アルゴリズム思想://時間複雑度:T(n)=O(nlog 3)=O(n 1.59)/************************************************************************************************************************************************************************************************************************************************************************************************************************************************1 : -1) int IntegerMultiply(int X, int Y, int N) { int sign = SIGN(X) * SIGN(Y); int x = abs(X); int y = abs(Y); if((0 == x) || (0 == y)) return 0; if (1 == N) return x*y; else { int XL = x/(int)pow(10., (int)N/2); int XR = x - XL * (int)pow(10., N/2); int YL = y/(int)pow(10., (int)N/2); int YR = y - YL * (int)pow(10., N/2); int XLYL = IntegerMultiply(XL, YL, N/2); int XRYR = IntegerMultiply(XR, YR, N/2); int XLYRXRYL = IntegerMultiply(XL - XR, YR - YL, N/2) + XLYL + XRYR; return sign * (XLYL * (int)pow(10., N) + XLYRXRYL * (int)pow(10., N/2) + XRYR); } } int _tmain(int argc, _TCHAR* argv[]) { int x = 1234; int y = 4321; cout<<"x * y = "<
参考解答
XとYの両方がnビットの2進整数であるとして、それらの積XYを計算します.小学校で学んだ方法で積XYを計算するアルゴリズムを設計することができるが,計算手順が多すぎて効率が低いように見える.この方法は、2個当たり1桁の乗算または加算を1ステップ演算と見なす場合、O(n 2)ステップ演算をしてこそ、積XYを求めることができる.次に,より効率的な大整数積アルゴリズムを分治法で設計した.
図6-3大整数XとYのセグメント
図6−3に示すように、nビットのバイナリ整数XとYをそれぞれ2セグメントに分け、各セグメントの長さはn/2ビット(単純化のため、nを2のべき乗と仮定する)である.
これにより、X=A 2 n/2+B、Y=C 2 n/2+Dとなる.このように、XとYの積は、
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)
式(1)でXYを計算すると,n/2ビットの整数の乗算(AC,AD,BC,BD)を4回,nビットを超えない整数の加算(式(1)のプラス記号にそれぞれ対応)を3回,シフト(式(1)の2 nと2 n/2にそれぞれ対応)を2回行う必要がある.これらの加算とシフトはすべてO(n)ステップ演算を共用する.T(n)を2つのnビット整数に乗算するために必要な演算総数とすると、式(1)により、
(2)
これによりT(n)=O(n 2)となる.したがって,(1)式でXとYの積を計算することは小学生の方法よりも有効ではない.アルゴリズムの計算の複雑さを改善するには,乗算回数を減らす必要がある.そのため、XYを別の形式に書きます.
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)
式(3)は式(1)より複雑に見えるが,n/2ビット整数の乗算(AC,BDおよび(A−B)(D−C))を3回,加算,減算,および2回シフトするだけである.これにより、
(4)
再帰方程式を解くスイート式法を用いて,T(n)=O(nlog 3)=O(n 1.59)とすぐに解くことができる.式(3)を用い,結果に及ぼすXとYの符号の影響を考慮して,大整数乗算の完全アルゴリズムMULTを以下のように与えた.
function MULT(X，Y，n); {X Y 2 2n ， X Y XY}
begin
S:=SIGN(X)*SIGN(Y); {S X Y }
X:=ABS(X);
Y:=ABS(Y); {X Y }
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A:=X n/2 ;
B:=X n/2 ;
C:=Y n/2 ;
D:=Y n/2 ;
ml:=MULT(A,C,n/2);
m2:=MULT(A-B,D-C,n/2);
m3:=MULT(B,D,n/2);
S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;上記の2進数大整数乗算は、乗算の効率を向上させ、乗算回数を減少させるために、10進数大整数の乗算にも適用することができる.次の例では、アルゴリズムの計算プロセスを示します.
X=314 l、Y=5327とし、上記のアルゴリズムでXYを計算する計算過程を以下のようにリストすることができる.ここで、'番号付きの数値は、AC、BD、および(A-B)(D-C)の計算が完了した後に記入される.
X=3141 A=31 B=41 A-B=-10
Y=5327 C=53 D=27 D-C=-26
AC=(1643)'
BD=(1107)'
(A-B)(D-C)=(260)'
XY=(1643)'104+[(1643)'+(260)'+(1107)']102+(1107)'
=(16732107)'
A=31 A1=3 B1=1 A1-B1=2
C=53 C1=5 D1=3 D1-C1=-2
A1C1=15 B1D1=3 (A1-B1)(D1-C1)=-4
AC=1500+(15+3-4)10+3=1643
B=41 A2=4 B2=1 A2-B2=3
D=27 C2=2 D2=7 D2-C2=5
A2C2=8 B2D2=7 (A2-B2)(D2-C2)=15
BD=800+(8+7+15)10+7=1107
|A-B|=10 A3=1 B3=0 A3-B3=1
|D-C|=26 C3=2 D3=6 D3-C3=4
A3C3=2 B3D3=0 (A3-B3)(D3-C3)=4
(A-B)(D-C)=200+(2+0+4)10+0=260
大きな整数を3つまたは4つに分けて乗算すると、計算の複雑さはどのように変化しますか?2段に分かれた乗算より優れていますか?この問題はみんなで考えてください.
コードの実装
/****************************************************************************//関数機能:分治法2つのNが整数の積を求める//入力パラメータ:X,Yはそれぞれ2つのNが整数//アルゴリズム思想://時間複雑度:T(n)=O(nlog 3)=O(n 1.59)/************************************************************************************************************************************************************************************************************************************************************************************************************************************************1 : -1) int IntegerMultiply(int X, int Y, int N) { int sign = SIGN(X) * SIGN(Y); int x = abs(X); int y = abs(Y); if((0 == x) || (0 == y)) return 0; if (1 == N) return x*y; else { int XL = x/(int)pow(10., (int)N/2); int XR = x - XL * (int)pow(10., N/2); int YL = y/(int)pow(10., (int)N/2); int YR = y - YL * (int)pow(10., N/2); int XLYL = IntegerMultiply(XL, YL, N/2); int XRYR = IntegerMultiply(XR, YR, N/2); int XLYRXRYL = IntegerMultiply(XL - XR, YR - YL, N/2) + XLYL + XRYR; return sign * (XLYL * (int)pow(10., N) + XLYRXRYL * (int)pow(10., N/2) + XRYR); } } int _tmain(int argc, _TCHAR* argv[]) { int x = 1234; int y = 4321; cout<<"x * y = "<