温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

使用C++怎么实现一个高精度算法

发布时间:2021-04-16 18:03:50 来源:亿速云 阅读:289 作者:Leah 栏目:编程语言

这期内容当中小编将会给大家带来有关使用C++怎么实现一个高精度算法,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。

1. 高精度加法

以3479957928375817 + 897259321544245为例:

3479957928375817
+897+2593+2154+4245
====
437612172499110062
进位0进位1进位0进位1
4377217249920062

C语言实现代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}


//High Precision Of Addition
int main()
{
  char stra[N], strb[N];   //字符串数组,以字符形式储存两个大数;
  int i = 0, step = 4, carry = 0; //step表示块长,carry为进位位;
  int lengtha, lengthb, maxlength, resultsize;  //maxlength表示stra和strb二者长度较大的那个;
  int numa[N], numb[N],numc[N];  //依次储存被加数,加数,和;
  memset(numa, 0, sizeof(numa));
  memset(numb, 0, sizeof(numb));
  memset(numc, 0, sizeof(numc));     //初始化为零;
  scanf("%s%s", stra, strb);
  lengtha = strlen(stra);
  lengthb = strlen(strb);   //计算两个大数的长度
  //字符数字转为四位一块的整数数字
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }
  for(i = lengthb-1; i >= 0; --i)
  {
    numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
  }
  maxlength = lengtha > lengthb ? lengtha : lengthb;

  //逐块相加,并进位
  for(i = 0; i <= maxlength/step; ++i)
  {
    numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry;  //计算和
    carry = (numa[i] + numb[i])/Pow(10, step); //计算进位
  }

  //计算最后和的块的总数
  resultsize = numc[maxlength/step] > 0 ? maxlength/step : maxlength/step - 1;
  printf("%d", numc[resultsize]);
  for(i = resultsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //右对齐,补零输出;
  }
  printf("\n");
  return 0;
}

2. 高精度减法

与加法类似,不同的是要注意正负号和显示位数的变化。以99999037289799 - 100004642015000为例:

先判断被减数和减数哪个大,显然这里减数大,故输出结果为负数。在用大数减去小数,(若某一块相减为负数,则要向高位块借位)如下表

100004642015000
-99-9990-3728-9799
1564735201
借位0借位1借位0借位1
0564725201

C语言实现代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}

//High Precision Of Subtraction
int main()
{
  char stra[N], strb[N];   //字符串数组,以字符形式储存两个大数;
  int i = 0, step = 4, borrow = 0, mark = 0; //step表示块长,borrow为借位位, mark为结果符号位;
  int lengtha, lengthb, maxlength, resultsize;  //maxlength表示stra和strb二者长度较大的那个;
  int numa[N], numb[N],numc[N], *maxnum, *minnum;  //依次储存被减数,减数,和;
  memset(stra, 0, sizeof(stra));
  memset(strb, 0, sizeof(strb));
  memset(numa, 0, sizeof(numa));
  memset(numb, 0, sizeof(numb));
  memset(numc, 0, sizeof(numc));     //初始化为零;
  scanf("%s%s", stra, strb);
  lengtha = strlen(stra);
  lengthb = strlen(strb);   //计算两个大数的长度
  maxlength = lengtha >= lengthb ? lengtha : lengthb;

  //字符数字转为四位一块的整数数字
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }
  for(i = lengthb-1; i >= 0; --i)
  {
    numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
  }

  //找出较大的数
  maxnum = numa;
  minnum = numb;
  mark = 1;
  for(i = (maxlength-1)/step; i >= 0; --i)
  {
    if(numa[i] > numb[i])
    {
      maxnum = numa;
      minnum = numb;
      mark = 1;
      break;
    }
    else if(numa[i] < numb[i])
    {
      maxnum = numb;
      minnum = numa;
      mark = -1;
      break;
    }
  }

  //逐块相减,并借位
  for(i = 0; i <= maxlength/step; ++i)
  {
    numc[i] = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)%Pow(10,step);  //计算差
    borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1; //计算借位
  }

  //计算最后和的块的总数
  resultsize = maxlength/step;
  while(!numc[resultsize])  --resultsize;
  printf("%d", mark*numc[resultsize]);
  for(i = resultsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //右对齐,补零输出;
  }
  printf("\n");
  return 0;
}

3. 高精度乘法

乘法可以看作是乘数每一位与被乘数相乘后再相加,以4296556241 x 56241为例:

被乘数4296556241
乘数56241
被乘数x乘数4296556241
14296556241
4168*1038620*1024964*10
284*10019310*10012482*100
6252*100057930*100037446*1000
5210*1000048275*1000031205*10000
累加和2362122543006855351000081
进位(从低位向高位)2415430435100
241642619550081

C语言实现代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}


//High Precision Of Multiplication
int main()
{
  char stra[N], strb[N];   //字符串数组,以字符形式储存两个大数;
  int i = 0, j = 0, k = 0, step = 4, carry = 0; //step表示块长,carry为进位位;
  int lengtha, lengthb, resultsize, tmpsize, eachnum; //resultsize储存块的总数,eachnum用来储存乘数的每一位
  int numa[N], numb[N], numc[N], tmp[N];  //依次储存被乘数数&积,乘数;
  memset(numa, 0, sizeof(numa));
  memset(numb, 0, sizeof(numb));
  memset(numc, 0, sizeof(numc)); //初始化为零;
  scanf("%s%s", stra, strb);
  lengtha = strlen(stra);
  lengthb = strlen(strb);   //计算两个大数的长度
  //将被乘数字符数字转为四位一块的整数数字
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }
  //将乘数数字字符数字转为一位一块的整数数字
  for(i = lengthb-1; i >= 0; --i)
  {
    numb[lengthb-1-i] = strb[i]-'0';
  }

  resultsize = tmpsize = (lengtha-1)/step;
  //取乘数的每一位与被乘数的逐块相乘,并进位;
  for(i = 0; i < lengthb; ++i)
  {
    memcpy(tmp, numa, sizeof(numa));  //将numa数组赋值给tmp数组;

    k = i/step;   //k储存每一块需要向高位块移动的次数;
    if(k)
    {
      for(j = tmpsize; j >= 0; --j)
      {
        tmp[j+k] = tmp[j];
        tmp[j] = 0;
      }
      tmpsize += k;
    }

    //乘以乘数每一位扩展成的块;
    eachnum = numb[i]*Pow(10, i%step);
    for(j = 0; j <= tmpsize; ++j)
    {
      tmp[j] *= eachnum;
    }

    //大数相加
    carry = 0; //进位置零;
    for(j = 0; j <= resultsize; ++j)
    {
      numc[j] += tmp[j] + carry;
      carry = numc[j]/Pow(10,step);
      numc[j] %= Pow(10, step);
    }
    if(carry)
    {
      ++resultsize;
      numc[j] += carry;
    }
  }

  //输出
  printf("%d", numc[resultsize]);
  for(i = resultsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //右对齐,补零输出;
  }
  printf("\n");
  return 0;
}

4. 高精度除法

高精度除法有两种,一种是高精度除以低精度,另一种是高精度除以高精度。前者只需将每一块除以低精度除数即可;后者则考虑用高精度减法来实现,即每次减去高精度除数,直到减到小于除数,则减的次数即为商,剩余的即为余数。

高精度除以低精度
以9876342876 / 343为例:

被除数9876342876
除数343
向低位块进位98137190
028794002
余数190

C语言代码实现如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}

//High Precision Of division
//(1)高精度除以低精度
int main()
{
  char stra[N];   //字符串数组,以字符形式储存高精度被除数;
  int i = 0, step = 4, carry = 0; //step表示块长,carry为高位向低位进位位;
  int lengtha, resultsize;
  int numa[N], numb, numc[N], numd;  //依次储存被除数,除数,商, 余数;
  memset(numa, 0, sizeof(numa));
  memset(numc, 0, sizeof(numc));     //初始化为零;
  scanf("%s%d", stra, &numb);
  lengtha = strlen(stra);  //计算被除数的长度

  //字符数字转为四位一块的整数数字
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }

  carry = 0; //高位向低位进位位置零
  resultsize = (lengtha-1)/step;
  //逐块相除,高位向低位进位
  for(i = resultsize; i >= 0; --i)
  {
    numc[i] = (numa[i] + carry*Pow(10,step))/numb;  //计算商
    carry = (numa[i] + carry*Pow(10,step))%numb; //计算进位
  }
  numd = carry;  //最低位块的余数即为整个除法的余数

  //计算最后和的块的总数
  while(!numc[resultsize])  --resultsize;
  //输出商
  printf("%d", numc[resultsize]);
  for(i = resultsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //右对齐,补零输出;
  }
  //输出余数
  printf("\n%d\n", numd);
  return 0;
}

高精度除以高精度
以176342876 / 3453452为例:

被除数176342876
- (51 x 除数)51 x 3453452
余数216824
51

C语言代码实现如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}

//High Precision Of division
//(2)高精度除以高精度
int main()
{
  char stra[N], strb[N];   //字符串数组,以字符形式储存两个大数;
  int i = 0, step = 4, borrow = 0; //step表示块长,borrow为进位位;
  int lengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark;  //maxlength表示stra和strb二者长度较大的那个;
  int numa[N], numb[N], numc[N], numd[N];  //依次储存被除数数,除数数,商,余数;
  memset(stra, 0, sizeof(stra));
  memset(strb, 0, sizeof(strb));
  memset(numa, 0, sizeof(numa));
  memset(numb, 0, sizeof(numb));
  memset(numc, 0, sizeof(numc));
  memset(numd, 0, sizeof(numd));   //初始化为零;
  scanf("%s%s", stra, strb);
  lengtha = strlen(stra);
  lengthb = strlen(strb);   //计算两个大数的长度

  //字符数字转为四位一块的整数数字
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }
  for(i = lengthb-1; i >= 0; --i)
  {
    numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
  }
  memcpy(numd, numa, sizeof(numa));
  numbsize = (lengthb-1)/step;
  numcsize = 0;
  numdsize = (lengtha-1)/step;

  do
  {
    maxsize = numdsize > numbsize ? numdsize : numbsize;
    //计算剩余数是否小于除数
    mark = 1;
    for(i = maxsize; i >= 0; --i)
    {
      if(numd[i] > numb[i])
      {
        mark = 1;
        break;
      }
      else if(numd[i] < numb[i])
      {
        mark = -1;
        break;
      }
    }

    //判断是否余数已经小于除数
    if(!(mark+1))  break;

    borrow = 0; //借位置零;
    //逐块相减,并借位
    for(i = 0; i <= maxsize; ++i)
    {
      tmpnum = (numd[i] - numb[i] + Pow(10, step) + borrow)%Pow(10,step);  //计算差
      borrow = (numd[i] - numb[i] + Pow(10, step) + borrow)/Pow(10,step) - 1; //计算借位
      numd[i] = tmpnum;
    }
    while(!numd[numdsize]) --numdsize;

    //每减一个除数,商加一;
    borrow = 1;
    for(i = 0; i <= numcsize; ++i)
    {
      numc[i] += borrow;
      borrow = numc[i]/Pow(10,step);
      numc[i] %= Pow(10,step);
    }
    if(borrow)
    {
      ++numcsize;
      numc[i] += borrow;
    }
  }while(1);

  printf("%d", numc[numcsize]);
  for(i = numcsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //右对齐,补零输出;
  }
  printf("\n");
  printf("%d", numd[numdsize]);
  for(i = numdsize-1; i >= 0; --i)
  {
    printf("%04d", numd[i]);  //右对齐,补零输出;
  }
  printf("\n");
  return 0;
}

上述就是小编为大家分享的使用C++怎么实现一个高精度算法了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++
AI