文章	评论	标签
6	0	7

高精度计算

高精度运算，是指参与运算的数(加数，减数，因子……）范围大大超出了标准数据类型（整型（int），超长整形（long long )、实型（float/double））能表示的范围的运算。

高精度算法

高精度算法，属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中，

用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。

`operator`

operator是C++和pascal的关键字，它和运算符一起使用，表示一个运算符函数，理解时应将operator=整体上视为一个函数名。

基本原理

加减乘除的基本原理与小学时学的竖式计算几乎无异，通过简单的模拟竖式计算实现。

例子：

加法：

$531 + 531 = 1062$

A[2]:5 A[1]:3 A[0]:1

+ B[2]:5 B[1]:3 B[0]:1

-----------------------------------------------------

Ans[3]:1 Ans[2]:0 Ans[1]:6 Ans[0]:2

减法：

A[2]:5 A[1]:3 A[0]:1

- B[2]:2 B[1]:1 B[0]:0

-----------------------------------------------------

Ans[2]:3 Ans[1]:2 Ans[0]:1

乘法：

$12 * 12 = 144$

A[1]:1 A[0]:2

+ B[1]:1 B[0]:2

-----------------------------------------------------

Ans[1 + 0]:+2 Ans[0 + 0]:+4 ( $12 * 2 = 24$ )

Ans[1 + 1]:+1 Ans[0+ 1]:+2 ( $12 * 10 = 120$ )

-----------------------------------------------------

Ans[2]:1 Ans[1]:4 Ans[0]:4

详细实现

数字的存储&&读入&&输出

很显然，我们存数时肯定不能用标准数据类型存储，那我们怎么办？？
因为高精度数的运算就是简单的模拟竖式计算，而竖式计算时我们是一个数位一个数位的计算，那我们把一个高精度数看成N个数字就行了，用一个数组存。
负数怎么办？？
开个bool做标记。不过还有别的方法。
```
bool ifMinus;
```
C++
我们观察例子时会发现，数组下表是从0开始的，这是为什么？？
方便乘法时算数位，自己可以手动模拟一下。但是读入，输出，去多余的0是稍微需要绕一下。
```
Ans[i + j] = A[i] * B[j];    //数组下表是从0开始
Ans[i + j - 1] = A[i] * B[j]    //数组下表是从1开始
```
C++

我们观察例子时会发现，数组下标小的存的是数位大的，这是为什么呢？？

竖式计算时，我们从小到大进行计算，但面临进位时，如果按照输入顺序，即从高位到低位存，那么我们就需要向数组[数组下表的前一位（-1）]加一个数，但当前数组下标是0时，那么我们就需要加一个数到数组[-1]，但是在C++中数组下标不能为负，而且数组下标大的存的是数位小的，那我们就要从数组下表大的往数组下标小的运算，所以会很变扭。但我们将倒着存时就不会面临这个问题。

//Tips:代码原来是从0开始的方法，从1开始的是改的，Bug可能会比从0开始的多
//数组下表是从0开始
void read()
{
    char *Tmp = new char[maxn];
    scanf("%s", Tmp);
    memset(digit, 0, sizeof(digit));
    lenth = strlen(Tmp);
    ifMinus = Tmp[0] == '-';
    for (int i = ifMinus; i < lenth; ++i)
    {
        digit[lenth - i - 1] = Tmp[i] - '0';
    }
    while (!digit[lenth - 1] && lenth > 1)
        --lenth;
    delete[] Tmp;
}
void read(const int &tmpA)
{
    read((long long)tmpA);
}
void read(const long long &tmpA)
{
    memset(digit, 0, sizeof(digit));
    ifMinus = tmpA < 0;
    if (ifMinus)
        digit[0] = -tmpA;
    else
        digit[0] = tmpA;
    lenth = 1;
    (*this).format();
}
void print()
{
    if (ifMinus && digit[lenth - 1])
        putchar('-');
    for (int i = lenth - 1; i >= 0; --i)
        putchar(digit[i] + '0');
}
 
//数组下表是从1开始
void read()
{
    char *Tmp = new char[maxn];
    scanf("%s", Tmp);
    memset(digit, 0, sizeof(digit));
    lenth = strlen(Tmp);
    ifMinus = Tmp[0] == '-';
    for (int i = ifMinus; i < lenth; ++i)
    {
        digit[lenth - i] = Tmp[i] - '0';
    }
    while (!digit[lenth] && lenth > 1)
        --lenth;
    delete[] Tmp;
}
void read(const int &tmpA)
{
 read((long long)tmpA);
}
void read(const long long &tmpA)
{
    memset(digit, 0, sizeof(digit));
    ifMinus = tmpA < 0;
    if (ifMinus)
        digit[0] = -tmpA;
    else
        digit[0] = tmpA;
    lenth = 1;
    (*this).format();
}
void print()
{
    if (ifMinus && digit[lenth])
        putchar('-');
    for (int i = lenth - 1; i; --i)
        putchar(digit[i] + '0');
}

进位和退位

我们进位时有两种操作方法，一是在运算过程中考虑进位，二是在运算结束后考虑进位。

两种其实都可以，如果是第一种，那我们在运算过程中考虑进位就要多写一个if，这在乘法中极为不友好；如果是第二种，那我们就需要多写一个for，增加时间。

退位同理但只在减法中出现。

//以乘法为例
//第一种
for(int i = 0;i < A.Lenth;++ i){
    for(int j = 0;j < B.Lenth;++ j){
        Ans.Digit[i + j] += A.Digit[i] * B.Digit[j];
        if(Ans.Digit[i + j] >= Hex){
            Ans.Digit[i + j + 1] += (Ans.Digit[i + j] / Hex);
            Ans.Digit[i + j] %= Hex;
            if(i + j + 1 == Ans.Lenth)
                ++ Ans.Lenth;
        }
    }    
}
//第二种
for(int i = 0;i < A.Lenth;++ i)
    for(int j = 0;j < B.Lenth;++ j)
        Ans.Digit[i + j] += A.Digit[i] * B.Digit[j];
for(int i = 0;i < Ans.Lenth;++ i){
    if(Ans.Digit[i] >= Hex){
        Ans.Digit[i + 1] += (Ans.Digit[i] / Hex);
        Ans.Digit[i] %= Hex;
        if(i + 1 == Ans.Lenth)
            ++ Ans.Lenth;
    }
}

数字的比较

与我们自己比较数字的方法相同，从大的数位到小的数位一位一位的比较，但要注意符号。

写出一个大于和等于就可以实现所有的比较运算符。

bool operator==(const hpDigit &tmpA) const
{
    if (ifMinus != tmpA.ifMinus || lenth != tmpA.lenth)
        return false;
    for (int i = 0; i < lenth; ++i)
        if (digit[i] != tmpA.digit[i])
            return false;
    return true;
}
bool operator!=(const hpDigit &tmpA) const
{
    return !(*this == tmpA);
}

bool operator>(const hpDigit &tmpA) const
{
    if (*this == tmpA)
        return false;
    if (ifMinus != tmpA.ifMinus)
        return ifMinus < tmpA.ifMinus;
    if (ifMinus && tmpA.ifMinus)
        return !(*this).unsignedIfBigger(tmpA);
    return (*this).unsignedIfBigger(tmpA);
}
bool operator<(const hpDigit &tmpA) const
{
    return *this != tmpA && !(*this > tmpA);
}
bool operator>=(const hpDigit &tmpA) const
{
    return !(*this < tmpA);
}
bool operator<=(const hpDigit &tmpA) const
{
    return !(*this > tmpA);
}

实例代码

#include <cstdio>
#include <cstdlib>
#include <cstring>

const int maxn = 50000;

struct hpDigit
{
    const int hex = 10;
    bool ifMinus;
    long long digit[maxn];
    int lenth;

    hpDigit()
    {
        ifMinus = false;
        memset(digit, 0, sizeof(digit));
        lenth = 1;
    }
    hpDigit(int A)
    {
        *this = A;
    }
    hpDigit(long long A)
    {
        *this = A;
    }

    void read()
    {
        char *Tmp = new char[maxn];
        scanf("%s", Tmp);
        memset(digit, 0, sizeof(digit));
        lenth = strlen(Tmp);
        ifMinus = Tmp[0] == '-';
        for (int i = ifMinus; i < lenth; ++i)
        {
            digit[lenth - i - 1] = Tmp[i] - '0';
        }
        while (!digit[lenth - 1] && lenth > 1)
            --lenth;
        delete[] Tmp;
    }
    void read(const int &tmpA)
    {
        read((long long)tmpA);
    }
    void read(const long long &tmpA)
    {
        memset(digit, 0, sizeof(digit));
        ifMinus = tmpA < 0;
        if (ifMinus)
            digit[0] = -tmpA;
        else
            digit[0] = tmpA;
        lenth = 1;
        (*this).format();
    }
    void print()
    {
        if (ifMinus && digit[lenth - 1])
            putchar('-');
        for (int i = lenth - 1; i >= 0; --i)
            putchar(digit[i] + '0');
    }

    void format()
    {
        for (int i = 0; i < lenth; ++i)
        {
            if (digit[i] >= hex)
            {
                digit[i + 1] += (digit[i] / hex);
                digit[i] %= hex;
                if (i + 1 == lenth)
                    ++lenth;
            }
            if (digit[i] < 0)
            {
                digit[i + 1] -= 1;
                digit[i] += hex;
            }
        }
        while (!digit[lenth - 1] && lenth > 1)
            --lenth;
    }

    hpDigit unsignedPlus(const hpDigit &tmpA) const
    {
        hpDigit tmp;
        tmp.lenth = tmpA.lenth > lenth ? tmpA.lenth : lenth;
        for (int i = 0; i < tmp.lenth; ++i)
            tmp.digit[i] = digit[i] + tmpA.digit[i];
        tmp.format();
        return tmp;
    }
    hpDigit unsignedMinus(const hpDigit &tmpA) const
    {
        hpDigit tmp;
        tmp.lenth = tmpA.lenth > lenth ? tmpA.lenth : lenth;
        for (int i = 0; i < tmp.lenth; ++i)
            tmp.digit[i] = digit[i] - tmpA.digit[i];
        tmp.format();
        return tmp;
    }
    bool unsignedIfBigger(const hpDigit &tmpA) const
    {
        if (lenth > tmpA.lenth)
            return true;
        if (lenth < tmpA.lenth)
            return false;
        for (int i = lenth - 1; i >= 0; --i)
            if (digit[i] != tmpA.digit[i])
                return digit[i] > tmpA.digit[i];
        return false;
    }

    hpDigit operator=(const hpDigit &tmpA)
    {
        memcpy(digit, tmpA.digit, sizeof(tmpA.digit));
        lenth = tmpA.lenth;
        ifMinus = tmpA.ifMinus;
        return *this;
    }
    hpDigit operator=(const int &tmpA)
    {
        (*this).read(tmpA);
        return *this;
    }
    hpDigit operator=(const long long &tmpA)
    {
        (*this).read(tmpA);
        return *this;
    }

    bool operator==(const hpDigit &tmpA) const
    {
        if (ifMinus != tmpA.ifMinus || lenth != tmpA.lenth)
            return false;
        for (int i = 0; i < lenth; ++i)
            if (digit[i] != tmpA.digit[i])
                return false;
        return true;
    }
    bool operator!=(const hpDigit &tmpA) const
    {
        return !(*this == tmpA);
    }

    bool operator>(const hpDigit &tmpA) const
    {
        if (*this == tmpA)
            return false;
        if (ifMinus != tmpA.ifMinus)
            return ifMinus < tmpA.ifMinus;
        if (ifMinus && tmpA.ifMinus)
            return !(*this).unsignedIfBigger(tmpA);
        return (*this).unsignedIfBigger(tmpA);
    }
    bool operator<(const hpDigit &tmpA) const
    {
        return *this != tmpA && !(*this > tmpA);
    }
    bool operator>=(const hpDigit &tmpA) const
    {
        return !(*this < tmpA);
    }
    bool operator<=(const hpDigit &tmpA) const
    {
        return !(*this > tmpA);
    }

    hpDigit operator+(const hpDigit &tmpA) const
    {
        if (ifMinus == tmpA.ifMinus)
            return (*this).unsignedPlus(tmpA);
        hpDigit tmpB;
        if (ifMinus && !tmpA.ifMinus)
        {
            tmpB = *this;
            tmpB.ifMinus = false;
            return tmpA - tmpB;
        }
        tmpB = tmpA;
        tmpB.ifMinus = false;
        return (*this) - tmpB;
    }
    hpDigit operator+=(const hpDigit &tmpA)
    {
        return *this = *this + tmpA;
    }
    hpDigit operator++()
    {
        return *this += 1;
    }
    hpDigit operator++(int)
    {
        hpDigit tmp = *this;
        *this += 1;
        return tmp;
    }

    hpDigit operator-()
    {
        hpDigit tmp = *this;
        if (lenth == 1 && digit[0] == 0)
            tmp.ifMinus = false;
        else
            tmp.ifMinus = ifMinus ? false : true;
        return tmp;
    }

    hpDigit operator-(const hpDigit &tmpA) const
    {
        hpDigit tmpB;
        if (tmpA.ifMinus)
        {
            tmpB = tmpA;
            tmpB.ifMinus = false;
            return *this + tmpB;
        }
        if (ifMinus)
            return (*this).unsignedPlus(tmpA);
        if ((*this) > tmpA)
            return (*this).unsignedMinus(tmpA);
        return -tmpA.unsignedMinus(*this);
    }
    hpDigit operator-=(const hpDigit &tmpA)
    {
        return *this = *this - tmpA;
    }
    hpDigit operator--()
    {
        return *this -= 1;
    }
    hpDigit operator--(int)
    {
        hpDigit tmp = *this;
        *this -= 1;
        return tmp;
    }

    hpDigit operator*(const hpDigit &tmpA)
    {
        hpDigit tmpB;
        tmpB.ifMinus = ifMinus != tmpA.ifMinus;
        tmpB.lenth = lenth + tmpA.lenth;
        for (int i = 0; i < lenth; ++i)
            for (int j = 0; j < tmpA.lenth; ++j)
                tmpB.digit[i + j] += digit[i] * tmpA.digit[j];
        tmpB.format();
        return tmpB;
    }
    hpDigit operator*=(const hpDigit &tmpA)
    {
        return *this = *this * tmpA;
    }
};

int main()
{
    hpDigit A, B, C;
    A.read();
    B.read();
    A += B;
    A.print();
    printf("\n");
    A *= A;
    A.print();
    printf("\n");
    A -= B;
    A.print();
    printf("\n");
    C.read();
    A -= C;
    A.print();
    printf("\n");
    return 0;
}