稍微搜索了一下 大数乘法,
搜到了就是 五种算法:
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
然后看了一介绍,Java 中,采用的是
用二重循环直接相乘
采用 Karatsuba algorithm
采用 Toom-Cook multiplication
然后看了一下,竟然是数论。好吧,我根本看不懂。
按java的算法类型,建议你照着 Karatsuba 乘法 去写吧!数位不够时,可以使用递归就是了。
或者你去翻译:GMP(The GNU MP Bignum Library)。这里面有你所需要的算法,不过是 C++ 的。
附:找到的 Karatsuba 算法, C++ 的,稍微琢磨了一下,估计要先写一个大数加减法的。主要是看不太懂。
--------------------
最后,我决定我再不关注这个贴子了,看不懂。
搜到了就是 五种算法:
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
然后看了一介绍,Java 中,采用的是
用二重循环直接相乘
采用 Karatsuba algorithm
采用 Toom-Cook multiplication
然后看了一下,竟然是数论。好吧,我根本看不懂。
按java的算法类型,建议你照着 Karatsuba 乘法 去写吧!数位不够时,可以使用递归就是了。
或者你去翻译:GMP(The GNU MP Bignum Library)。这里面有你所需要的算法,不过是 C++ 的。
附:找到的 Karatsuba 算法, C++ 的,稍微琢磨了一下,估计要先写一个大数加减法的。主要是看不太懂。
程序代码:
/** * 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); }
--------------------
最后,我决定我再不关注这个贴子了,看不懂。
[此贴子已经被作者于2020-9-15 21:36编辑过]
授人于鱼,不如授人于渔
早已停用QQ了