上一篇写的“[大整数乘法]分治算法的时间复杂度研究”，这一篇是基于上一篇思想的代码实现，以下是该文章的连接：
http://www.cnblogs.com/McQueen1987/p/3348426.html
代码主要实现大整数乘法，过程中也涉及到[大整数加法] 和 [大整数减法] 的计算，代码如下：
类1
————————————————————————————————————————————————————————————
package bigIntNum;
public class NumDividEqual {
public char[] A;
public char[] B;
int n;
/**
* 将数组均分为两份，分别存入数组A和数组B中；
* @param input
*/
public NumDividEqual(char[] input){
n = input.length/2;
A = new char[n];
B = new char[n];
for(int i = 0; i<n;i++){
A[i] = input[i];
}
for(int i = 0; i<n;i++){
B[i] = input[i + n];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
类2
————————————————————————————————————————————————————————————
package bigIntNum;
import java.util.Arrays;
public class bigIntMult {
/**
* 将字符数组倒序排列
* @param input
* @return
*/
public char[] reverse(char[] input) {
char[] output = new char[input.length];
for (int i = 0; i < input.length; i++) {
output[i] = input[input.length - 1 - i];
}
return output;
}
/**
* 将大整数平均分成两部分
* @param input
* @return
*/
public NumDividEqual partition(char[] input) {
return new NumDividEqual(input);
}
/**
* 求两数组中较大数组的长度，如果其长度为奇数则+1变偶
* @param num1
* @param num2
* @return
*/
public int calLength(char[] num1, char[] num2) {
int len = num1.length > num2.length ? num1.length : num2.length;
if (len == 1)
return 1;
len += len & 1;
return len;
}
/**
* 除去数字前面多余的0
* @param input
* @return
*/
public static char[] trimPrefix(char[] input) {
char[] ret = null;
for (int i = 0; i < input.length; i++) {
if (ret == null && input[i] == '0')
continue;
else {
if (ret == null) {
ret = new char[input.length - i];//出去数字前面多余的0
}
ret[i - (input.length - ret.length)] = input[i];
}
}
if (ret == null)
return new char[] { '0' };
return ret;
}
/**
* 数组如果长度不足n，则在数组前面补0，使长度为n。
* @param input 输入数组要求数字的最高位存放在数组下标最小位置
* @param n
* @return
*/
public static char[] format(char[] input, int n) {//；
if (input.length >= n) {
return input;
}
char[] ret = new char[n];
for (int i = 0; i < n - input.length; i++) {
ret[i] = '0';
}
for (int i = 0; i < input.length; i++) {
ret[n - input.length + i] = input[i];
}
return ret;
}
/**
* 大整数尾部补0。相当于移位，扩大倍数
* @param input
* @param n
* @return
*/
public char[] addTail(char[] input, int n) {//
char[] ret = new char[input.length + n];
for (int i = 0; i < input.length; i++) {
ret[i] = input[i];
}
for (int i = input.length; i < ret.length; i++) {
ret[i] = '0';
}
return ret;
}
/**
* 大整数加法
* @param num1
* @param num2
* @return
*/
public char[] add(char[] num1, char[] num2) {
int len = num2.length > num1.length ? num2.length : num1.length;
int carry = 0;//进位标识
num1 = format(num1, len);
num2 = format(num2, len);
char[] ret = new char[len + 1];
for (int i = len - 1; i >= 0; i--) {
int tmp = num1[i] + num2[i] - 96;
tmp += carry;
if (tmp >= 10) {
carry = 1;
tmp = tmp - 10;
} else {
carry = 0;
}
ret[len - i - 1] = (char) (tmp + 48);
}
ret[len] = (char) (carry + 48);//最后一次，最高位的进位
return trimPrefix(reverse(ret));
}
/**
* 大整数减法：
* @param num1 被减数，大整数乘法中只有一个减法(A+B)(C+D)-(AC+BD)=AC+BC>0,因此參數num1>num2且都为正
* @param num2 减数
* @return
*/
public static char[] sub(char[] num1, char[] num2) {
int lenMax = num1.length > num2.length ? num1.length : num2.length;
char[] newNum1 = Arrays.copyOf(format(num1, lenMax), lenMax);//字符串前面补0，使两串长度相同
char[] newNum2 = Arrays.copyOf(format(num2, lenMax), lenMax);
for(int i=0;i<lenMax;i++){//when num1-num2<0 return
if((newNum1[i]=='0' && newNum1[i]=='0') || newNum1[i] == newNum2[i]){//newNum1 is bigger;
continue;
}
else if(newNum1[i] < newNum2[i]){//不滿足參數num1>num2；
System.out.println("The Parameter in sub(A,B).A MUST Bigger Than B!");
System.exit(0);
}
else break;
}
for(int i=lenMax-1;i>=0;i--){
if(newNum1[i] < newNum2[i]){//result < 0
newNum1[i] = (char) (newNum1[i] + '0' + 10 - newNum2[i]);
newNum1[i-1] = (char) (newNum1[i-1] - 1);
}
else{
newNum1[i] = (char) (newNum1[i] + '0' - newNum2[i]);
}
}
return trimPrefix(newNum1);
}
/**
* 大整数乘法
* @param num1
* @param num2
* @return
*/
public char[] mult(char[] num1, char[] num2) {
char[] A, B, C, D, AC, BD, AjB, CjD, ACjBD, AjBcCjD, SUM;
int N = calLength(num1, num2);//求两数组中较大数组的长度，如果长度为奇数则+1变偶，方便二分成两部分
num1 = format(num1, N);//数组高位存整数的高位数；数字前面补0，使长度为n；
num2 = format(num2, N);
if (num1.length > 1) {
NumDividEqual nu1 = partition(num1);//将大整数平均分成两部分
NumDividEqual nu2 = partition(num2);
A = nu1.A;
B = nu1.B;
C = nu2.A;
D = nu2.B;
AC = mult(A, C);//分治求大整数乘法
BD = mult(B, D);
AjB = add(A,B);
CjD = add(C,D);
ACjBD = add(AC,BD);
AjBcCjD = mult(AjB, CjD);
char[] tmp1 = addTail(sub(AjBcCjD, ACjBD), N / 2);//尾部补0，相当于移位
char[] tmp2 = add(addTail(AC, N), BD);
SUM = add(tmp1, tmp2);
char[] test = trimPrefix(SUM);//除去结果前面多余的0
return test;
} else {
Integer ret = (num1[0] - 48) * (num2[0] - 48);
return ret.toString().toCharArray();
}
}
public static void main(String[] args) {
String st1 = "168746315641347979798";
String st2 = "164681654767446887797451316158";
char[] a = st1.toCharArray();
char[] b = st2.toCharArray();
bigIntMult bg = new bigIntMult();
char[] ret = bg.mult(a, b);
System.out.println(ret);
}
}
代码优化：
1.可以写个hash表，存储一些常见的乘法，从而避免每次都重复计算。比如9999x9999999，里面有重复的9x9计算，可以考虑hash表存储这些计算的结果，用到时直接查询结果，从而避免重复计算。
声明：代码是本人脑力劳动结果，请尊重他人劳动。转载注明出处！