大数乘法

所谓大数相乘（Multiplication algorithm），就是指数字比较大，相乘的结果超出了基本类型的表示范围，所以这样的数不能够直接做乘法运算。这时候可以用小学学的乘法竖式累加模拟乘法，结果储存在数组中。时间复杂度为O(2)

算法分析

源码

package 高精度;

/**
 * https://www.bilibili.com/video/BV1LA411v7mt?p=3
 */
import java.util.Scanner;

public class multiply {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String a = in.next();
		String b = in.next();
		in.close();
		int total[] = new int[a.length() + b.length() + 1]; // 结果
		// 把最后一个数字存储到下标为一里
		int[] c = new int[a.length() + 1];
		int[] d = new int[b.length() + 1];
		// 字符串的反转
		for (int i = 0; i < a.length(); i++) {
			c[a.length() - i] = a.charAt(i) - '0'; // 321会变成数组中的0123形式
		}
		for (int j = 0; j < b.length(); j++) {
			d[b.length() - j] = b.charAt(j) - '0';
		}
		// 核心代码
		for (int i = 1; i <= a.length(); i++) {
			for (int j = 1; j <= b.length(); j++) {
				total[i + j - 1] += c[i] * d[j];
				total[i + j] += total[i + j - 1] / 10; // 所进的位数（不可用c[i]*d[j]/10）
				total[i + j - 1] %= 10; // 进位后还剩的

			}
		}
		int index = total.length - 1;
		while (total[index] == 0 && index > 1) // 这范围多调试，默认答案结尾为total[1]
			index--; // 把前面多于的零去掉
		for (int i = index; i >= 1; i--) {
			System.out.print(total[i]);
		}

	}

}