High precision operation

High precision addition

analysis

The main ways to realize high-precision addition are 2 spot ：① How to save the number ② How to calculate logarithm
One 、 How to save a large integer ？
answer ： Exists in the array , And from a bit （ Low position ） Start saving . For example, a number 123456789.

Location	0	1	2	3	4	5	6	7	8
Number of deposits	9	8	7	6	5	4	3	2	1

（1） Why reverse order ？
answer ： Every time you calculate , May encounter carry problems . If a carry occurs during the calculation of the largest bit , And we use positive order storage , You need to move the array to make a space at the beginning , This will be very cumbersome . Therefore, it is very convenient to add the last carry by directly using reverse order storage .
And this is also in line with the direction of our manual calculation .（ Manual calculation will be explained later ）
（2） Why use dynamic arrays （vector）
answer ： In dynamic arrays , have access to STL The self-contained function is very convenient to obtain the array length , No external summation storage , And random access to .
Two 、 How to calculate an array ？
answer ： Simulate artificial addition , Add from the low order of two numbers , When the sum is less than 10 Time is directly expressed as the operation result of this bit , The sum is greater than or equal to 10 Will be greater than 10 As the result of the operation of this bit and move forward one bit .

Templates

vector<int> add(string a,string b){
    
    vector<int>A,B;// Store the string in reverse order into the dynamic array .
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');// Transformation types 
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
    vector<int>C;
    int t=0;// Carry sign , Initial carry 0
    for(int i=0;i<A.size()||i<B.size();i++){
    
        if(i<A.size())t+=A[i];// The current bit exists , Join in t
        if(i<B.size())t+=B[i];
        C.push_back(t%10);// Add non carry numbers to the array .
        t/=10;// When t Greater than 10 Time quotient 1, That is, carry .
    }
    if(t)C.push_back(1);// Determine whether the last carry 
    return C;
}

Example

791. High precision addition - AcWing Question bank
AC Answer key ：

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

vector<int> add(string a,string b){
    
    vector<int>A,B;// Store the string in reverse order into the dynamic array .
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');// Transformation types 
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
    vector<int>C;
    int t=0;// Carry sign , Initial carry 0
    for(int i=0;i<A.size()||i<B.size();i++){
    
        if(i<A.size())t+=A[i];// The current bit exists , Join in t
        if(i<B.size())t+=B[i];
        C.push_back(t%10);// Add non carry numbers to the array .
        t/=10;// When t Greater than 10 Time quotient 1, That is, carry .
    }
    if(t)C.push_back(1);// Determine whether the last carry 
    return C;
}

int main(){
    
    string a,b;
    cin>>a>>b;
    auto sum=add(a,b);//auto You can automatically determine the type of return value , Can be lazy .
    for(int i=sum.size()-1;i>=0;i--)cout<<sum[i];
    return 0;
}

High precision subtraction

analysis

​ The storage methods of the four high-precision algorithms are the same .

	$A_3$	$A_2$	$A_1$	$A_0$
—		$B_2$	$B_1$	$B_0$

$A_i-B_i-t$ There are two situations ,

①$A_i-B_i-t\ge 0$ There is direct $A_i-B_i-t$.

②$A_i-B_i-t<0$ Yes $A_i-B_i+10-t$, At the same time, record a debit .

At this time, you can find a problem , Only when guaranteed $A\ge B$ When can we calculate in a correct order . So we also need to consider being $A<B$ The situation of , This situation is also easy to deal with, just change it to $-(B-A)$ That's all right. . Of course, there is another point here , Namely $A$ and $B$ Must be positive numbers , If there is a negative number, it still needs a judgment to transform .

• summary ： Judge $A$ and $B$ The size of the relationship ,$A\ge B$ When $A-B$;$A<B$ When $-(B-A)$.

Finally, we need to remove the leading 0.

Templates

bool cmp(vector<int> &A,vector<int> &B){
    
    if(A.size()!=B.size())return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--)
        if(A[i]!=B[i])return A[i]>B[i];
    return true;
}
vector<int> sub(vector<int> &A,vector<int> &B){
    
    vector<int> C;
    for(int i=0,t=0;i<A.size();i++){
    
        t=A[i]-t;
        if(i<B.size())t-=B[i];
        C.push_back((t+10)%10);
        if(t<0)t=1;
        else t=0;
    }
    while(C.size()>1&&C.back()==0)C.pop_back();// Remove the lead 0
    return C;
}
vector<int> C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A),cout<<'-';

Example

792. High precision subtraction - AcWing Question bank

#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A,vector<int> &B){
    
    if(A.size()!=B.size())return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--)
        if(A[i]!=B[i])
            return A[i]>B[i];
    return true;
}
vector<int> sub(vector<int> &A,vector<int> &B){
    
    vector<int> C;
    for(int i=0,t=0;i<A.size();i++){
    
        t=A[i]-t;
        if(i<B.size())t-=B[i];
        C.push_back((t+10)%10);
        if(t<0)t=1;
        else t=0;
    }
    while(C.size()>1&&C.back()==0)C.pop_back();// Remove the lead 0
    return C;
}

int main(){
    
    string a,b;
    vector<int> A,B;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
    vector<int> C;
    if(cmp(A,B))C=sub(A,B);
    else C=sub(B,A),cout<<'-';
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    cout<<endl;
    return 0;
}

High precision multiplication

analysis

​ The high-precision multiplication here is different from the previous high-speed addition and division , Not two high-precision phase operations . But a high precision and a low precision operation . The low accuracy here is less than $max(longlong)/10$ Of .

		$A_2=1$	$A_1=2$	$A_0=3$
$\times$				$B=12$
carry	$t_3$	$t_2$	$t_1$	$t_0$
value	$C_3$	$C_2$	$C_1$	$C_0$

First step ：

$C_0=(A_0\ast B+t_0)\%10=6$

$t_1=(A_0\ast B+t_0)/10=0$

The second step ：

$C_1=(A_1\ast B+t_1)\%10=7$

$t_2=(A_1\ast B+t_1)/10=2$

The third step ：

$C_2=(A_2\ast B+t_2)\%10=4$

$t_3=(A_2\ast B+t_2)/10=1$

Step four ：

$C_3=(0\ast B+t_3)\%10=1$

• The final answer $123\ast 12=1476$

Templates

vector<int> mul(vector<int> &A,int b){
    
    vector<int> C;
    int t=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;
}
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');

Example

793. High precision multiplication - AcWing Question bank

#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A,int b){
    
    vector<int> C;
    int t=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]);
    return 0;
}

High precision division

analysis

​ Just like high-precision multiplication , High precision division is also a high precision and low precision operation . And the setting will not produce decimals , It exists in the form of remainder .

Templates

vector<int> div(vector<int> &A,int b,int &r){
    //r Is reference passing 
    vector<int> C;// merchant 
    r=0;
    for (int i=A.size()-1;i>=0;i--){
    // Start at the top 
        r=r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0)C.pop_back();
    return C;
}

Example

794. High precision division - AcWing Question bank

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r){
    //r Is reference passing 
    vector<int> C;// merchant 
    r=0;
    for (int i=A.size()-1;i>=0;i--){
    // Start at the top 
        r=r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0)C.pop_back();
    return C;
}
int main(){
    
    string a;
    vector<int> A;
    int B;
    cin>>a>>B;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    int r;
    auto C=div(A,B,r);
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    cout<<endl<<r<<endl;
    return 0;
}