自己用JAVA实现的大数相乘——稻草人
代码:
import java.util.Scanner;
public class bigNumMultiply {
/**
* 实现两个大数相乘
* @param args
*/
public static final int MAX_LEN = 10000000;
public static int[] tempArray1 = new int[MAX_LEN];
public static int[] tempArray2 = new int[MAX_LEN];//这两个数组用来暂时存储局部结果
//初始化数组函数
public static void Init()
{
for(int i=0;i<MAX_LEN;i++)
{
tempArray1[i] = 0;
tempArray2[i] = 0;
}
}
//实现大数相乘的函数
public static String mul(String num1,String num2)
{
String result = "";
int len1 = num1.length();
int len2 = num2.length();
int tempNum1 = 0,tempNum2 = 0;//num1和num2里拆出来相乘的单个数
int pre = 0;//进位,初始化为0
int mulRes = 0;//乘积
for(int i=0;i<len2;i++)
{
int loc_begin = 0;//往数组里存放一轮计算结果的开始位置
tempNum2 = num2.charAt(i)-'0';
for(int j=0;j<len1;j++)
{
tempNum1 = num1.charAt(j)-'0';
mulRes = tempNum1*tempNum2+pre;
if(i==0)
{
if(j==len1-1){//一轮计算结束
tempArray1[loc_begin] = mulRes;
pre = 0;//一轮存储完毕,进位置0
}
else//一轮计算没有结束
{
pre = mulRes/10;//进位
tempArray1[loc_begin] = mulRes%10;//进位后保存结果
}
loc_begin++;
}
else
{
if(j==len1-1){//一轮计算结束
tempArray2[loc_begin] = mulRes;
pre = 0;//一轮存储完毕,进位置0
}
else//一轮计算没有结束
{
pre = mulRes/10;//进位
tempArray2[loc_begin] = mulRes%10;//进位后保存结果
}
loc_begin++;
}
}
if(i>0)
{
posSum(i,loc_begin-1);//错位求和,结果存放在tempArray1中,i是错位数
}
}
boolean boo = true;
for(int k=tempArray1.length-1;k>=0;k--)
{
if(tempArray1[k]==0 && boo)
{
continue;
}
else
{
boo = false;
result = result+tempArray1[k];
}
}
if(result=="")
result = "0";
return result;
}
//错位求和
public static void posSum(int n,int len)
{
int pre = 0;
int sum = 0;
int i=0;
int j=0;
while(true)
{
if(i>=n)
{
sum = tempArray1[i] + tempArray2[j] + pre;
if(j<len)
{
tempArray1[i] = sum%10;
pre = sum/10;
}
if(j==len)
{
tempArray1[i] = sum;
break;
}
j++;
}
i++;
}
}
public String getMulRes(String num1,String num2)
{
boolean boo = true;//标记结果是否是正数,初始化假设是正数
String result = null;//存放两个大数相乘的结果。
//判断两个大数均为负数
if(num1.charAt(0)=='-' && num2.charAt(0)=='-')
{
num1 = (String)num1.subSequence(1, num1.length());
num2 = (String)num2.subSequence(1, num2.length());
}
else if(num1.charAt(0)=='-' || num2.charAt(0)=='-')//其中一个为负数
{
boo = false;//一正一负,结果为负数。
if(num1.charAt(0)=='-')
{
num1 = (String)num1.subSequence(1, num1.length());
}
else if(num2.charAt(0)=='-')
{
num2 = (String)num2.subSequence(1, num2.length());
}
}
num1 = reverse(num1);
num2 = reverse(num2);
if(num1.length()<=num2.length())
result = mul(num2,num1);
else
result = mul(num1,num2);
if(!boo&&!result.equals("0"))//如果结果为负数,则在前面加‘-’号
result = "-"+result;
return result;
}
//字符串取反,如:(123-->321),方便之后求积
public static String reverse(String str)
{
char[] strarray = str.toCharArray();
StringBuffer sbf = new StringBuffer();
for (int i = strarray.length - 1; i >= 0; i--)
sbf.append(strarray[i]);
return sbf.toString();
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
bigNumMultiply multiply = new bigNumMultiply();
System.out.println("请输入第一个大数:");
while(in.hasNext())
{
Init();//初始化,数组置0
String strNum1 = in.next();
System.out.println("请输入第二个大数:");
String strNum2 = in.next();
System.out.println(strNum1+"*"+strNum2+" = "+multiply.getMulRes(strNum1,strNum2));
System.out.println("请输入第一个大数:");
}
}
}
测试数据:
请输入第一个大数:
123456789
请输入第二个大数:
987654321
123456789*987654321 = 121932631112635269
请输入第一个大数:
10000
请输入第二个大数:
10000
10000*10000 = 100000000
请输入第一个大数:
87654321
请输入第二个大数:
123455666677
87654321*123455666677 = 10821422636174761317
请输入第一个大数:
4566000
请输入第二个大数:
10001
4566000*10001 = 45664566000
请输入第一个大数:
-78655443122
请输入第二个大数:
98765411222
-78655443122*98765411222 = -7768437184792961515084
结果是0的测试数据:
请输入第一个大数:
0
请输入第二个大数:
0
0*0 = 0
请输入第一个大数:
-99
请输入第二个大数:
0
-99*0 = 0
请输入第一个大数:
0
请输入第二个大数:
788
0*788 = 0
请输入第一个大数:
* 限于个人水平,代码比较复杂,同求效率较高的代码。
分享到:
相关推荐
本程序可以求出:任意位的两个大数相乘的结果。 已经实验过>2000位的两数相乘,有兴趣的话,你也试一试吧。 support me!thanks!
其中,Karatsuba算法是一种分治策略,它将两个数分别拆分为较小的部分,然后利用递归关系进行计算,时间复杂度为O(n^1.585)。Toom-Cook算法则是在Karatsuba基础上的扩展,适用于更多个数的相乘。而FFT算法则是通过...
在实际编程中,处理大数相乘通常会用到特定的库,如Java的`BigInteger`类,Python的`int`类型(自动支持大数),或者C++的`GMP`库等。这些库提供了方便的API来进行大数运算,包括乘法。 例如,在Python中,我们可以...
Karatsuba算法将两个n位数的乘法转化为3个较小的n/2位数的乘法,其时间复杂度为O(n^1.585),优于直接乘法的O(n^2)。Toom-Cook算法则更为灵活,可以调整分解的次数,从而在不同情况下优化性能。 对于大数的指数幂...
总结部分,作者提到虽然C语言实现大数相乘比较繁琐,需要自定义函数,但其他如C++、Java和Python等语言提供了更方便的库函数来处理大数。这个过程是学习和理解大数运算原理的好方法。 总之,这篇教程详细介绍了如何...
`BigInteger`的`multiply`方法用于执行两个大数的乘法操作,如下所示: ```java BigInteger result = bigInt1.multiply(bigInt2); ``` `BigInteger`类还支持其他算术操作,如`add`(加法)、`subtract`(减法)、`...
本篇将深入探讨如何利用Java实现两个大整数的相乘,尤其是面对1000位以上的数字时的高效算法。 首先,Java标准库提供了`java.math.BigInteger`类,它专门用于表示和操作任意大小的整数。`BigInteger`类支持所有基本...
两个大数相乘:利用数组实现,数组a存放大数1的每一位,数组b依次存放大数2的每一位。如:一大数1为3463546,则数组 a[]={3,4,6,3,5,4,6},大数2为:89019 则数组b[]={8,9,0,1,9},现在要大数1和大数2相乘,并按数位...
标题中的"mul.zip_Mul(ti)住宅_mul的范围_大数相乘"暗示了我们正在讨论一个涉及大整数乘法的场景,可能是一个软件或算法实现。在描述中提到,“数字比较大,相乘的结果超出了基本类型的表示范围,不能够直接做乘法...
这个"Android两个数相乘源码"示例提供了一个简单的方法来实现两个数字的乘法操作。让我们深入理解其背后的原理,并探讨如何扩展到其他算术运算。 首先,Android应用开发主要使用Java或Kotlin语言,因此源码也会基于...
大数的乘法相对复杂一些,常见的算法有Karatsuba算法和Toom–Cook算法,这里我们可能采用了更基础的“学校乘法”方法,也就是将一个大数拆分为多个位,然后分别与另一个大数相乘,再将结果相加并适当调整位数。...
在具体实现上,首先,输入的两个大整数会被转换成8的倍数,这是因为分治法的处理过程中,需要对每一位进行操作,8的倍数可以使处理更为简洁。接着,通过递归调用,将大整数逐步分解到单个数字的乘法,直到乘法操作...
大整数分解问题:给定两个n位长二进制数x和y,求这两个数的乘积。时间复杂性控制在Θ(n1.6)
4. `multiply()` 方法:该方法用于将两个 BigInteger 对象相乘。 例如:`BigInt1 = BigInt1.multiply(BigInt2);` 5. `divide()` 方法:该方法用于将一个 BigInteger 对象除以另一个 BigInteger 对象。 例如:`...
在这个程序中,可能包含了对`BigInteger`对象的操作,比如创建大数实例、两个大数的乘法运算,以及可能的错误处理和性能优化。`BigInteger`类的乘法操作可以通过调用`multiply()`方法完成,该方法接受另一个`...
1. **初始化:** 创建一个足够长的数组用于存储两个大数相乘的结果。 2. **逐位相乘:** 从最低位开始,逐位对两个大数进行相乘。 3. **进位处理:** 对于每次相乘的结果,如果其值大于等于10,则需要将其拆分为个位...
这种方法将一个大数拆分为二进制位,然后逐位处理。 5. **Bitwise操作**:位操作如位移、与、或、异或等,可以用来有效地处理二进制表示的大数。例如,通过位移操作,可以避免使用乘法和除法,提高速度。 6. **库...
5. **大数乘法实现**:通过嵌套循环来实现两个大数相乘,外层循环遍历第一个大数的每一位,内层循环遍历第二个大数的每一位。每次迭代将对应位的乘积累加到结果的对应位上,并处理进位。 ```c bigfloat b_c...
比如,我们可以将每个大数拆分成若干个更小的块,然后对这些块进行乘法运算,并将结果合并起来。这种方法称为分块乘法,是实现大数乘法的一个基础方法。 在实际应用中,如何选择合适的算法取决于很多因素,如数值的...