C++ 大整数类 高精度运算库

/*----------简介----------*/ 本运算库提供定长有符号大整数类的声明和基本操作的封装，实现过程仅使用基于C++98标准的基本语法，不依赖于任何标准库或者第三方库，以求最大限度保证代码的移植性(比如GCC和Visual Studio)和安全性(比如STL线程安全)。 本运算库采用模拟竖式算法，加法和减法的时间复杂度为O(N)，乘法和除法的时间复杂度为O(N^2)。 本运算库虽然不依赖于具体环境，但最佳运行系统为32位。本运算库无法充分发挥64位系统性能，16位系统因需要额外模拟长整型运算从而导致性能不及预期。 本运算库共包含2个文件： Arithmetic.h 包含Integer类的声明 Arithmetic.cpp 包含Integer类的实现 使用本运算库时，请将上述两个文件关联到相关项目，并且将下面的代码添加到需要使用本运算库的文件中： #include "Arithmetic.h" /*----------数据结构----------*/ 使用short int数组进行存储，数组的低位存储数据的低位，数据采用万进制。数组的最高位存储数据的符号，1表示正，-1表示负，0表示0。例如，数字142857的存储格式为： Element[0]=2857，Element[1]=14，Element[Length-1]=1 数组的大小可以通过下面的参数进行更改： static const int Length=64; 数组默认建在栈区，可以通过删除或注释掉下面的语句将数组改建在堆上： #define ARITHMETIC_OPTIMIZATION_STACK 数据存储在堆上可以避免栈溢出，相应的会牺牲性能。 /*----------成员函数----------*/ Integer类成员函数可分为6类： 1) 构造函数 Integer(const bool& =false); Integer(const Integer&); 2) 赋值函数 Integer& operator=(const Integer&); 3) C风格字符串转换函数 bool Char(const char*); char* Char()const; 4) 基本运算函数 Integer operator+(const Integer&)const; Integer operator-()const; Integer operator-(const Integer&)const; Integer operator*(const Integer&)const; Integer operator/(const Integer&)const; Integer operator%(const Integer&)const; 5) 比较函数 bool operator==(const Integer&)const; bool operator>(const Integer&)const; bool operator<(const Integer&)const; 6) 析构函数 virtual ~Integer(); 减法由加法和负号实现，其它成员函数之间相互独立(使用赋值函数除外)。 /*----------使用说明----------*/ 1) 默认的构造函数只能初始化0和1： Integer Zero1,Zero2(false),Zero3=0; //正确，三个数都将初始化为0 const Integer One1(true),One2=1; //正确，两个数都将初始化为1 const Integer Two=One1+One2; //正确，Two将初始化为2 Integer Int=3; //逻辑错误，Int将初始化为1 2) 与C风格字符串相互转换时，采用十进制，除0以外的整数带符号，不能有多余字符： /*int i=3; *char transition[10]; *sprintf(transition,"+%d",i); //transition[0]='+',transition[1]='3',transition[2]='\0' */ Int.Char(transition); //正确，Int赋值为3，并返回true Int.Char("5"); //错误，Int仍为3，并返回false cout<<Int.Char(); //等效于cout<<"+3"; Int.Char("-7"); //正确，Int赋值为-7，并返回true i=aoti(Int.Char()); //i赋值为-7 Int.Char("0"); //正确，Int赋值为0，并返回true strcpy(transition+5,Int.Char()); //transition[5]='0',transition[6]='\0' Int.Char("+0123"); //错误，Int仍为0，并返回false 3) 当运算溢出或除0时，算术运算将直接传递异常结果，比较运算则直接返回false： /* *假设Overflow上溢，Div0除0 */ Integer Error=Div0; //可以，异常结果可以初始化 Int=Two+Error; //Int为除0，异常结果直接传递 Int=Overflow*Int; //Int为上溢，异常结果传递左边优先 if(Int>Two){...} //结果为false，异常结果无法比较 注意，下面两种表达方式，在正常情况下效果相同，但在异常情况下结果相反： if(!(Int>Two)){...} //在异常情况下结果为true if(Int<Two||Int==Two){...} //在异常情况下结果为false 4) 溢出或除0结果转换为C风格字符串时，在溢出方向或0后面加'!': cout<<Error.Char(); //等效于cout<<"0!"; cout<<Int.Char(); //等效于cout<<"+!"; /*----------性能----------*/ 在Lenovo G475GX笔记本电脑上，基于本运算库编写的Baillie-PSW素性测试程序，使用Dev-C++ 4.9.8.0编译O3优化，对10^999+7完成素性检验耗时16.5s。