Java实现分治思想下的大整数数乘

2021/12/4 1:17:11

本文主要是介绍Java实现分治思想下的大整数数乘,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:使用分治算法实现两个大整数的相乘

image.png

实现算法:

public class Main {
    //核心算法
    public static long big_integer_multiplication(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 half_N = Math.max(size1, size2) / 2;

        // 拆分为a, b, c, d
        long A = Long.valueOf(String.valueOf(num1).substring(0, size1 - half_N));
        long B = Long.valueOf(String.valueOf(num1).substring(size1 - half_N));
        long C = Long.valueOf(String.valueOf(num2).substring(0, size2 - half_N));
        long D = Long.valueOf(String.valueOf(num2).substring(size2 - half_N));

        // 计算z2, z0, z1, 此处的乘法使用递归
        long z2 = big_integer_multiplication(A, C);
        long z0 = big_integer_multiplication(B, D);
        long z1 = big_integer_multiplication((A + B), (C + D)) - z0 - z2;

        return (long)(z2 * Math.pow(10, (2*half_N)) + z1 * Math.pow(10, half_N) + z0);
    }

    // 测试
    public static void main(String[] args) {
        System.out.println(big_integer_multiplication(1234,4567)); //True
        System.out.println("------------------------------------");
        System.out.println(big_integer_multiplication(123456789,987654321)); //True
        System.out.println("------------------------------------");
        System.out.println(big_integer_multiplication(12345,1234)); //True
    }
    
}

参考资料:

  • 维基百科:Multiplication algorithm
  • 大数乘法,在算法上,主要有几种思路?
  • 华为OJ机试题目:两个大整数相乘(纯C语言实现两个大整数相乘,两种方法实现大数相乘)
  • 算法理解 — 大数相乘问题
  • KaraTsuba乘法 — 高效的大数乘法
  • Karatsuba Multiplication Algorithm – Python Code
  • Toom-Cook 3-Way Multiplication from GMP Documentations
  • 大数相乘(from滴答滴答百度空间)
  • 大整数运算
  • Java的BigInteger的乘法运算是用什么算法实现的?


这篇关于Java实现分治思想下的大整数数乘的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程