`
gshxsyq
  • 浏览: 20692 次
社区版块
存档分类
最新评论

java大数相乘算法

    博客分类:
  • java
阅读更多

准备阶段:

       准备一个整型数组若无特别说明下文提到的数组都是指该整型数组其维数为str1和str2这两个字符串的长度之和(两数相乘,其乘积的位数必不大于两乘数的位数之和)。因事先无法知道str1和str2的长度,所以使用动态内存分配的方式定义该数组这里记为arr。该数组的作用是用来保存两个大数相乘的结果每个数组元素存放一个整数并且该整数是0~9间的整数。初始状态都设置为0。

运算步骤:

        在进行大数相乘时仍然采用传统的计算方式即从数的最低位开始用其每一位依次与被乘数相乘然后将结果依次相加。显然要得到最终结果需要涉及到多次的相乘和相加的运算。

        第一次相乘

               (本文约定一次相乘意为乘数的某一位和被乘数的所有位依次相乘并把结果进行相应处理后的一次过程)乘数str2的末位bn与被乘数的每一位相乘并把结果按末位在前首位在后的顺序存入数组arr中。若1≤k≤m如果c[k]≥10则需要进位使得c[k+1]=c[k+1]+c[k]/10c[k]=c[k]%10这个过程称之为数组的重构。

        当进行第二次相乘时乘数str2的倒数第二位b[n- 1]与被乘数的每一位相乘结果依次和数组arr中的attr[2]~attr[m+1]的元素相加并且修改对应数组元素然后按需要进行数组的重构。以此类推当完成第n次相乘后数组arr中存放的数据便是最终结果不过是反序的即最高位在后个位在前这时只要将结果数组逆转,并移除首位为0的元素。最后依次输出每个数组元素的值即可

下面是用Java具体代码的实现:

import java.util.Arrays;

public class BigNumberMultiplication {

	/**
	 * 计算两数相乘
	 * 在进行大数相乘时,仍然采用传统的计算方式,即从数的最低位开始,用其每一位依次与被乘数相乘,然后将结果依次相加存放在结果数组中;(结果数组为末位在前首位在后)
	 * 每次相乘之后对数组进行重构,对大于10的产生进位;
	 * 计算完后对结果数组进行逆转,逆转完之后将结果首位为0的的元素移除,此时的结果数组就为最终计算的结果。
	 * @param str1	被乘数
	 * @param str2	乘数
	 * @return 返回两数相乘后的结果数组
	 */
	public int[] calculateMulti(int[] str1,int[] str2){
		int[] resultArr = new int[str1.length+str2.length];//两数相乘的最大位数不会超过两数的长度之和
		int offset =0;//记录乘数已经进行计算的次数,即进行第几次乘数运算
		for(int i=str2.length-1;i>=0;i--){
			//用其每一位一次与被乘数相乘,将结果一次相加存放在结果数组对应位置中
			for(int j=str1.length-1;j>=0;j--){
				resultArr[offset+str2.length-1-j]+=str2[i]*str1[j];
			}
			//重构数组
			rebulidResultArr(resultArr,offset,str1.length);
			offset++;
		}
		convertResultArr(resultArr);
		//将结果首位为0的元素移除
		boolean isBegin= false;
		for(int i=0;i<resultArr.length;i++){
			if(!isBegin&&resultArr[i]>0){
				isBegin = true;
				resultArr = Arrays.copyOfRange(resultArr, i, resultArr.length);
				break;
			}
		}
		return resultArr;
	}

	/**
	 * 重构结果数组,判断指定位的数值是否大于10,如果大于10就要进位
	 * @param resultArr	待重构的数组
	 * @param offset	重构的起始索引,在这里为第几次重构或者第几次相乘
	 * @param length	需要重构的长度,在这里为被乘数的长度。
	 */
	private void rebulidResultArr(int[] resultArr, int offset, int length) {
		int i= offset;
		while(i<offset+length){
			if(resultArr[i]>10){
				resultArr[i+1] += resultArr[i]/10;
				resultArr[i] %= 10;
			}
			i++;
		}
	}
	/**
	 * 翻转数组,将指定的数组逆转过来
	 * @param resultArr	待翻转的数组
	 */
	private void convertResultArr(int[] resultArr){
		int i=0,j=resultArr.length-1,temp = 0;
		while(i<j){
			temp = resultArr[i];
			resultArr[i]=resultArr[j];
			resultArr[j]=temp;
			i++;
			j--;
		}
	}
	/**
	 * 打印计算的结果
	 * @param resultArr	计算的结果数组
	 */
	public void printResultArr(int[] resultArr){
		for(int i=0;i<resultArr.length;i++){
			System.out.print(resultArr[i]);
		}
	}
	
	public static void main(String[] args) {
		BigNumberMultiplication test= new BigNumberMultiplication();
		int[] str =new int[20];
		for(int i=0;i<str.length;i++){
			str[i]=(i+1)%10;
			System.out.print(str[i]);
		}
		System.out.println();
		int[] resuleArr = test.calculateMulti(str, str);
		test.printResultArr(resuleArr);
		
	}
	
	
}

 

 

分享到:
评论

相关推荐

    大数相乘算法,java代码,包含独立大数相加算法

    大数相乘算法,java代码,包含独立大数相加算法 其中bigNumberPlus(String s1,String s2)为大数相加方法 bigNumberMultiply(String s1,String s2)为大数相乘方法

    大数相乘解决无限位数相乘问题

    大数相乘的算法多种多样,其中包括经典的Karatsuba算法、Toom-Cook算法,以及更为高效的FFT(快速傅里叶变换)算法。其中,Karatsuba算法是一种分治策略,它将两个数分别拆分为较小的部分,然后利用递归关系进行计算...

    JAVA大数相乘

    "JAVA大数相乘"这个主题主要涉及到Java中的`BigInteger`类,它提供了对任意精度整数的支持,能够有效地处理大数运算,包括加法、减法、乘法、除法以及更复杂的数学操作。`BigInteger`类是Java标准库`java.math`包的...

    大数相乘指数幂的实现

    大数相乘的基本算法有多种,其中最简单的是直接乘法,类似于小学数学中的竖式乘法,但效率较低。随着计算需求的提高,人们发展出了更高效的算法,如Karatsuba算法和Toom-Cook算法,这些算法利用分治策略将大数乘法...

    2021-11-22 C语言学习应用——用C语言实现大数相乘(csdn)————程序.pdf

    总结部分,作者提到虽然C语言实现大数相乘比较繁琐,需要自定义函数,但其他如C++、Java和Python等语言提供了更方便的库函数来处理大数。这个过程是学习和理解大数运算原理的好方法。 总之,这篇教程详细介绍了如何...

    mul.zip_Mul(ti)住宅_mul的范围_大数相乘

    标题中的"mul.zip_Mul(ti)住宅_mul的范围_大数相乘"暗示了我们正在讨论一个涉及大整数乘法的场景,可能是一个软件或算法实现。在描述中提到,“数字比较大,相乘的结果超出了基本类型的表示范围,不能够直接做乘法...

    大整数相乘算法 分治法

    大整数相乘算法是计算机科学中用于处理超出标准数据类型范围的大整数乘法问题的一种方法。在大多数编程语言中,如C++,整数类型(如`unsigned long`)都有其最大值限制,一旦超过这个限制,就无法正确表示大整数的...

    大数阶乘的程序编写的 经典算法 和 支持大数的算法

    在实际应用中,如Python的math库和Java的BigInteger类,都提供了内置的大数支持,可以方便地计算和操作大数阶乘。 总结来说,要处理大数阶乘,关键在于理解基本数据类型的表示限制,并采用适当的数据结构(如数组)...

    JAVA实现大整数相乘

    本篇将深入探讨如何利用Java实现两个大整数的相乘,尤其是面对1000位以上的数字时的高效算法。 首先,Java标准库提供了`java.math.BigInteger`类,它专门用于表示和操作任意大小的整数。`BigInteger`类支持所有基本...

    java rsa加密算法实现

    1. **RSA原理**:RSA算法基于数论中的大数因子分解难题,由两个大素数P和Q相乘得到N,然后计算N的欧拉函数φ(N) = (P-1) * (Q-1),选取一个与φ(N)互质的整数E作为公钥的加密指数,再计算E关于φ(N)的模逆数D作为...

    Calculate.rar_大数

    大数相乘的算法有多种实现方式,其中一种经典算法是Karatsuba算法,它是一种分治算法,比传统的长乘法更快。还有一种更高效的算法是Toom–Cook算法,其时间复杂度更低,但实现起来比Karatsuba算法更复杂。不过,Java...

    任意大的两个数相乘

    在实际编程中,处理大数相乘通常会用到特定的库,如Java的`BigInteger`类,Python的`int`类型(自动支持大数),或者C++的`GMP`库等。这些库提供了方便的API来进行大数运算,包括乘法。 例如,在Python中,我们可以...

    java实现RSA算法

    RSA算法基于大数因数分解的困难性,即在现有的计算能力下,将两个大素数相乘得到的合数进行因数分解是非常耗时的。其核心过程包括密钥生成、加密和解密三个步骤: - **密钥生成**:选择两个大素数p和q,计算n=p*q和...

    大数实现的椭圆曲线(ECC)加解密算法

    例如,可以使用学校课本中的长除法进行大数除法,使用Karatsuba或Toom-Cook算法进行高效的大数乘法。 接下来,是ECC实现模块。这一部分涉及到椭圆曲线方程的数学运算,如点的加法和双倍。对于椭圆曲线上的点P(x, y)...

    华中科技大学算法实验

    这个实验涵盖了四个核心主题:大数相乘、二分查找树、最近点对问题和Floyd算法。这些知识点在计算机科学中具有举足轻重的地位,是理解和解决复杂计算问题的基础。 1. **大数相乘**:在计算机科学中,处理大数是必不...

    java大数乘法的简单实现 浮点数乘法运算

    本文将详细介绍如何实现一个简单的Java大数乘法,包括浮点数的乘法运算。 首先,大数乘法的基本思想是将大数分解为单个数字,然后按照常规乘法规则逐位相乘。在Java中,我们可以使用字符串来存储这些大数,因为字符...

    java练习_大数运算_BigInteger.pdf

    Java大数运算 BigInteger 类的方法调用 正如我们在 Java 中处理大数运算时,需要使用 BigInteger 类来实现,这是因为 Java 的基本数据类型无法存储非常大的数字。BigInteger 类提供了几个重要的方法来进行大数运算...

    大数乘法能够实现2个200位以内数的乘法

    5. **库支持**:许多编程语言如Python、Java、C#等都内置了大数支持,提供了简便的大数乘法函数,例如Python的`*`运算符可以直接用于大数乘法,底层通常会用到上述的高效算法。 在描述中提到的“将该数拆分,进行...

    acm源码大全各种算法

    当需要计算两个字符串表示的大数相乘时,可以使用类似于手动竖式乘法的方法。上述代码将每个数字转换为字符数组,然后逐位相乘并累加进位。为了处理进位,它维护了一个标志变量`flag`。这种方法虽然简单,但效率较...

Global site tag (gtag.js) - Google Analytics