长整数乘法

Question

我准备面试问题不是为了完成家庭作业.关于如何复用非常长的整数有一个问题.任何人都可以用C++提供任何源代码来学习吗？我试图通过学习其他解决方案来改善自己,从而缩小我和他人之间的差距.

非常感谢!

很抱歉,如果您认为这不是提出此类问题的正确位置.

Answer 1

你可以使用GNU Multiple Precision Arithmetic Library for C++.

如果你只是想要一个简单的方法来乘以大数(整数),你在这里:

#include<iostream>

#include<string>
#include<sstream>
#define SIZE 700

using namespace std;



class Bignum{

    int no[SIZE];   


    public:

        Bignum operator *(Bignum& x){ // overload the * operator
        /*
            34 x 46
            -------
               204          // these values are stored in the
              136           // two dimensional array mat[][];
            -------
             1564   // this the value stored in "Bignum ret"
        */                              
    Bignum ret;             
    int carry=0;
    int mat[2*SIZE+1][2*SIZE]={0};
    for(int i=SIZE-1;i>=0;i--){
        for(int j=SIZE-1;j>=0;j--){
            carry += no[i]*x.no[j];
            if(carry < 10){
                mat[i][j-(SIZE-1-i)]=carry;
                carry=0;
            }
            else{
                mat[i][j-(SIZE-1-i)]=carry%10;
                carry=carry/10;
            }
        }
    }
    for(int i=1;i<SIZE+1;i++){
        for(int j=SIZE-1;j>=0;j--){
            carry += mat[i][j]+mat[i-1][j];

            if(carry < 10){

                mat[i][j]=carry;

                carry=0;

            }

            else{

                mat[i][j]=carry%10;

                carry=carry/10;

            }
        }
    }
    for(int i=0;i<SIZE;i++)
        ret.no[i]=mat[SIZE][i];
    return ret;
}

Bignum (){

    for(int i=0;i<SIZE;i++)

        no[i]=0;

}


Bignum (string _no){

    for(int i=0;i<SIZE;i++)

        no[i]=0;

    int index=SIZE-1;

    for(int i=_no.length()-1;i>=0;i--,index--){

        no[index]=_no[i]-'0';

    }

}


void print(){

    int start=0;

    for(int i=0;i<SIZE;i++)

    if(no[i]!=0){

        start=i;

        break;      // find the first non zero digit. store the index in start.

    }

    for(int i=start;i<SIZE;i++) // print the number starting from start till the end of array.

        cout<<no[i];

    cout<<endl;

    return;

}
 };


 int main(){

Bignum n1("100122354123451234516326245372363523632123458913760187501287519875019671647109857108740138475018937460298374610938765410938457109384571039846");
Bignum n2("92759375839475239085472390845783940752398636109570251809571085701287505712857018570198713984570329867103986475103984765109384675109386713984751098570932847510938247510398475130984571093846571394675137846510874510847513049875610384750183274501978365109387460374651873496710394867103984761098347609138746297561762234873519257610");

Bignum n3 = n1*n2;
n3.print();

return 0;

  }

正如你所看到的,它是2个巨大的整数:) ...(最多700位)