高精度計算：C++ LongInt實現

一、為什麼需要高精度計算

在進行數字計算的時候，常常會遇到數值過大（超過計算機所能表示的範圍）的情況。例如，計算排列組合數、大數乘法、大數除法、高精度加減法、高精度冪等計算等。這時，就需要用到高精度計算。

高精度計算是通過將一個大數拆分成多個小數，然後利用計算機的機制來進行處理，進而達到表示大數的目的。一般情況下，我們可以利用數組存儲一個數，每個元素存儲這個數的一位，這樣就可以表示任意長度的大數。

二、C++ LongInt實現

C++語言本身就支持很好的高精度計算，用STL即可。例如vector、string等類，都可以進行高精度運算。另外，我們還可以自己實現一些高精度的類，例如LongInt。

下面給出一個簡單的LongInt類實現，包括加、減、乘、除、取模、賦值、大小比較等基本操作。

#include<vector>
#include<iostream>
using namespace std;
class LongInt{
public:
    vector<int>num;
    bool flag;
    LongInt(){flag=false;}
    LongInt(string s){init(s);}
    LongInt(const LongInt&a){num=a.num;flag=a.flag;}
    void init(string&s){
        int len=s.length()-1;
        while(len>=0){num.push_back(s[len]-'0');len--;}
        flag=s[0]=='-';
        if(flag)num.pop_back();
    }
    LongInt&operator+(LongInt&rhs){
        int carry=0;
        int len=max(num.size(),rhs.num.size());
        for(int i=0;i<len;i++){
            if(i<num.size())carry+=num[i];
            if(i=num.size())num.push_back(0);
            num[i]=carry%10;
            carry/=10;
        }
        if(carry)num.push_back(carry);
        return*this;
    }
    LongInt&operator-(LongInt&rhs){
        int borrow=0;
        for(int i=0;i<num.size();i++){
            if(i<rhs.num.size())borrow=num[i]-rhs.num[i]-borrow;
            else borrow=num[i]-borrow;
            if(borrow1&&num.back()==0)num.pop_back();
        return*this;
    }
    LongInt&operator*(LongInt&rhs){
        vector<int>result(num.size()+rhs.num.size(),0);
        for(int i=0;i<num.size();i++){
            for(int j=0;j1&&num.back()==0)num.pop_back();
        return*this;
    }
    LongInt&operator/(LongInt&rhs){
        int len=num.size()-rhs.num.size();
        LongInt quotient;quotient.flag=flag^rhs.flag;
        if(len<0){
            quo.num.push_back(0);
            return quotient;
        }
        LongInt dividend(*this<<len);
        LongInt divisor(rhs<=0;i--){
            int l=0,r=10,ans=0;
            while(l<=r){
                int mid=(l+r)>>1;
                if(dividend>=(divisor*mid)){l=mid+1;ans=mid;}
                else r=mid-1;
            }
            quotient.num.insert(q.n.begin(),ans);
            dividend-=(divisor*ans);
            divisor>>1;
        }
        while(quotient.num.size()>1&&quotient.num.back()==0)quotient.num.pop_back();
        return quotient;
    }
    LongInt&operator%(LongInt&rhs){
        *this-*((*this/rhs)*rhs);
        return*this;
    }
    LongInt&operator<<(int n){
        while(n--)num.insert(num.begin(),0);
        return*this;
    }
    bool operator>(LongInt&r){
        if(num.size()!=r.num.size())return num.size()>r.num.size();
        for(int i=num.size()-1;i>=0;i--)if(num[i]!=r.num[i])return num[i]>r.num[i];
        return false;
    }
    bool operator<(LongInt&rhs){return rhs>*this;}
    bool operator=(LongInt&rhs){
        num=rhs.n;
        return flag=rhs.flag;
    }
    void print(){
        if(flag)putchar('-');
        for(int i=num.size()-1;i>=0;i--)putchar(num[i]+'0');
    }
};

三、使用LongInt類實現高精度計算

下面，我們來利用上面實現的LongInt類進行高精度計算。可以實現加法、減法、乘法、除法、取模等計算。

#include<iostream>
#include<string>
#include"LongInt.h"
using namespace std;
int main(){
    string s1="123456789012345678901234567890";
    string s2="987654321098765432107654321098";
    
    LongInt a(s1),b(s2);
    cout<<"a=";a.print();cout<<endl;
    cout<<"b=";b.print();cout<<endl;
    cout<<"add=";(a+b).print();cout<<endl;
    cout<<"sub=";(a-b).print();cout<<endl;
    cout<<"mul=";(a*b).print();cout<<endl;
    cout<<"div=";(a/b).print();cout<<endl;
    cout<<"mod=";(a%b).print();cout<<endl;
    
    return 0;
}

四、總結

本文介紹了高精度計算以及其重要性，同時，通過C++語言自帶類實現了高精度計算功能，並且給出了相應的數學運算實現，例如加、減、乘、除、取模等操作。儘管C++語言自帶的類可以實現高精度計算，但自己實現高精度類的好處也是顯而易見的，例如可以提高代碼的效率、更好的理解高精度計算。