[6. high precision multiplication]

High precision multiplication

Ideas ：

• Multiply high precision integers by low precision integers , take Smaller numbers are treated as a whole , Every bit of a high-precision integer , Multiply by low precision integers
• The next bit is multiplied by a small integer , And add the carry .
• Remove the lead 0, Because the result may be 0123456

Specific steps

1. take High precision integers A and Low precision integer b In reverse order Arrange in an array
2. Every bit of a high-precision integer , Multiply the whole by a low precision integer .
3. Consider carrying ,(A * b + t) %10 As a result ,(A * b + t) / 10 For carry .
4. Remove the lead 0, Because the result may be 0123456
5. take C Median number , Reverse order printout .

give an example ：

Code

#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A, int b)
{
     
   vector<int> C;
   int t = 0;         // At the very beginning t0 = 0;
   for (int i = 0; i < A.size() || t; i ++)
   {
     
       if(i < A.size()) t += A[i] * b;
       C.push_back(t % 10);
       t /= 10;
   }
   
   while (C.size() > 1 && C.back() == 0) C.pop_back();  // Remove the lead 0;
   return C;
}

int main()
{
     
   string a;
   int b;
   cin >> a >> b;
   
   vector<int>A;
   for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
   
   auto C = mul(A,b);
   
   for (int i = C.size() - 1; i >= 0; i --)printf("%d", C[i]);
}

The core algorithm can be changed to ：

vector<int> mul(vector<int> &A, int b)
{
     
   vector<int> C;
   int t = 0;         // At the very beginning t0 = 0;
   for (int i = 0; i < A.size() ; i ++)
   {
     
       t += A[i] * b;
       C.push_back(t % 10);
       t /= 10;                
   }                            
   if (t != 0) C.push_back(t);   // here t There are many situations , May be 0（ No carry ）, The possible carry is 1, It is also possible to carry more than 1
                                // There are only two cases of addition , Or carry , Carry only  1, Or not carry 
   
   while (C.size() > 1 && C.back() == 0) C.pop_back();  // Remove the lead 0;
   return C;
}