面试问题 - 实施Biginteger Multiply

Question

实施Biginteger Multiply

1. 使用整数数组存储像297897654这样的大整数将存储为{2,9,7,8,9,7,6,5,4}
2. 实现bigintegers的乘法函数
   Expamples:{2,9,8,8,9,8}*{3,6,3,4,5,8,9,1,2} = {1,0,8,6 ,3,7,1,4,1,8,7,8,9,7,6}

我没有实现这个课程,并认为它几个星期,无法得到答案.

任何人都可以帮我用C#/ Java实现它？非常感谢.

Answer 1

你知道如何在纸上进行乘法运算吗？

  123
x 456
-----
  738
 615
492
-----
56088

我只想在代码中实现该算法.

Answer 2

C++实现:

源代码:

#include <iostream>

using namespace std;

int main()
{
    int a[10] = {8,9,8,8,9,2};
    int b[10] = {2,1,9,8,5,4,3,6,3};

    // INPUT DISPLAY
    for(int i=9;i>=0;i--) cout << a[i];
    cout << " x ";
    for(int i=9;i>=0;i--) cout << b[i];
    cout << " = ";

    int c[20] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    for(int i=0;i<10;i++)
    {
            int carry = 0;
            for(int j=0;j<10;j++)
            {
                    int t = (a[j] * b[i]) + c[i+j] + carry;
                    carry = t/10;
                    c[i+j] = t%10;
            }
    }

    // RESULT DISPLAY
    for(int i=19;i>=0;i--) cout << c[i];
    cout << endl;
}

输出:

0000298898 x 0363458912 = 00000108637141878976

Answer 3

有一个极好的算法，叫做“ Karatsuba算法”。这里
使用分而治之的方法。可以在其中乘以大数。.
我已经在Java中实现了它。

 package aoa;
    import java.io.*;
    public class LargeMult {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException
    {
        // TODO code application logic here
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter 1st number");
        String a=br.readLine();
        System.out.println("Enter 2nd number");
        String b=br.readLine();
        System.out.println("Result:"+multiply(a,b));

    }
    static String multiply(String t1,String t2)
    {

        if(t1.length()>1&&t2.length()>1)
        {
            int mid1=t1.length()/2;
            int mid2=t2.length()/2;
            String a=t1.substring(0, mid1);//Al
            String b=t1.substring(mid1, t1.length());//Ar
            String c=t2.substring(0, mid2);//Bl
            String d=t2.substring(mid2, t2.length());//Br
            String s1=multiply(a, c);
            String s2=multiply(a, d);
            String s3=multiply(b, c);
            String s4=multiply(b, d);


            long ans;
            ans=Long.parseLong(s1)*(long)Math.pow(10, 
            b.length()+d.length())+Long.parseLong(s3)*(long)Math.pow(10,d.length())+
            Long.parseLong(s2)*(long)Math.pow(10, b.length())+Long.parseLong(s4);
            return ans+"";
        }
        else

        {
            return (Integer.parseInt(t1)*Integer.parseInt(t2))+"";
        }   
    }
}    

希望对您有所帮助！