0

I tried to write the multiplication code for the huge numbers. The problem is slow. I could not execute in a short time. In this example, the execution time is about a 7 seconds. I want it in one second or less. Is there a suggestion on the code or any library that help me in my problem

string multiply(string num1, string num2) 
{ 
    int len1 = num1.size(); 
    int len2 = num2.size(); 
    vector<int> result(len1 + len2, 0);  
    int i_n1 = 0;  
    int i_n2 = 0;  
    for (int i=len1-1; i>=0; i--) 
    { 
        int carry = 0; 
        int n1 = num1[i];
        i_n2 = 0;           
        for (int j=len2-1; j>=0; j--) 
        { 
            int n2 = num2[j] ; 
            int sum = n1*n2 + result[i_n1 + i_n2] + carry; 
            carry = sum/10; 
            result[i_n1 + i_n2] = sum % 10;  
            i_n2++; 
        } 
  
        if (carry > 0) 
            result[i_n1 + i_n2] += carry; 
        i_n1++; 
    }
    int i = result.size() - 1; 
    while (i>=0 && result[i] == 0) 
    i--; 
    if (i == -1) 
    return "0"; 
    string s = ""; 
      
    while (i >= 0) 
        s += std::to_string(result[i--]);   
    return s; 
}
main()
{
    string str1 ="";
    string str2 ="";
    for(int i=0;i<50000;i++)
    {
     str1+=to_string ((rand()%10));
     str2+=to_string ((rand()%10));\
    }
  clock_t t_star=clock();
  multiply(str1, str2);
  std::cout<<(double)((double)clock()-(double)t_star)/(double)CLOCKS_PER_SEC<<std::endl;
  system("pause");
}
  • Does this link help? https://stackoverflow.com/questions/62441306/is-there-a-good-way-to-optimize-the-multiplication-of-two-bignums – Telescope Feb 04 '21 at 17:22
  • Note you are missing a call to srand. – stark Feb 04 '21 at 17:46
  • make sure you have the optimizer turned on. – user4581301 Feb 04 '21 at 18:25
  • 1
    This doesn't address the question, but there are a couple of problems with this code. First, multiplying an N-digit number by an M-digit number can result in a number with N+M+1 digits. The `result` vector is too small. Second, the contents of the two `std::string` objects that are passed to `multiply` are all character codes, not the digits 0..10. The code in `main` converts the randomly-generated digits into character codes; `'0'` is not the same as `0`. My advice is to use `std::vector` rather than `std::string` for the data, and to not convert the values to text. – Pete Becker Feb 04 '21 at 18:58
  • I have tried all the mentioned methods, but to no avail, but I have not tried Thread because I do not know where to place it, because the process is sequential execution – program_lover Feb 04 '21 at 19:13
  • now i'm trying to try out some library,,,,any suggestions – program_lover Feb 04 '21 at 19:16
  • thank you "Telescope ". the link was useful i found it guys replace the decimal base to a larger base only – program_lover Feb 04 '21 at 19:54
  • see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) – Spektre Feb 04 '21 at 20:05
  • "Spektre" the link you raised is interesting i try programming it and go deeper into it thank you – program_lover Feb 04 '21 at 20:27
  • Have you considered using FFTs? This is the fastest known method for multiplying large numbers. http://numbers.computation.free.fr/Constants/Algorithms/fft.html – XylemFlow Feb 05 '21 at 09:38
  • It depends on how large your numbers are though. For thousands of digits the FFT is fastest, but for 10s or maybe hundreds or digits it's probably the method using: https://en.wikipedia.org/wiki/Karatsuba_algorithm – XylemFlow Feb 05 '21 at 09:47
  • @XylemFlow 1. FFT based Schönhage-Strassen multiplication is slower than [NTT based Schönhage-Strassen multiplication](https://stackoverflow.com/q/18577076/2521214) 2. Schönhage-Strassen multiplication is not the fastest there are slightly faster algorithms out there now also based on NTT/FTT – Spektre Feb 05 '21 at 13:00
  • 1
    @XylemFlow see this [Even faster integer multiplication](https://arxiv.org/ftp/arxiv/papers/1407/1407.3360.pdf) on page 3 is comparison of well known algorithms (I just found by 3 sec of google search) ... however the better complexity algorithms usually involves huge overhead meaning they usable only on really big numbers ... so its best to have more implementations and chose which to use based on bit-width of operands. – Spektre Feb 05 '21 at 13:11

0 Answers0