Java实现分治思想下的大整数数乘
2021/12/4 1:17:11
本文主要是介绍Java实现分治思想下的大整数数乘,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:使用分治算法实现两个大整数的相乘
实现算法:
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实现分治思想下的大整数数乘的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南
- 2024-11-23JAVA项目部署入门:新手必读指南
- 2024-11-23Java项目部署入门:新手必看指南
- 2024-11-23Java项目部署入门:新手必读指南
- 2024-11-23Java项目开发入门:新手必读指南
- 2024-11-23JAVA项目开发入门:从零开始的实用教程
- 2024-11-23Java项目开发入门:新手必读指南