分治アルゴリズムケース4:大整数乗算

大きな整数乗算による複素積の実現

x=a+biとy=c+diは2つの複素数(a,b,c,dはいずれもnビット整数とする)とする.蛮力アルゴリズムを用いて4回のnビット整数乗算を行い、積、すなわちxy=(ac-bd)+(ad+bc)iを計算する必要がある.3回のnビット整数乗算で積を計算するアルゴリズムを設計してください.

(1).アルゴリズム設計の構想の大数は乗算します:例えば1234、それを2つの部分に分割して、12と34、34の文字の長さlength=2を取得して、それから1234=12 x 10 length.再帰的な境界条件は,入力したデータの長さが1または2の場合,データが小さく,直接乗算して結果を得ることができる.データが大きいと、A,B,C,Dの2つの大きな数の2つの部分が取得されます.A,Cはそれぞれ10 lengthで割って2つの数の前半部を得,B,Dはそれぞれ10 lengthを型抜きして後半部を得た.2 x AC x 10 n＋m＋(A x 10 n−B)(D−Cx 10 m)＋2 x BDにより結果を導出した.ここでn,mはそれぞれB,Dの長さである.(異なる桁数の乗算が可能)
複素乗算:2つの複素数の実部と虚部を受信し、式(a+bi)(c+di)=ac-bd+[(a-b)+ac+bd]iから大数の乗算multiplyを呼び出してa x c、b x d、(a-b)x(d-c)の結果を得、複素数の積(2)を返す.アルゴリズム実装コード

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		int c = in.nextInt();
		int d = in.nextInt();
		System.out.println(multi(a,b,c,d));	}
	private static String multi(int a,int b,int c,int d) {
		/*
		 * (a+bi)(c+di) = ac-bd+[(a-b)(d-c)+ac+bd]i
		 */
		long ac = multiply(a,c);
		long bd = multiply(b,d);
		long xx = multiply((a-b),(d-c)) +ac+bd;
		//       ，   ，     +     ，        
		return xx > 0? ac-bd+"+"+xx+"i":ac-bd+""+xx+"i";
	}
	private static long multiply(long x,long y) {
		/*	  x = A | B		
		 *    y = C | D
		 */
		//  x B     ，y D     
		long n = String.valueOf(x).length() - String.valueOf(x).length()/2;
		long m = String.valueOf(y).length() - String.valueOf(y).length()/2;
		//        1 2 ，    
		if(String.valueOf(x).length()/2 == 1||String.valueOf(x).length()/2 == 0)
			return x*y;
		
		long A = (long) (x/Math.pow(10, n));//  A  
		long B = (long) (x%Math.pow(10, n));//  B  
		long C = (long) (y/Math.pow(10, m));//  C
		long D = (long) (y%Math.pow(10, m));//  D
		//        (A*10^n + B)(C*10^m + D) --> AC*10^(n+m) +AD*10^n +BC*10^m +BD
		//       :--->AC*10^(n+m) +(A*10^n -B)(D - C*10^m) +AC*10^(m+n) +BD +BD
		//			 --->2*AC*10^(n+m) +(A*10^n -B)(D - C*10^m) +2*BD
		long AC = (long) (2*multiply(A,C)*Math.pow(10, m+n));
		long BD = 2*multiply(B,D);
		long XX = multiply((long)(A*Math.pow(10, n)-B),(long)(D-C*Math.pow(10, m)));
		
		return AC+XX+BD;
		
	}
}

計算された2つの数はいずれもnビットであると仮定する.式から,n/2次整数の乗算,6次加減法,2次シフトを3回行うだけであることが分かった.T(n)=3 xT(n/2)+O(n)