长沙免费建站网络营销,长春网站建设联系吉网传媒优,织梦网站如何做软件下载,做网站原型图是用什么软件解决算法;
* 1. 模拟小学乘法#xff1a;最简单的乘法竖式手算的累加型#xff1b;
* 2. 分治乘法#xff1a;最简单的是Karatsuba乘法#xff0c;一般化以后有Toom-Cook乘法#xff1b;
* 3. 快速傅里叶变换FFT#xff1a;#xff08;为了避免精度问题#xff0c;可…解决算法;
* 1. 模拟小学乘法最简单的乘法竖式手算的累加型
* 2. 分治乘法最简单的是Karatsuba乘法一般化以后有Toom-Cook乘法
* 3. 快速傅里叶变换FFT为了避免精度问题可以改用快速数论变换FNTT时间复杂度O(N lgN lglgN)。具体可参照Schönhage–Strassen algorithm
* 4. 中国剩余定理把每个数分解到一些互素的模上然后每个同余方程对应乘起来就行
* 5. Furer’s algorithm在渐进意义上FNTT还快的算法。不过好像不太实用本文就不作介绍了。大家可以参考维基百科Fürer’s algorithm
参考地址https://blog.csdn.net/u010983881/article/details/77503519 1. 小学乘法代码如下
/*** 模拟小学乘法*/public static String primaryMul(String str1, String str2){System.out.println(start primaryMul param str1 , str2 ;time System.currentTimeMillis());int[] int1 string2IntArray(str1);int[] int2 string2IntArray(str2);ListInteger result new ArrayList();for (int i int1.length-1; i 0 ; i--) {ListInteger tempList new ArrayList();int ten 0;for (int j int2.length-1; j 0 ; j--) {int a int1[i] * int2[j] ten;ten a / 10;tempList.add(a % 10);}if (ten 0){tempList.add(ten);}//两行相加int carry 0;for (int j 0; j tempList.size(); j) {int r1 0;int index j (int1.length-1-i);if (index 0 | result.size() index){r1 result.get(index);}int a tempList.get(j) r1 carry;carry a / 10;if (index 0 | result.size() index){result.set(index, a % 10);}else{result.add(a % 10);}}if (carry 0){result.add(carry);}}//方向旋转int copy;for (int i 0; i result.size(); i) {if (i result.size() / 2){copy result.get(i);int index result.size() -1 -i;result.set(i, result.get(index));result.set(index, copy);}}StringBuilder sb new StringBuilder();for (Integer integer : result) {sb.append(integer);}System.out.println(end primaryMul result sb ;time System.currentTimeMillis());return sb.toString();}public static int[] string2IntArray(String str){String[] strs str.split();int[] ret new int[strs.length];for (int i 0; i strs.length; i) {ret[i] Integer.parseInt(strs[i]);}return ret;}
2. 小学算法-累加算法 /*** 模拟小学乘法 - 累加算法*/private static String accumul(String str1, String str2){System.out.println(start accumul param str1 , str2 ;time System.currentTimeMillis());int[] int1 string2IntArray(str1);int[] int2 string2IntArray(str2);int[] result new int[int1.length int2.length];for (int i 0; i int1.length; i) {for (int j 0; j int2.length; j) {result[i j 1] int1[i] * int2[j];}}for (int i result.length - 1; i 0; i--) {if (result[i] 10){result[i-1] result[i] / 10;result[i] result[i] % 10;}}StringBuilder sb new StringBuilder();for (Integer integer : result) {sb.append(integer);}System.out.println(end accumul result sb ;time System.currentTimeMillis());return sb.toString();}
3. 分治算法-Karatsuba
/*** Karatsuba乘法*/
public static long karatsuba(long num1, long num2){//递归终止条件if(num1 10 || num2 10) return num1 * num2;// 计算拆分长度int size1 String.valueOf(num1).length();int size2 String.valueOf(num2).length();int halfN Math.max(size1, size2) / 2;/* 拆分为a, b, c, d */long a Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN));long b Long.valueOf(String.valueOf(num1).substring(size1 - halfN));long c Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN));long d Long.valueOf(String.valueOf(num2).substring(size2 - halfN));// 计算z2, z0, z1, 此处的乘法使用递归long z2 karatsuba(a, c);long z0 karatsuba(b, d);long z1 karatsuba((a b), (c d)) - z0 - z2;return (long)(z2 * Math.pow(10, (2*halfN)) z1 * Math.pow(10, halfN) z0);
}
