投稿
  1. 高性能架构探索首页
  2. C/C++

关于高精度

admin • • C/C++ • 阅读 147

高精度算法

高精度算法，是指参与运算的数（加法，减法，因数......），而这些数字的巨大，远远超过了unsigned long long 或其他标准数据类型，这时，我们就要用高精度算法了…… 不得不说，极其毒瘤啊

众所周知，一般的高精度算法都是模拟竖式，这显然是对的，但为什么是这样呢？首先，我们知道，2020以前的大部分电脑都是很……很聪明，它只听你说对的话，如果你说错了话，他就反了你了……

高精度起源于很久很久以前，也不知道为什么，可能是因为人发明的方法更聪明些，就被计算机采用了……

高精度加法[1]

  1. 我们在一开始时需要把两个字符串右移，以求右对齐，来进行模拟。
  2. 左移是在充分必要时才用的。[2]
  3. 在模拟时，我们可以再模拟的时候就直接进位，也可以把进位的位保存下来，到了最后再加，这里编者用的前者。

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1005
char s1[MAXN], s2[MAXN], ans[MAXN];
inline void right_move(char *s)  //这里用的是指针，也可以用void right_move(char s[])来定义，效果一样         
{
    int len = strlen(s);
    for(register int i = len - 1, j = MAXN - 1; i >= 0; i--, j--)
    {
        s[j]=s[i]-48;
        s[i]=0;
    }
}// 右移函数，作用是向右对齐
inline void left_move(char *s)        
{
    int i = 0;
    while(s[i] == 0)
        i++;
    for(int j = 0; i < MAXN;)
    {
        s[j++] = s[i++] + 48;
        s[i-1] = 0;
    }
}// 左移函数，作用是向左对齐
void add(char *s1,char *s2,char *ans)
{
    memset(ans,0,sizeof ans);
    int len1=strlen(s1),len2=strlen(s2);
    int len=len1>len2?len1:len2;
    right_move(s1);
    right_move(s2);// 这里两行我们进行向右对齐，以便模拟
    for(int i=MAXN-1;i>=MAXN-len;i--)
    {
        ans[i]+=s1[i]+s2[i];    // 这里进行'+'的操作
        ans[i-1]=ans[i]/10;       //进位
        ans[i]=ans[i]%10;
    }
    left_move(ans);
}
int main()
{
    scanf("%s%s",s1,s2);
    add(s1,s2,ans);
    printf("%s",ans);
}

高精度减法[3]

  1. 和加法一样，我们需要以字符串来读入。
  2. 首先要比较被减数和减数的大小，如果被
    减数小于减数，我们应该拿减数来减去被
    减数，并在结果前加‘-’。
  3. 考虑大小的时候优先考虑长度，若长度相等，则可以作为字符串直接比
    较大小。
  4. 比较大小后，拿大的减小的，如高精加，用加法模拟。
  5. 先将两个数右对齐，然后，逐位做减法，
    减法要考虑借位，如果某一位不够减，则
    向它左边借位。

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1005
char s1[MAXN], s2[MAXN], ans[MAXN];
inline void right_move(char *s)       //右移
{
    int len = strlen(s);
    for(register int i = len - 1, j = MAXN - 1; i >= 0; i--, j--)
    {
        s[j]=s[i]-48;
        s[i]=0;
    }
}
inline void left_move(char *s)        //左移
{
    int i = 0;
    while(s[i] == 0)
        i++;
    for(int j = 0; i < MAXN;)
    {
        s[j++] = s[i++] + 48;
        s[i-1] = 0;
    }
}
inline int cmp(char *s1, char *s2)    //这个是比较两个字符串大小的函数
{
    int len1 = strlen(s1), len2 = strlen(s2);
    if(len1 > len2)
        return 1;
    else if(len1 < len2)
        return -1;
    else 
        return strcmp(s1, s2);
}
void sub(char *s1,char *s2,char *ans)   //这个显然就是高精减♂啦~
{
    memset(ans,0,sizeof ans);
    int len1 = strlen(s1), len2 = strlen(s2);
    int len = len1 > len2 ? len1 : len2;
    right_move(s1);
    right_move(s2);
    for(register int i = MAXN - 1; i >= MAXN - len; i--)
    {
        ans[i] += s1[i] - s2[i];
        if(ans[i] < 0)
        {
            ans[i - 1]--;
            ans[i] += 10;
        }
    }
    left_move(ans);
    return ;
}
int main()
{
    scanf("%s%s",s1,s2);
    if(cmp(s1,s2)>0)
    {
        sub(s1,s2,ans);
        printf("%s",ans);
    }
    else if(cmp(s1,s2)<0)
    {
        sub(s2,s1,ans);
        printf("-%s",ans);
    }
    else 
        printf("0");
}

高精度乘法[4]

同样有几个点需要注意:

  1. 还是用字符串输入
  2. 最后ans数组的长度应为a+b位才不会出问题。
  3. 采用左对齐更方便

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
char num1[maxn], num2[maxn], res[maxn];
void multi(char *s1, char *s2, char *s3)
{
    int len1 = strlen(s1), len2 = strlen(s2);
    for(register int i = 0; i < len1; i++)
    {
        for(register int j = 0; j < len2; j++)
            s3[i + j + 1] += (s1[i] - 48) * (s2[j] - 48);
        for(register int k = len1 + len2 - 1; k > 0; k--)
        {
            s3[k - 1] += s3[k] / 10;
            s3[k] = s3[k] % 10;
        }
    }
    return ;
}
int main()
{
    scanf("%s",num1);
    scanf("%s",num2);
    int len1 = strlen(num1), len2 = strlen(num2);
    multi(num1, num2, res);
    int i = 0;
    while(res[i] == 0 && i < len1 + len2)
        i++;
    if(i == len1 + len2)
        printf("0");                                       //结果为0的情况
    else
    {
        for(; i < strlen(num1) + strlen(num2); i++)
        printf("%c", res[i] + 48);
    }
    return 0;
}

高精度除法[5]

  1. 还是模拟竖式除法
  2. 我们不好估算商是多少，可以换成减法，
    不断的减去除数。
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2005
char num1[MAXN], num2[MAXN], res[MAXN];
int i,j,k,len1, len2, d = 0;
int mycmp(char *s1,char *s2,int start,int end)

    if(end - start + 1 > len2)
        return 1;
    else if(end - start + 1 < len2)
        return -1;
    else 
        return strncmp(s1 + start, s2, len2);
}
int main()
{
    scanf("%s",num1);
    scanf("%s",num2);
    len1 = strlen(num1), len2 = strlen(num2);
    int start = 0, end = len2;
    while(1)
    {
    end = start + len2 - 1;
    while(end < len1 && mycmp(num1, num2, start, end) < 0)
         end++;//不够除时，end往后移
    if(end >= len1)
        break;
    while(mycmp(num1, num2, start, end) >= 0)
    {
        for(i=len2-1,j=end;i>=0;i--,j--)
        {
            if(num1[j]<num2[i])
            {
                num1[j]+=10;
                num1[j-1]--;
            }
            num1[j]=num1[j]-num2[i]+48;//用减法来做除法
        }
        res[end]++;//减一次，该位的商增加1
        while(start < len1 && num1[start] == '0')
            start++;//被除数前面的0跳过
    }
}

当然 是惯例，在最后 肯定会有一个菜单：一个封装了简单高精度的结构体

好东西模板

#include <bits/stdc++.h>
using namespace std;
#define Max(a,b) ((a)>(b)?(a):(b))
#define LL long long
struct bignum
{
    LL a[2000],lim; 
    int len;
    bignum(){ 
        memset(a, 0, sizeof(a)); 
        len = 1; lim = 100000000LL; 
    } 
    bool operator<(const bignum &b) const
    {
        if(len < b.len) 
            return 1;
        if(len > b.len) 
            return 0;
        for(register int i = len; i >= 1; --i) 
        {
            if(a[i] < b.a[i]) 
                return 1;
            if(a[i] > b.a[i]) 
                return 0;
        }
        return 0;
    }
    void operator+=(const bignum &b) 
    {
        len = Max(len, b.len);
        for(register int i = 1; i <= len; ++i) 
            a[i] += b.a[i]; 
        for(register int i = 1; i <= len; ++i)
        { 
            a[i + 1] += a[i] / lim; 
            if(i == len && a[i + 1]) 
                ++len; 
            a[i] %= lim; 
        }
    }
    bignum operator + (const bignum &b) const
    { 
        bignum c = *this;
        c += b; 
        return c;
    } 
    void operator -= (const bignum &b) 
    {
        for(register int i = 1; i <= len; ++i) 
        {
            a[i] -= b.a[i];
            if(a[i]<0)
                a[i] += lim, --a[i+1];
        }
        for(; len>1 && !a[len]; --len);
    }
    bignum operator-(const bignum &b) const
    {
        bignum c = *this; 
        c -= b;
        return c;
    }
    void operator*=(LL b) 
    {
        for(register int i=1;i<=len;++i)
            a[i] *= b;
        for(int i=1;i<=len;++i){
            a[i+1]+=a[i]/lim;
            if(i==len && a[i+1]) ++len;
            a[i]%=lim;
        }
    }
    bignum operator*(LL b) const
    { 
        bignum c=*this; c*=b; 
        return c; 
    } 
    void operator*=(const bignum &b) 
    { 
        bignum c; c.len=len+b.len-1; 
        for(LL i=1;i<=len;++i) 
            for(LL j=1;j<=b.len;++j) 
                c.a[i+j-1]+=a[i]*b.a[j]; 
        for(LL i=1;i<=c.len;++i){ 
            c.a[i+1]+=c.a[i]/lim; 
            if(i==c.len && c.a[i+1]) ++c.len; 
            c.a[i]%=lim; 
        } 
        *this=c; 
    } 
    bignum operator*(const bignum &b) const
    { 
        bignum c=*this; c*=b; 
        return c; 
    } 
    void operator/=(LL b) 
    { 
        for(LL i=len;i>1;--i){ 
            a[i-1]+=a[i]%b*lim; 
            a[i]/=b; 
        } 
        for(a[1]/=b;len>1 && !a[len];--len); 
    } 
    bignum operator/(const LL &b) const
    {
        bignum c=*this; c/=b;
        return c;
    }
    void operator/=(const bignum &b) 
    { 
        LL i,j,l,r,mid; 
        bignum c, _b , res;
        if (*this<b) {
            *this=res;
            return;
        }
        res.len = len-b.len+1; 
        for(i = res.len; _b=b,l=0,r=lim,i>=1; --i){ 
            for(j=1; j < i; ++j) _b*=lim;
            while(l<r){
                mid=(l+r+1)>>1;
                c = _b*mid;
                if(*this<c) r=mid-1;
                else l=mid;
            }
            *this-=_b*l; res.a[i]=l; 
        }
        for(*this=res;len>1 && !a[len];--len); 
    } 
    bignum operator/(const bignum &b) const
    {
        bignum c=*this; c/=b;
        return c;
    }
    void Read(char *s)
    {
        len=strlen(s);
        for (LL i=0,j;j=(len-i-1)/8+1,i<len;i++)
            a[j]=a[j]*10+s[i]-'0';
        if (len%8) len=len/8+1;
        else len/=8;
    }
    void Print()
    {
        printf("%I64d",a[len]);
        for(LL i=len-1;i>=1;i--)
            printf("%08I64d",a[i]);
        printf("\n");
    } 
};
int main()
{

    return 0;
}

高精度第一阶的算法笔记，请大家点下赞，在评论区指出错误QAQ

  1. 这个算法的思路还是很清晰的，我们只需要开两个字符数组，然后我们进行模拟竖式加法，有几个点需要注意一下 ↩︎

  2. 显然是在最后的时候向左移来输出哒啦QAQ~ ↩︎

  3. 这个玩意儿比高精度加乘难（一些？），但是这是低级运算，和加法一个档次的，所以先讲它 ↩︎

  4. 到了二级运算啦(～￣▽￣)～ ↩︎

  5. 长+难得一批 ↩︎

原文链接: https://www.cnblogs.com/Quantum-Coke-Machine/p/12372770.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    关于高精度

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/332355

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月1日 下午6:27
下一篇 2023年3月1日 下午6:27

相关推荐