求一个10位以上的大整数相乘的java算法

Question

/** */
/**
 * 大整数项乘
 * @author seven
 *
 */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.math.*;public class Test1 {
public static void main(String[] args) {
Test1 t1 = new Test1(); long x, y; System.out.println("Input x ");
x = t1.getNumFromConsole();
System.out.println("x:" + num(x) + "位数");
System.out.println("Input y ");
y = t1.getNumFromConsole();
System.out.println("x:" + num(y) + "位数");
System.out.println(t1.mult(x, y, num(x)));
} public long getNumFromConsole() {
String str = null;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
str = br.readLine();
} catch (IOException e) {
System.out.println(e.getMessage());
}
return Long.parseLong(str);
} public long mult(long x, long y, int n) {
long a, b, c, d, s;
int e;
if (n == 1)
return x * y;
else {
a = (long) (x / Math.pow(10, n / 2));// 取x左半部分
b = (long) (x % Math.pow(10, n / 2));// 取x的又半部分
c = (long) (y / Math.pow(10, n / 2));// 取y的左半部分
d = (long) (y % Math.pow(10, n / 2));
e = num(a); s = (long) (mult(a, c, e)
* Math.pow(10, n)
+ (mult((a - b), (d - c), e) + mult(a, c, e) + mult(b, d, e))
* Math.pow(10, n / 2) + mult(b, d, e));
return s;
}
} // 判断输入数字的位数
private static int num(long x) {
int i = 0;
if (x - 9 <= 0)
return 1;
else {
while (x != 0) {
i++;
x = x / 10;
}
return i;
}
}
}
这个算法10位以上的就算不出了 请问如何改进？

Answer 1

http://topic.csdn.net/u/20080325/17/349A70A3-FD50-4FE9-8319-24F140F82298.html
参考我在该贴8楼的回帖。

Answer 2

以前写着玩的。参考一下。 //大数相加与大数相乘,大数阶乘
import java.util.*;
public class tt {
    public static void main(String args[]) 
{
// System.out.print( bigAdd(null,"1123123123123132"));
// System.out.print(bigJie(10));
// System.out.print(Jie(2000));
// System.out.print(cheng("123123123123123123123","200"));
// System.out.print(bigJian("123456123456789","445645645645"));
System.out.print(bigChu("123456789123","11231223"));
    }
/*
大数相减，若a>b则用a的每一位减b,否则用b-a，最后前面加负号
然后判断每一位的正负，负数则取10+此数，上一位-1；
*/
public static String bigChu(String a,String b )
{
if(a==null) a="";
if(b==null) b="";
int temp=0;
int[] array1=new int[9000];
int[] array2=new int[9000];
int[] array3=new int[9000];
String result="";
while(bigJian(a,b).charAt(0)!='-')
{
result=bigAdd(result,"1");
a=bigJian(a,b);
}
result+=" mod "+a;
return result;
}
public static String bigJian(String a,String b)
{
if(a==null) a="";
if(b==null) b="";
int temp=0;
boolean blag;
if(a.length()>b.length())
{
blag=true;
}
else
{
if(a.length()==b.length())
{
if(a.compareTo(b)>=0)
{
blag=true;
}
else
{
blag=false;
}
}
else
{
blag=false;
}

}
int[] array1=new int[9000];
int[] array2=new int[9000];
int[] array3=new int[9000];
String result="";
//把两个串分别放在数组中
for(int i=0;i<a.length();i++)
{
array1[9000-a.length()+i]=Integer.parseInt(Character.toString(a.charAt(i)));
}
for(int i=0;i<b.length();i++)
{
array2[9000-b.length()+i]=Integer.parseInt(Character.toString(b.charAt(i)));
}
//每一位分别相减
for(int i=0 ;i<array3.length;i++)
{
if(blag)
{
array3[i]=array1[i]-array2[i];
}
else
{
array3[i]=array2[i]-array1[i];
}
} for(int i=array3.length-1;i>temp;i--)
{
if(array3[i]<0)
{
array3[i]+=10;
array3[i-1]-=1;
}
}
for(int i=0;i<9000;i++)//去掉数组前的0000
{
if(array3[i]!=0)
{
temp=i;
break;
}
if(i==8999)
{
return "0";
}
}
if(!blag)
{
result="-";
}
for (int i=temp;i<9000 ;i++ )
{
result+=array3[i];
}
return result;
}
public static String bigAdd(String a,String b)
{
if(a==null) a="";
if(b==null) b="";
int temp=0;
int[] array1=new int[9000];
int[] array2=new int[9000];
int[] array3=new int[9000];
String result="";
//把两个串分别放在数组中
for(int i=0;i<a.length();i++)
{
array1[9000-a.length()+i]=Integer.parseInt(Character.toString(a.charAt(i)));
}
for(int i=0;i<b.length();i++)
{
array2[9000-b.length()+i]=Integer.parseInt(Character.toString(b.charAt(i)));
}
//每一位分别相加
for(int i=0 ;i<array3.length;i++)
{
array3[i]=array1[i]+array2[i];
}
//进位，上一位=上一位+当前位/10
//       当前位=当前位%10
for(int i=array3.length-1;i>0;i--)
{
array3[i-1]+=array3[i]/10;
array3[i]=array3[i]%10;
}
for(int i=0;i<9000;i++)//去掉数组前的0000
{
if(array3[i]!=0)
{
temp=i;
break;
}
if(i==8999)
{
return "0";
}
}
for (int i=temp;i<9000 ;i++ )
{
result+=array3[i];
}
return result;
}
//大数*非大数
/*
 * b*a就是b个a想加，循环调用加法；
*/
public static String cheng(String a,int b)
{
String result="";
for(int i=0;i<b;i++)
{
result=bigAdd(result,a);
}
return result;
}
//大数*大数
/*
 * 用b的每一位分别乘a，得到的数再最后加上相应个数的0
 * 存在数组temp中，再让temp的每个元素相加得到结果
*/
public static String cheng(String a,String b)
{
String[] temp=new String[b.length()];
String result="";
for(int i=0;i<b.length();i++)
{
temp[i]=cheng(a,Integer.parseInt(Character.toString(b.charAt(i))));
for(int j=0;j<b.length()-i-1;j++)
{
temp[i]+="0";
}
}
for(int i=0;i<temp.length;i++)
{
result=bigAdd(result,temp[i]);
}
return result;
} public static String Jie(int b)
{
String result="";
int temp=0; //用于最后去掉整个数组中的前面没用的 0
int tt=0; //用于记录每次乘的进位数；
int[] a=new int[9000];  //
a[8999]=1; //把数组最后一位设为了1，从最后一位开始乘，
for(int i=1;i<=b;i++) //用从 1 到 b 的每一个数去乘数组的每个元素，
{
for(int j=8999;j>=0;j--)
{
a[j]=a[j]*i+tt;    //数组中的元素=原来的数*i+进位数，
tt=0;    //进位数清0，用于下回记录；
if((a[j]+"").length()>=2) //此元素大于10则进位，本身只保留余数;
{
tt=a[j]/10;
a[j]=a[j]%10;
}
}
}
for(int i=0;i<a.length;i++)//去掉数组前的0000
{
if(a[i]!=0)
{
temp=i;
break;
}
if(i==8999)
{
return "0";
}
}
for(int i=temp;i<a.length;i++)//输出
{
result+=a[i];
}
return result;
}
}

Answer 3

Java 有自己的 BigDecimal 你看看帮助吧！ 
非得用数组啊？ 我建议你研究一下BigDecimal的源代码，也许有收获!

Answer 4

BigDecimal 对于过大的数字，运算不准确的。必须自己手动补充。。

Answer 5

给你个大数相乘的算法：　public class Factory {
public static void main(String[] str){
int[] result = new int[10000];
int digits =1;
result[0] = 1;
for(int i = 2; i <= 100;i++){
digits = mul(result, digits, i);
}
System.out.println(toString(result, digits));
}

static int mul(int[] array, int digits, int n){
int more = 0;
for(int i = 0;i < digits;i++){
more = more + array[i]*n;
array[i] = more % 10;
more = more / 10;
}
while(more > 0){
array[digits++] = more % 10;
more = more / 10;

}
return digits;
}

static String toString(int[] array, int digits){
String result = "";
for(int i = digits - 1;i >= 0;i--){
result = result + array[i];
}
return result;
}
}

Answer 6

BigDecimal不怎么样，上面手动写的确很不错

Answer 7

我贴的那个算法返回的s为long形 但是long是从 -2,147,483,648   到   2,147,483,647 但是他居然能得出超过这个范围的数字 而且不是溢出数据 是正确数据 这是为啥？？？

Answer 8

Java里int是32位， -2,147,483,648  到  2,147,483,647 是int

Answer 9

java.math.BigInteger中有处理大整数的方法，
BigInteger.multiply(BigInteger var)就是处理大整数相乘的方法，还有其他的你也可以去看看，我就不一一列举了，api还是很强大的。（而且这是个实用的类，所以建议你记住）代码如下：
BigInteger n=new BigInteger("12345475464654412546"),
           m=new BigInteger("54687614546547687");//定义2个大整数
System.out.println(n.multiply(m));        就是这么简单，其他方法有点舍近求远了，可以作为兴趣自己编一下（参考java编号得api），呵呵，我这部算偷懒的方法吧，有这个方法为什么不用