精华内容
下载资源
问答
  • C++实现高精度计算类库,包含了FFT的乘法除法,开平方,用法类似java的bigint,实测速度比java的快很多
  • c++高精度乘法,字符串做法,支持50000位两数相乘,希望大佬帮助改进。Thanks♪(・ω・)ノ
  • c++高精度时间纳秒

    2018-06-25 13:46:36
    用于代码测试性能,可以得出代码执行时间,以便优化代码 可以获得纳秒级别的时间差 //时 //分 //秒 //纳秒 //微妙 //毫秒
  • C++高精度计算器

    2015-02-11 10:01:29
    C++高精度计算器。 高精度范例 代码简洁。明了。
  • 高精度模版C++

    2018-07-18 14:45:56
    高精度模版,C++版本,coder必备技能之一,你值得拥有。
  • 这个版本的高精度整数库不仅支持高精度高精度,同时修复了减法计算中的一个严重的bug。并支持高精度类型与其他一切可转换为高精度类型的类型(int,long long,unsignd,string)进行混合运算。同时,全面优化了除法、...
  • c++高精度算法

    千次阅读 2020-08-05 10:29:09
    这是我的第一篇高精度文章。 什么是高精度 有时,我们要做特别大数据的计算。多大呢?几百万位,远远超过了long long的数据范围,直接用long long肯定会溢出。这时候我们就要用高精度算法 PS:python自带高精度 所有...

    c++语言

    什么是高精度

    有时,我们要做特别大数据的计算。多大呢?几百万位,远远超过了long long的数据范围,直接用long long肯定会溢出。这时候我们就要用高精度算法
    PS:python自带高精度

    所有高精度算法的基本原理

    大体的思路,就是用字符数组(因为字符数组可以达到一个下标对应一个数字,达到按位处理的目的),然后转到整形数组(整型数组才能进行计算)一个下标对应一个数字,用另一个数组进行按位相加。

    高精度运算

    现在只写高精度加法、乘法。以后会逐渐补充

    加法

    思路分析

    我们用数学竖式的方法来分析
    别说这不是高精度,原理一样的,要不你来写个几百万位的竖式(防杠精)
    在这里插入图片描述
    这是小学数学的知识 对应位相加,有进位的加到下一位。

    现在,按照刚才的思路进行模拟。仍然是134+84。但存到计算机中,再按位相加,变成了这样:
    在这里插入图片描述
    对于这种错位的情况,我们一般采取的办法是倒序存储(先不说代码如何实现)。于是就是这样:
    在这里插入图片描述
    就是结果也是反着的。但是没关系,我们再进行倒序输出。218,没错!

    代码

    有了上面的说明,代码就很好懂了。

    #include<iostream>
    #include<cstring>
    using namespace std;
    int main(){
    	int add1=0; //专门处理最后输出时进位的问题
    	int a[1000]={},b[1000]={},c[2000]; //分别对应加数1,加数2,和
    	char a1[1000],b1[1000];
    	//1.输入、转换
    	cin>>a1>>b1;
    	//因位数可能不同,所以倒序存储要分两次完成
    	for(int i=0;i<strlen(a1);i++){
    		a[strlen(a1)-1-i]=a1[i]-'0'; //至于如何倒序存储,自己举例子思考,自行理解即可
    	}
    	for(int i=0;i<strlen(b1);i++){
    		b[strlen(b1)-1-i]=b1[i]-'0';
    	}
    	//2.按位计算
    	for(int i=0;i<max(strlen(a1),strlen(b1));i++){ //注意要用最大长度,否则计算不完
    		c[i]+=a[i]+b[i]; //对应位相加。要写+=是因为进位数据以提前存好,用=会丢失数据
    		c[i+1]=c[i]/10; //把进位存到下一位
    		c[i]%=10; //把这一位模10,仅保留个位
    		//【上边的两行顺序一定不能反,否则进位数据会丢失】
    	}
    	//3.输出
    	//因为是加法,所以和比加数的最大长度最多只会多一位,所以只需判断一次
    	if(c[max(strlen(a1),strlen(b1))]!=0){
    		add1=1; //如果不是0,则说明有进位,需要多输出一次
    	}
    	for(int i=max(strlen(a1),strlen(b1))+add1-1;i>=0;i--){
    		cout<<c[i];
    	}
    	return 0;
    }
    

    乘法

    思路分析

    有了前边加法的基础,应该很容易想到,乘法也需要倒序存储。
    这里我就不多说了。
    在这里插入图片描述
    需要解释的地方如下:
    1.核心计算部分
    高精度乘法,实际上就是用加法模拟乘法。用乘法分配律就很好懂:

    123*45=123*(40+5)=123*40+123*5

    在用高精度计算时,也是一样的,只是进位处理不一样。我们用一个新的数组存储答案(这里定为c[2000]={})数组下标从1开始用,c[1]+=3*5,c[1]+=2*5……,c[2]+=3*4,……
    在我加粗的部分,很明显,不是从下标1开始了。原因很简单,自行列竖式理解
    2.处理进位部分
    这里处理进位的方法比较特殊,大体思路是把这一位除以10的结果加到下一位,并对这一位模10;下一位仍然这样,再下一位……

    代码

    再强调一次,此代码数组下标是从1开始用的

    #include<iostream>
    using namespace std;
    int main(){
    	string a1,b1;
    	int a[2000]={},b[2000]={},c[5000]={};
    	cin>>a1>>b1;
    	for(int i=1;i<=a1.length();i++){ //倒序存储
    		a[i]=a1[a1.length()-i]-'0';
    	}
    	for(int i=1;i<=b1.length();i++){
    		b[i]=b1[b1.length()-i]-'0';
    	}
    	for(int i=1;i<=b1.length();i++){ //核心计算部分,具体解释请看思路分析
    		for(int j=1;j<=a1.length();j++){
    			c[i+j-1]+=a[j]*b[i];
    		}
    	}
    	for(int i=1;i<a1.length()+b1.length();i++){ //处理进位部分,具体解释请看思路分析
    		if(c[i]>9){
    			c[i+1]+=c[i]/10;
    			c[i]%=10;
    		}
    	}
    	int chu=a1.length()+b1.length(); //用来处理多余的前导0
    	while(c[chu]==0 && chu>1){ //如果计算结果为0,必须保留最后一位0,所以chu必须同时>1
    		chu--;
    	}
    	for(int i=chu;i>=1;i--){ //倒序输出,没说的
    		cout<<c[i];
    	}
    	return 0;
    }
    

    推荐阅读

    我的个人博客
    我的个人网站

    展开全文
  • 用C/C++实现基本高精度计算

    千次阅读 2020-11-23 14:57:09
    高精度计算 什么是高精度 高精度算法 高精度数的读写 高精度加法 高精度减法 高精度乘法 高精度除法及求余 (前置技能:小学数学知识,C语言基础) 什么是高精度 我们知道,C/C++在64位编译器中支持的环境下,其各种...

    (前置技能:小学数学知识,C语言基础)

    什么是高精度

    我们知道,C/C++在64位编译器中支持的环境下,其各种整型数据类型表示是有范围的。

    类型名             			 		  	  取值范围
    signed char        			   		     -128~127
    unsiged char					  	  	    0~255
    short int        			  	       -32768~32767
    int            		 			  -2147483648~2147483647
    unsigned int								0~4294967295
    long         	          		  -2147483648~2141483647
    unsigned long 								0~4294967295
    long long 	 		     -9223372036854775808~9223372036854775807
    unsigned long long 						    0~18446744073709551615
    

    尽管long long类型(或者在有些编译器中表示为__int64.注意int64前面有2个下划线)能表示的数已经相当大了,但和一些天文数字比起来,它连屏幕的一行都占不到。很多实际数学问题其实是long long也无法解决的。
    例如,围棋的走法有3的361次方,这个数字怎么显示出来?宇宙中原子的总和是10的80次方,怎么显示出来?这些都是语言本身的数据类型无法表示的。实际上,这些数字如果用二进制去储存的话,需要的空间也是特别大的。为了节约空间,同时让我们能够算出这些大数据,我们需要一种应用数组进行模拟计算的方法——高精度计算。

    高精度算法

    提醒:本博文该部分的所有代码均只用于展示计算原理,如果要整合在一起并进行更加复杂的符合操作,会产生诸多bug(其实直接复制粘贴任何一段都可能会有问题)总之就是,在这里找不到板子啦

    高精度数的读写

    1. 读入高精度数
      直观地输入一个高精度数时,我们需要存储一个有很多很多位的数字.
      如何存储?最直接的方法就是将它存入一个字符串.
      例如,我们可以这样:
    char str[100] = {""};//100表示数据可能的最大位数.
    scanf("%s, &str);
    

    这种输入方式再简单不过了,我们输入“43983926969436339448266492\n”
    则数据“43983926969436339448266492”就被存入其中了
    (提示:彩蛋数据)
    2. 存储高精度数
    现在,数据的读取完成了,我们应该如何处理这个数,让他变得方便于计算呢?
    我们不妨再设置一个数组,然后将输入的数逆序存入,也就是将str的最后一位存入数组a的第0位、将str的倒数第二位存入数组a的第1位……

    #include <string.h>
    
    int a[100] = {0};//100应该为这个数据可能的最大位数.
    for(int i = 0; i < strlen(str); ++i)
    	a[i] = str[strlen(str) - i - 1] - '0';
    

    这个时候就有人会问了:为什么要逆序存储?
    这是因为,数据的长度毕竟不确定,高精度计算既然是利用数组计算,应当是需要每一位每一位对齐再处理运算. 如果顺序存储,两个数长度不一样,最后一位的下标也不同,最后处理运算时最后一位不能直接对齐,还要经过一个移位的操作,显然加大了计算机的操作量. 反之,如果我们采取逆序存储的方式,存入的数组从第0位开始依次是个位、十位、百位……这些对应关系不会随着数据的长度改变而改变,有利于后面对两个高精度数进行运算.
    ——————————————————————————

    高精度加法

    了解了高精度的输入与存储后,我们可以定义一个表示高精度数据的结构体:

    #define LEN 1001//假定1001是我们处理的所有数据的最大位数
    
    struct hp{
        char str[LEN];
        int a[LEN];
    };
    

    为了进行加法,我们可以先准备3个结构体,分别作为两个加数和和. 注意定义后,为了正确输入并在后续输出时检查前导0, 应该将结构体的字符数组初始化为空串,将a数组全部初始化为0.

    void init(struct hp *x)//初始化函数
    {
    	for(int i = 0; i < LEN; ++i)
    	{
    		x->a[i] = 0;
    		x->str[i] = '\0';
    	}
    }
    

    如何进行高精度的加法?
    回想小学数学,那一个个竖式,逢十进一,简便美观的十进制表达……哦,我的上帝,多么纯粹简朴的方法啊!
    于是,高精度加法,其实就是基于竖式运算原理的啦~正因如此,我们才需要对齐两个加数.
    加法:
    先获取两个加数中最大的位数len,则本次加法计算需要进行len次操作. 从第0位开始,每次将对应位相加,得到和在该位的数值. 如果和在该位的数值大于等于10,那么将其减掉10,并让高一位加1.

    void add(struct hp x, struct hp y, struct hp *ans)
    {
        int len = 0;
        if(strlen(x.str) > strlen(y.str))
            len = strlen(x.str);
        else len = strlen(y.str);
        for(int i = 0; i < len; ++i)
        {
            ans->a[i] += x.a[i] + y.a[i];
            while(ans->a[i] >= 10)
            {
                ans->a[i] -= 10;
                ans->a[i + 1]++;
            }
        }
    }
    

    加法计算器完整代码:

    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #define LEN 1001//假定该程序处理的数据都是小于1000位的.
    /*最长位数1001是为了安全.*/
    
    struct hp{
        char str[LEN];
        int a[LEN];
    };//创建结构体hp(high-precision)
    //注意使用指针,这样来通过指针形参修改传入的实参.
    void init(struct hp *x)//hp初始化函数
    {
    	for(int i = 0; i < LEN; ++i)
    	{
    		x->a[i] = 0;
    		x->str[i] = '\0';
    	}
    }
    void in(struct hp *x)//输入函数.
    {
        scanf("%s", &x->str);
        int len = strlen(x->str);
        for(int i = 0; i < len; ++i)
            x->a[i] = x->str[len - i - 1] - '0';
    }
    void add(struct hp x, struct hp y, struct hp* ans)//加法函数
    {
        int len = 0;
        if(strlen(x.str) > strlen(y.str))
            len = strlen(x.str);
        else len = strlen(y.str);
        for(int i = 0; i < len; ++i)
        {
            ans->a[i] += x.a[i] + y.a[i];
            while(ans->a[i] >= 10)
            {
                ans->a[i] -= 10;
                ans->a[i + 1]++;
            }
        }
    }
    void show(struct hp ans)//输出函数
    {
        int j = LEN - 1;//数组有LEN位,其最后一个下标是LEN-1.
        while(ans.a[j] == 0 && j >= 1)
            --j;//跳过所有前导0.
            /*注:为了确保能输出结果0,前导0最多跳到第一位,
            不检查第0位是否为0,因此加了条件j >= 1.*/
           //现在,j的值是我们要输出的这个结果的最大位的下标.
        while(j >= 0)
        {
            printf("%d", ans.a[j]);
            --j;
        }
        printf("\n");
    }
    int main()
    {
        struct hp x, y, ans;
        init(&x);
        init(&y);
        init(&ans);
        in(&x);
        in(&y);
        add(x, y, &ans);
        show(ans);
        return 0;
    }
    
    

    以上就是进行高精度加法的过程了.


    高精度减法

    实现高精度减法,我们同样可以用三个结构体. 原理与加法相似,仍然是竖式原理:
    先获取被减数的位数len,则本次减法计算需要进行len次操作. 从第0位开始,每次将对应位相减,得到和在该位的数值. 如果和在该位的数值小于0,那么将其加上10,并让高一位减1.

     void minus(struct hp x, struct hp y, struct hp* ans)
    {
        int len = strlen(x.str);
        for(int i = 0; i < len; ++i)
        {
            ans->a[i] += x.a[i] - y.a[i];
            while(ans->a[i] < 0)
            {
                ans->a[i] += 10;
                ans->a[i + 1]--;
            }
        }
    }
    

    但是这样的减法是无法计算结果为负数的情况. 例如1 - 10.为了解决减法出现负数的问题,我们需要往结构体中添加一个表示正负的符号. 例如,添加一个bool值,并定义一个比较函数,利用其比较被减数和减数的大小(此处比较函数就交给你们啦). 当减数大于被减数,让设置的bool值为0,反之为1. 当bool值为1时直接进行减法运算. 如果bool值为0,就返回用减数减去被减数的结果.
    同样地,利用这个表示符号位的布尔值,我们还可以定义含有负数的加法,等等……


    高精度乘法

    要进行高精度乘法,我们会如何去操作?
    竖式乘法?我们很容易想到这样的方式:
    计算123 * 52,
    首先列竖式,让123乘以2,也就是让每一位乘以2,得到246.
    然后让123每一位乘以5,得到615(这里隐含了进位操作).
    最后,因为5是十位,它的位权是10,所以615修正为6150.
    让6150+246,得到结果6396.
    这个算法是可行的,让我们来看它的步骤应该如何设计:

    1. 首先获取被乘数和乘数的长度len1,len2;
    2. 定义len2个高精度数 a[len2],它们作为被乘数与乘数每一位分别相乘的结果;
    3. 每个 a[i] 拥有一个位权 j ,j 决定在后续处理中将所有 a[i] 相加时每个a[i] 要乘以10的幂数;
      (说白了就是为了模拟竖式乘法最后相加的过程)
    4. 取出乘数的第 i 位,让被乘数的每一位乘以这个数 ,并把乘得的结果存入a[i] 对应的位.
      (例如上方例子,123乘以5的时候,位权j为1,我们应当将结果15、 10、 5分别存入 a[1] 的第1(j + 0)位,第2(j + 1)位,第3(j + 2)位. 这里的a[1] 就是 {0,5,10,15} 了. 同理,我们知道 a[0] 为 {2,4,6}.)
    5. 最后一步和自然的竖式乘法的最后一步一致,让所有的 a[i] 相加. 因为我们在之前的讨论中已经封装了高精度的加法,并且进位判定都是用的while语句,因此无论 a[i] 的第几位有多大,最后相加的过程中也能利用进位得到正确结果了.

    代码实现:

    void multi(struct hp x, struct hp y, struct hp* ans)
    {
    	int len1 = strlen(x.str);
    	int len2 = strlen(y.str);
    	struct hp A[len2];//乘数有len2位.
    	/*这里应该还有一个使所有A.a[i]初始化为0的操作.
    	这里只展示乘法原理,略去.*/
    	for(int i = 0; i < len2; ++i)
            {
                //每个因子进i位.
                int n = y.a[i];//注意取n为被乘数的第i位.
                //让A[i]的每一位都乘上这个数.
                int u = i;
                for(int j = u; j < u + len1; ++j)
                    A[i].a[j] = x.a[j - u] * n;
            }
            //让所有因子相加.
            for(int i = 0; i < len2; ++i)
            {
            	struct hp tmp;
              	ans = add(ans, A[i], tmp);
            }
            return ans;
    }
    

    高精度除法及求余

    高精度除法的原理仍然是基于竖式除法……只不过,为了方便代码更加容易理解,我们不妨换一种方式解释.
    譬如,我们现在要计算1234除以9.

    1. 首先,获取最大位是4.将其减1得到3.
    2. 9乘以10的3次幂,得到9000.
    3. 用1234减去9000,结果小于0,有效的减法为0次. 在结果的千位放置0.
    4. 将9000降幂变为900,用1234减去900,得到334. 再减一个900,小于0. 有效的减法为1次,在结果的百位放置1.
    5. 将900降幂得到90,用334减去90,可以减3次,得到64. 有效的减法为3次,在结果的十位放置3.
    6. 将90降幂得到9,用64减去9,可以减7次,得到1.在结果的个位放置7.
    7. 9已经是9乘以10的零次幂了,最后这个1小于除数,那么我们除法得到的余数是1.
    8. 故:1234除以9等于137,余1.

    那么,我们将其转化为可以被机器执行的描述:

    1. 如果被除数的位数(len1)小于除数的位数(len2),直接返回0. (余数为被除数.)
    2. 否则的话,获取除数位数,让其乘以10的(被除数位数-除数位数)次方,得到一个数b.
    3. 定义一个长度最长为被除数位数数组cnt[len1].
    4. 将被除数减去b. 每减去一次b,cnt[位数]++.
    5. 当被除数即将在减去后小于0时,不执行该步减法,让b缩小为原来的十分之一.
    6. 继续减,直到b和原来的除数相等.

    该算法的实现依赖于高精度乘法和高精度减法,只有这两种计算方法已经封装了才可以实现除法. 另外,同样需要一个比较函数.
    利用这个算法,我们就可以求出两个数的商和余数了.

    感受:ACM的日子,每周还是要学点东西的~

    展开全文
  • 用于Visual studio 高精度计算库项目文件; 包括了gmp, mpir, mpfr, gmp, 等,可以直接在visual studio中编译成为静态或动态链接库,用于作超高精度数值计算时调用; 跟Eigen C++ tempalte library库和Pavel写的mpfr C++...
  • C++为什么需要高精度计算

    千次阅读 2020-02-20 17:58:20
    为什么 C++ 需要高精度计算?这个问题对于 C++ 来说,是一个比较尴尬的问题。因为 Java 和 Python 是不需要高精度计算的,因为这两个语言直接支持高精度数据。 从 C++ 的角度回答这个问题,我们首先要从 C++ 的基础...

    为什么 C++ 需要高精度计算?这个问题对于 C++ 来说,是一个比较尴尬的问题。因为 Java 和 Python 是不需要高精度计算的,因为这两个语言直接支持高精度数据。

    从 C++ 的角度回答这个问题,我们首先要从 C++ 的基础知识来看,也就是 C++ 的数据类型可以表示的范围。下表是 C++ 常用的数据类型的字节大小和数值范围。我们针对 G++ 来说明这个问题,因为在不同类型的编译器里,相同数据类型的大小是不一样的。

    C++ 数据类型含义长度(Byte) 可以表示数值范围
    bool布尔类型1B true 或者 false
    short有符号短整型2B-2^15 ~ 2^15-1-32,768 ~ 32,767
    unsigned short无符号短整型2B0 ~ 2^16-10 ~ 65,535
    int有符号整型4B~2^31 ~ 2^31-1-2,147,483,648 ~ 2,147,483,647
    unsigned int无符号整型4B0 ~ 2^32-10 ~ 4,294,967,295
    long long有符号长整型8B-2^63 ~ 2^63-1–9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
    unsigned long long无符号长整型8B0 ~ 2^64-10 ~ 18,446,744,073,709,551,615
    char有符号字符型1B-2^7 ~ 2^7-1-128 ~ 127
    unsigned char无符号字符型1B0 ~ 2^8-10 ~ 255
    float单精度浮点数4B 

    -3.4E-38 ~ 3.4E+38

    6 ~ 7位有效数据

    double双精度浮点数8B 

    -1.7E-308 ~ 1.7E+308

    15 ~ 16位有效数据

    long double长精度浮点数16B 

    -1.2E-4932 ~ 1.2E4932

    18 ~ 19位有效数据

    从上表,我们可以清楚的看到,当进行整数计算的时候, 数据超过 18,446,744,073,709,551,615,也就是超过 8Byte 后,C++就没有对应的数据类型就行表达。这就是为什么 C++ 需要高精度计算。

    展开全文
  • 高精度算法完整代码

    2018-06-07 16:01:48
    由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1),unsigned long(无符号整数)是(0~2^32-1),都约为几十亿.如果采用实数型,则能保存最大的double只能提供...
  • C++高精度基本运算(全面实现)

    千次阅读 多人点赞 2020-03-28 10:08:18
    C++高精度 写在开头: 本文主要实现的是自然数范围内做运算的 加法、减法、乘法、除法 四种基本高精度运算以及依靠减法和乘法实现的大数 阶乘 和利用字符串比较实现的 比较 运算(如果有需要可以自行加判断将范围扩充...

    C++高精度

    写在开头:
    本文主要实现的是自然数范围内做运算的 加法、减法、乘法、除法 四种基本高精度运算以及依靠减法和乘法实现的大数 阶乘 和利用字符串比较实现的 比较 运算(如果有需要可以自行加判断将范围扩充到整数范围内)

    实现思路

    我们用字符串去储存大数,让各个函数可以处理这些字符串进行模拟运算并返回一个用字符串表示的大数

    C++高精度 之 加法运算:

    大数加法运算的模拟相对简单,我们直接模拟竖式加法即可。我们把对应位相加并将结果存入一个定义好长度的数组(放在对应位处),我们可以先不必考虑每一位的进位情况,直接存数即可。当我们算完得到结果数组后,我们从最后一位(个位)开始检查进位情况,如果有进位我们调整该位及其高一位的数。当我们遍历完整个数组后再将数组转化成字符串返回即可。

    C++高精度 之 减法运算:

    大数减法整体思想依旧是加法的模拟竖式,不同点是我们需要判断一下被减数与减数的大小,我们保证被减数大于减数如果不满足我们交换两个字符串数并在答案字符串中存入一个负号("-")。然后我们模拟竖式加法,把对应位相减的结果存入一个定义好长度的数组的对应位处(不考虑每一位的借位情况),然后从个位开始检查借位,如果有借位我们调整该位及其高一位的数,最后转化数组为字符串并返回。

    C++高精度 之 乘法运算:

    乘法运算相对需要一些技巧,但仍旧是模拟竖式乘法,仍旧是不考虑进位,依次将每位相乘结果存入数组对应位处(这里需要累加存入,做竖式乘法我们知道每一位最后算结果时,不一定是两位相加有可能是多位),然后依旧是从个位开始检查进位,最后转化数组并返回结果。

    动画演示大数乘法运算的模拟过程:

    C++高精度乘法模拟动画

    乘法动画视频链接

    C++高精度 之 除法运算:

    因为是自然数范围内的除法我们模拟不出精确的小数结果,所以我们的函数最后需要返回两个值一个是商一个是余数。除法的模拟运算我们用到了大数减法,思想依旧是模拟竖式的除法:

    1. 我们从最高位依次取数直到大于等于除数为止
    2. 然后我们用目前取到的数减去若干个除数(直到减到小于除数为止)
    3. 然后我们记录减去了几个除数,最后将此数存入答案字符串
    4. 我们将记录清零然后再从被除数中再取一个数,判断是否小于除数
    5. 如果小于则直接将0加到答案字符串末尾
    6. 否则我们转入步骤 2 然后将最后记录加到答案字符串末尾
    7. 直到我们将被除数中的数取完为止

    动画演示大数除法运算的模拟过程:

    C++高精度除法模拟动画

    除法动画视频链接

    C++代码实现:

    #include<iostream>
    #include<vector>
    using namespace std;
    //......................................................................................
    int myCompare(string a,string b)//大数比较设定a>b返回1 a<b返回-1 a=b返回0 
    {
    	if(a.size()!=b.size())//如果字符串长度不同那么长度大的那个就是更大的大数 
    	{
    		if(a.size()>b.size())
    			return 1;
    		else 
    			return -1;
    	}
    	else //如果字符串长度相同我们通过直接比较字符串的字典序来判断大小 
    	{
    		if(a>b)
    			return 1;
    		else if(a==b)
    			return 0;
    		else 
    			return -1;
    	}
    }
    //......................................................................................
    string myAdd(string a,string b)			//高精度加法 
    {
    	int n=max(a.size(),b.size())+1;    
    	vector<int>ans(n,0);//开辟一个足够存储结果的数组,结果的位数最多为 位数最多的那个数的位数加一(考虑进位)
    	int i=a.size()-1,j=b.size()-1,k=n-1;//从个位开始通过模拟竖式进行大数加法 
    	while(i>=0&&j>=0)//当两数均未加完时 
    	{
    		ans[k--]=(a[i--]-'0')+(b[j--]-'0');//我们让我们的数组存储每一位相加的结果注意将字符串转为整型数字 
    	}
    	//检测是否有某个数的高位未加完将其直接存入数组中 
    	while(j>=0)
    	{
    		ans[k--]=(b[j--]-'0');
    	}
    	while(i>=0)
    	{
    		ans[k--]=(a[i--]-'0');
    	}
    	string c="";//创建一个字符串去存储答案 
    	for(int i=n-1;i>0;i--)//因为之前的竖式加每一位都没考虑进位所以我们从最后开始检查进位 
    	{//因为是加法如果有进位最多也就进一 
    		if(ans[i]>=10)//如果大于10说明应该进位那么我们让此位减10它的高一位加1 
    		{
    			ans[i]-=10;
    			ans[i-1]++;
    		}
    		c.insert(0,1,ans[i]+'0');//处理后的结果转化为字符插入结果字符的首位
    	} 
    	
    	if(ans[0]>0)//检查最最高位是否大于0如果两数相加没有进位那么这一位就是0我们就不必存储它否则则放入字符串 
    	{
    		c.insert(0,1,ans[0]+'0');
    	}
    	return c;//返回答案 
    }
    //......................................................................................
    string mySubtract(string a,string b)//高精度减法(整体思想同加法) 
    {
    	string c="";               //创建一个字符串去存储答案 
    	if(myCompare(a,b)==0)      //先比较一下两数大小如果相等我们直接返回0即可 
    		return "0";
    	if(myCompare(a,b)==-1)//如果a<b那么我们交换两数的值同时在答案字符串中先放入一个负号 
    	{
    		swap(a,b);
    		c.push_back('-');
    	}
    	int n=a.size();
    //开辟一个足够存储结果的数组  减法结果的位数最多为位数最多的那个数的位数我们保证了a为的大数所以就是a的位数 
    	vector<int>ans(n,0);
    	int i=a.size()-1,j=b.size()-1,k=n-1;//从个位开始模拟竖式减法 
    	int t=0;//表示低位的借位情况  0:无借位   1:有借位 
    	while(i>=0)                         //同加法一样模拟运算我们知道a是大数所以a遍历完竖式才完成 
    	{
    	    char nowb;//被减数当前位有数就正常减 没有数说明就是0
    	    if(j>=0) nowb=b[j];
    	    else nowb='0';
    		ans[k]=a[i]-nowb-t;//对应位相减同时减去低位的借位
    		if(ans[k]<0)//如果结果小于0 则向高位借一位
    		{
    			t=1;
    			ans[k]+=10;
    		} 
    		else t=0;  //否则向高位无借位
    		k--,i--,j--;  //继续判断高一位
    	}
    	bool flag=true;//这里与加法不同高位可能出现多个零开头的情况我们需要找到第一不是零的地方再存数 
    	for(int i=0;i<n;i++)
    	{
    		if(flag&&ans[i]==0)//如果当前数为0且未存数则不执行存数操作 
    			continue;
    		flag=false;        //一旦存入数更改标志位 
    		c.push_back(ans[i]+'0');	
    	}	 
    	return c;              //返回结果 
    }
    //......................................................................................
    string myMultiply(string a,string b)//高精度乘法 
    {
    	if(a=="0"||b=="0")   //其中有一个为0时直接返回0 
    		return "0";
    	vector<int>ans;      //开辟一个足够存储结果的数组
    	int n=a.size(),m=b.size();
    	ans.resize(n+m,0);   //乘法结果的位数最多为两数的位数之和
    	for(int i=0;i<n;i++) //这里从高位开始和从低位开始无所谓我们将两数相乘的结果不考虑放到对应位上最后去检测进位即可 
    	{                    //例如个位乘百位的结果 以及十位乘十位的结果 都放到百位上 
    		for(int j=0;j<m;j++)
    		{
    			ans[i+j+1]+=(a[i]-'0')*(b[j]-'0');
    		}
    	}
    	for(int i=n+m-1;i>0;i--)      //我们从低位开始检查进位 
    	{
    		if(ans[i]>=10)            //如果大于10说明有进位但乘法的进位不一定只进1 
    		{
    			ans[i-1]+=(ans[i]/10);//高位加地位的高于个位部分 
    			ans[i]%=10;           //低位对十求余 
    		}
    	} 
    	string c ="";   //创建字符串存储答案 
    	bool flag=true; //同减法一样找到第一个不是0的位置开始存数 
    	for(int t=0;t<n+m;t++)
    	{
    		if(flag&&ans[t]==0)
    			continue;
    		flag=false;
    		c.push_back(ans[t]+'0');	
    	}	 
    	return c;      //返回答案 
    }
    //......................................................................................
    vector<string>myDivide(string a,string b)//高精度除法
    {
    	vector<string>ans(2,"0");//先创建两个字符串空间去存储答案一个存商一个存余数 
    	if(myCompare(a,b)==-1)   //如果被除数比除数小商为0余数为a返回答案即可 
    	{
    		ans[1]=a;
    		return ans;
    	}
    	else if(myCompare(a,b)==0)//如果被除数与除数相等商为1余数为0返回答案即可
    	{
    		ans[0]="1";
    		return ans;
    	}
    	else              //否则我们需要模拟除法的竖式来进行计算 
    	{
    		string res="";//创建存储商的字符串 
    		int m1=a.size(),m2=b.size();
    		string a1=a.substr(0,m2-1);
    		for(int i=m2-1;i<m1;i++)     //模拟竖式从高位开始依次取数减去除数能减几个该位商的当前位就是几 
    		{	
    			if(a1=="0")			     //如果a1为0为了防止a1出现0开头的情况我们将它清空 
    				a1=""; 
    			a1.push_back(a[i]);      //我们从被除数中取一个数放入a1继续减 
    			int e=0;
    			while(myCompare(a1,b)>=0)//当a1大于等于除数时便一直减同时e累加 
    			{
    				e++;
    				a1=mySubtract(a1,b);
    			}
    			if(res.size()||e)        //如果res不为空或者e不为0我们存储他 
    				res.push_back(e+'0');
    		}
    		ans[0]=res;   //最后res就是商 
    		ans[1]=a1;    //a1就是余数 
    		return ans;   //返回答案 
    	}
    }
    //......................................................................................
    string myFactorial(string a)//高精度阶乘 
    {/*我们还可以利用高精度减法和乘法实现大数的阶乘(最大可运行出10000左右的阶乘)*/
    	if(a=="1")
    		return a;
    	else 
    		return myMultiply(a,myFactorial(mySubtract(a,"1")));
    }
    //......................................................................................
    int main()
    {
    	string a,b;
    	string add_ans,subtract_ans,multiply_ans,factorial_ans;
    	vector<string>divide_ans;
    	int compare_ans;
    	cin>>a>>b;
    	
    	compare_ans=myCompare(a,b);
    	cout<<compare_ans<<endl;
    	
    	add_ans=myAdd(a,b);
    	cout<<add_ans<<endl;
    	
    	subtract_ans=mySubtract(a,b);
    	cout<<subtract_ans<<endl;
    	
    	multiply_ans=myMultiply(a,b);
    	cout<<multiply_ans<<endl;
    	
    	divide_ans=myDivide(a,b);
    	cout<<divide_ans[0]<<endl<<divide_ans[1]<<endl;
    	
    //	factorial_ans=myFactorial(a);
    //	cout<<factorial_ans<<endl;
    	return 0;
    } 
    
    展开全文
  • 高精度计算1

    2018-10-24 12:27:06
    高精度计算,包括高精度加减乘(如何存储大整数?如何实现?如何进位?)
  • (1)返回高精度毫秒计时 long MyGetTickCount() { static BOOL init = FALSE; static BOOL hires = FALSE; static _int64 freq = 1; if(!init) { hires = QueryPerformanceFrequency((LARGE_INTEGER*)&...
  • C++ 高精度加法运算(a=a+b)

    千次阅读 2019-01-16 16:13:53
    一、为什么要高精度计算  利用计算机进行数值计算,有时计算要求精度高,希望计算的数的位数达到上百或者上千,甚至更多。但是由于计算机硬件问题,往往达不到实际问题所要求的精度。   二、思路:  1.考虑...
  • 高精度计算 #include<iostream> using namespace std; int main() { int x ; int a[1000] = { 0 }; int b=0; a[999] = 1; int n; cin>>x>> n; for (int i = 0; i<n;
  • c/c++ 高精度时间测试

    千次阅读 2018-07-30 09:44:37
    高精度时控函数QueryPerformanceFrequency(),QueryPerformanceCounter() 原理:QueryPerformanceCounter()这个函数返回高精确度性能计数器的值,它可以以微妙为单位计时.但是QueryPerformanceCounter()确切的...
  • C++计算高精度圆周率

    2021-02-11 14:48:49
    C/C++
  • 高精度计算

    2017-08-08 19:30:37
    高精度计算PPT
  • c++实现高精度加法

    2020-08-30 09:48:09
    高精度运算是指参与运算的数(加数,减数,因子……)范围大大超出了标准数据类型(整型,实型)能表示的范围的运算。例如,求两个200位的数的和。这时,就要用到高精度算法了。
  • C++ 实现高精度计算

    千次阅读 2014-02-28 17:58:28
    采用C++实现高精度加、减、单乘、双乘、比较大小、读入、输出 代码如下: #include #include #include #include #include #include #include #include #include #include using namespace std; template class hp ...
  • C++高精度运算模板

    万次阅读 多人点赞 2014-04-06 17:16:22
    C++实现大数类
  • C++高精度除以高精度(函数)

    千次阅读 2019-07-28 17:22:44
    //高精度除法运算 void chugao(int a[], int b[], int c[]) {  int tmp[201];  c[0]=a[0]-b[0]+1;  for (int i=c[0]; i>0; i--) {  memset(tmp, 0, sizeof(tmp));//替换  //补0操作  numcpy(b, tmp, i)...
  • C++高精度

    千次阅读 多人点赞 2019-08-13 14:26:40
    C++中当你用int、long long,甚至是unsigned long long 都无法处理的超级巨大数字,你会感到无比痛苦甚至到绝望,那么我们此时就只有一种方法了——高精度算法。
  • C/C++基本类型做算术运算时长度有限,但也...本资源用C++封装了一个高精度整型,完整重载了+-*/%==>>等操作符, 可以直接当整型使用于工程项目,包含了功能测试和性能测试程序,在vs 2019、及ubuntu gcc 均能编译运行。
  • Peking OJ 1001题 附有测试数据
  • C/C++高精度运算(大整数运算)详解(含压位)

    万次阅读 多人点赞 2018-04-22 22:49:50
    1.高精度加法 1.1 高精度加法 高精度运算的基本运算就是加和减。和算数的加减规则一样,模拟竖式计算,考虑错位运算与进位处理。下面是我老师给的代码,目前比网上其他的代码要精简和巧妙。 #include <...
  • C++ 高精度算法及N的阶乘

    千次阅读 2017-03-10 22:27:14
    高精度算法
  • =100),计算2的n次方的值。 输入 输入一个正整数N。 输出 输出2的N次方的值。 样例输入 5 样例输出 32 思路:已知 2^0 ~ 2^64 具体值,遇到大于 64 的 N ,相当于 2^64 * 2^(N - 64) 这里用到了大整数乘法,而大...
  • C++ 高精度运算类(BigC类)

    千次阅读 2013-12-01 14:24:56
    //此文件中提供了高精度运算类的声明 /********************************************************************************************************************************************************************...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,840
精华内容 16,336
关键字:

c++高精度计算

c++ 订阅