对于大数运算的算法,建议考虑位长和变量类型时,在参考java的系统算法(摘取):
1、Java 7 里面,就是用二重循环直接乘的,复杂度为O(n^2)。源代码:[BigInteger - Java71] (见1165行)
2、Java 8 里面,根据两个因数的大小,有三种乘法。源代码:[BigInteger - Java8] (见1464行):
2.1、当两个因数均小于 2^(32 × 80)时,用二重循环直接相乘,复杂度为 O(n^2)
2.2、当两个因数均小于 2^(32 × 240)时,采用 Karatsuba algorithm,复杂度为 O(n^(log2 3)≈O(n^1.585)
2.3、否则,采用 Toom-Cook multiplication,其复杂度为 O( n^(log3 5) ≈ O(n^1.465)
3、根据java系统的算法分析,如果4096以下优选算法1、4096-8192的优选算法2、大于8192的优选算法3
1、Java 7 里面,就是用二重循环直接乘的,复杂度为O(n^2)。源代码:[BigInteger - Java71] (见1165行)
2、Java 8 里面,根据两个因数的大小,有三种乘法。源代码:[BigInteger - Java8] (见1464行):
2.1、当两个因数均小于 2^(32 × 80)时,用二重循环直接相乘,复杂度为 O(n^2)
2.2、当两个因数均小于 2^(32 × 240)时,采用 Karatsuba algorithm,复杂度为 O(n^(log2 3)≈O(n^1.585)
2.3、否则,采用 Toom-Cook multiplication,其复杂度为 O( n^(log3 5) ≈ O(n^1.465)
3、根据java系统的算法分析,如果4096以下优选算法1、4096-8192的优选算法2、大于8192的优选算法3