目录
项目名称:C++大整数类
开发环境:devc++
优化级别:自动
C++标准:ISOC++11
在我们实际的编程当中,C++自带的整数类型只占用固定的内存,所以变量的最大值和最小值也就是固定的,非常的不妙。即使是最大的unsigned long long,也只能存储2^64-1的数,对于某些算法(例如RSA非对称加密算法),它们需要极大的数据存储量。因此,我就制作了一个大整数类。
测试代码
#include "NUM_TYPE_def.cpp"
#include <time.h>
#include <iostream>
void addTest(){
std::string s = "",s2 = "" ;
std::cin >> s >> s2 ;
NUM_TYPE a(s),b(s2) ;
clock_t start = clock() ;
a += b ;
printf("%llums : ",(clock() - start)) ;
a.output() ;
printf("\n") ;
}
void subTest(){
std::string s = "",s2 = "" ;
std::cin >> s >> s2 ;
NUM_TYPE a(s),b(s2) ;
clock_t start = clock() ;
a -= b ;
printf("%llums : ",(clock() - start)) ;
a.output() ;
printf("\n") ;
}
void mulTest(){
std::string s = "",s2 = "" ;
std::cin >> s >> s2 ;
NUM_TYPE a(s),b(s2) ;
clock_t start = clock() ;
a *= b ;
printf("%llums : ",(clock() - start)) ;
a.output() ;
printf("\n") ;
}
void divTest(){
std::string s = "",s2 = "" ;
std::cin >> s >> s2 ;
NUM_TYPE a(s),b(s2) ;
clock_t start = clock() ;
a /= b ;
printf("%llums : ",(clock() - start)) ;
a.output() ;
printf("\n") ;
}
void powTest(){
std::string s = "",s2 = "" ;
std::cin >> s >> s2 ;
NUM_TYPE a(s),b(s2) ;
clock_t start = clock() ;
a = pow(a,b) ;
printf("%llums : ",(clock() - start)) ;
a.output() ;
printf("\n") ;
}
void sqrtTest(){
std::string s = "" ;
std::cin >> s ;
NUM_TYPE a(s) ;
clock_t start = clock() ;
a = sqrt(a) ;
printf("%llums : ",(clock() - start)) ;
a.output() ;
printf("\n") ;
}
void gcdTest(){
std::string s = "",s2 = "" ;
std::cin >> s >> s2 ;
NUM_TYPE a(s),b(s2) ;
clock_t start = clock() ;
a = gcd(a,b) ;
printf("%llums : ",(clock() - start)) ;
a.output() ;
printf("\n") ;
}
void lcmTest(){
std::string s = "",s2 = "" ;
std::cin >> s >> s2 ;
NUM_TYPE a(s),b(s2) ;
clock_t start = clock() ;
a = lcm(a,b) ;
printf("%llums : ",(clock() - start)) ;
a.output() ;
printf("\n") ;
}
void primeTest(){
std::string s = "" ;
std::cin >> s ;
clock_t start = clock() ;
NUM_TYPE a(s) ;
bool t = is_prime(a) ;
printf("%llums : ",(clock() - start)) ;
if(t)printf("是质数\n") ;
else printf("是合数\n") ;
}
int main(){
int choose = 0 ;
while(1){
printf("1.加法测试\n2.减法测试\n3.乘法测试\n4.除法测试\n5.乘方测试\n6.开方测试\n7.GCD测试\n8.LCM测试\n9.质数测试\n请选择:") ;
scanf("%d",&choose) ;
switch(choose){
case 1 : addTest() ; break ;
case 2 : subTest() ; break ;
case 3 : mulTest() ; break ;
case 4 : divTest() ; break ;
case 5 : powTest() ; break ;
case 6 : sqrtTest() ; break ;
case 7 : gcdTest() ; break ;
case 8 : lcmTest() ; break ;
case 9 : primeTest() ; break ;
default : printf("input error!\n") ; break ;
}
}
return 0 ;
}
加法
减法
乘法
除法
乘方
开方
最大公因数
最小公倍数
质数判断
做过大数类的应该知道,一个大数类,它的进制是十分重要的:进制大了的话,加法、减法、乘法运算速度变快,但是除法运算速度极低;进制小的话,除法运算速度极快,但是加法、减法、乘法运算速度极慢。所以,我能想到的比较好的方案,就是仍然是用大进制数,但是在除法时特殊处理,最后就可以达到一个较快的速度。
1、五则运算:加减乘除取余
2、乘方
3、开方
4、最大公因数和最小公倍数
5、大小判断
6、大数类之间的相互赋值,交换
7、与long long的互相转换
8、自增自减
9、部分位运算:^,&,~,-,|
10、绝对值
NUM_TYPE_def.cpp
#include <stdio.h>
#include "useful_type.cpp"
#include "pow.cpp"
#include "move.cpp"
#include "lenght.cpp"
#include <string>
#define MAX_ONE (9)
#define MAX (1000000000LL)
#define NEAR_MAX (999999999LL)
#define ULL_MAX (0xffffffffffffffffULL)
#define NULLBACK(T) (*((T*)(0x0)))
class NUM_TYPE ;
NUM_TYPE sqrt(NUM_TYPE x) ;
NUM_TYPE gcd(NUM_TYPE a,NUM_TYPE b) ;
NUM_TYPE lcm(NUM_TYPE a,NUM_TYPE b) ;
class NUM_TYPE{
public :
bool m_op ;
public :
friend NUM_TYPE abs(NUM_TYPE a) ;
friend NUM_TYPE pow(NUM_TYPE a,NUM_TYPE b) ;
NUM_TYPE() : m_op(true) , data(0) , size(0) , nagative(false) {}
NUM_TYPE(const char* s) : m_op(true) , data(0) , size(0) {
*this = s ;
}
NUM_TYPE(std::string s) : m_op(true) , data(0) , size(0) {
*this = s.c_str() ;
}
NUM_TYPE(ll n) : m_op(true) , data(0) , size(0) {
*this = n ;
}
NUM_TYPE(const NUM_TYPE& b) : m_op(b.m_op) , data(0) , size(0) , nagative(b.nagative) {
reserve(b.size) ;
for(ull i = 0;i < size;++ i)
data[i] = b.data[i] ;
}
NUM_TYPE(NUM_TYPE&& b) : m_op(b.m_op) , data(b.data) , size(b.size) , nagative(b.nagative) {
b.data = 0 ;
b.size = 0 ;
b.nagative = 0 ;
}
~NUM_TYPE(){
if(data)delete[] data ;
data = 0 ;
size = 0 ;
nagative = 0 ;
}
void output(){
ull nothing = size - 1 ;
while(nothing != ULL_MAX && data[nothing] == 0)-- nothing ;
if(nothing == ULL_MAX)putchar('0') ;
else{
if(nagative)putchar('-') ;
printf("%u",data[nothing]) ;
while((-- nothing) != ULL_MAX)printf("%09u",data[nothing]) ;
}
}
bool operator>(NUM_TYPE b){
return compare(b) == -1 ;
}
bool operator<(NUM_TYPE b){
return compare(b) == 1 ;
}
bool operator==(NUM_TYPE b){
return compare(b) == 0 ;
}
bool operator>=(NUM_TYPE b){
return compare(b) != 1 ;
}
bool operator<=(NUM_TYPE b){
return compare(b) != -1 ;
}
bool operator!=(NUM_TYPE b){
return compare(b) != 0 ;
}
bool operator>(ll b){
return compare(b) == -1 ;
}
bool operator<(ll b){
return compare(b) == 1 ;
}
bool operator==(ll b){
return compare(b) == 0 ;
}
bool operator>=(ll b){
return compare(b) != 1 ;
}
bool operator<=(ll b){
return compare(b) != -1 ;
}
bool operator!=(ll b){
return compare(b) != 0 ;
}
NUM_TYPE& operator=(NUM_TYPE b){
swap(b) ;
return *this ;
}
NUM_TYPE& operator=(ll n){
nagative = (n < 0) ;
if(nagative)n = -n ;
if(n < MAX){
reserve(1) ;
data[0] = n ;
}else{
reserve(2) ;
data[0] = n % MAX ;
data[1] = n / MAX ;
}
return *this ;
}
NUM_TYPE& operator=(const char* s){
while(*s == '0')++ s ;
nagative = (s[0] == '-') ;
if(nagative)++ s ;
uint all = 0 ;
ull len = lenght(s),tlen = (len % MAX_ONE),bit = ULL_MAX ;
reserve(len / MAX_ONE + 2) ;
if(len){
for(ull i = len;i > tlen && i > 9;i -= MAX_ONE){
for(ull o = (i - MAX_ONE);o < i;++ o)
all = (all * 10) + (s[o] - '0') ;
data[++ bit] = all ;
all = 0 ;
}
if(tlen == 0)tlen = MAX_ONE ;
for(ull i = 0;i < tlen;++ i)
all = (all * 10) + (s[i] - '0') ;
data[++ bit] = all ;
}
return *this ;
}
NUM_TYPE& operator+=(NUM_TYPE b){
if(nagative != b.nagative){
b.nagative = (b.nagative) ? (false) : (true) ;
*this -= b ;
return *this ;
}
reserve((b.size > size) ? (b.size + 1) : (size + 1)) ;
ull temp = 0 ;
for(ull i = 0;i < size;++ i){
temp += data[i] ;
if(i < b.size)temp += b.data[i] ;
data[i] = temp % MAX ;
temp /= MAX ;
}
LessMemory() ;
return *this ;
}
NUM_TYPE operator+(NUM_TYPE b){
NUM_TYPE t(*this) ;
t += b ;
return move(t) ;
}
NUM_TYPE& operator+=(ll b){
return (*this += NUM_TYPE(b)) ;
}
NUM_TYPE operator+(ll b){
NUM_TYPE t(*this) ;
t += ull(b) ;
return move(t) ;
}
NUM_TYPE& operator-=(NUM_TYPE b){
bool tnagative = nagative ;
if(nagative != b.nagative){
b.nagative = (b.nagative) ? (false) : (true) ;
*this += b ;
return *this ;
}
b.nagative = nagative = false ;
if(*this < b)swap(b) , tnagative = (tnagative) ? (false) : (true) ;
const ull end = (b.size < size) ? (b.size) : (size) ;
for(ull i = 0;i < end;++ i){
if(get_data(i) < b.get_data(i)){
ull o = i ;
while(data[++ o] == 0) data[o] = NEAR_MAX ;
-- data[o] ;
data[i] = (MAX - b.data[i] + data[i]) ;
}else data[i] -= b.data[i] ;
}
nagative = tnagative ;
LessMemory() ;
return *this ;
}
NUM_TYPE operator-(NUM_TYPE b){
NUM_TYPE t(*this) ;
t -= NUM_TYPE(b) ;
return move(t) ;
}
NUM_TYPE& operator-=(ll b){
return (*this -= NUM_TYPE(b)) ;
}
NUM_TYPE operator*(NUM_TYPE b){
ull temp = 0,now = 0 ;
NUM_TYPE t ;
t.reserve(size + b.size + 1) ;
for(ull i = 0;i < size;i ++){
for(ull o = 0;o < b.size;o ++){
temp = ull(get_data(i)) * ull(b.get_data(o)) ;
now = i + o ;
while((temp += t.data[now]) > NEAR_MAX){
t.data[now] = temp % MAX ;
temp /= MAX ;
++ now ;
}
t.data[now] = temp ;
}
}
t.nagative = (nagative == b.nagative) ? (false) : (true) ;
t.LessMemory() ;
return move(t) ;
}
NUM_TYPE& operator*=(NUM_TYPE b){
*this = *this * b ;
return *this ;
}
NUM_TYPE operator*(ll b){
return move(*this * NUM_TYPE(b)) ;
}
NUM_TYPE& operator*=(ll b){
*this = *this * NUM_TYPE(b) ;
return *this ;
}
NUM_TYPE operator/(NUM_TYPE b){
if(b.zero())return move(b) ;
NUM_TYPE t,ans ;
ans.reserve(size - b.size + 1) ;
t.reserve(size) ;
t.m_op = false ;
ans.nagative = (b.nagative == nagative) ? (false) : (true) ;
b.nagative = false ;
NUM_TYPE tb[MAX_ONE] ;
for(ull i = 0;i < MAX_ONE;++ i)
tb[i] = b * pow(i) ;
for(ull i = (size - 1);i != ULL_MAX;-- i){
for(ull o = (size - i - 1);o > 0;-- o)
t.data[o] = t.data[o - 1] ;
t.data[0] = data[i] ;
for(ull o = MAX_ONE - 1;o != ULL_MAX;-- o)
while(t >= tb[o])t -= tb[o] , ans.data[i] += pow(o) ;
}
ans.LessMemory() ;
return move(ans) ;
}
NUM_TYPE& operator/=(NUM_TYPE b){
if(b.zero())return *this ;
*this = *this / b ;
return *this ;
}
NUM_TYPE operator/(ll b){
return (*this / NUM_TYPE(b)) ;
}
NUM_TYPE& operator/=(ll b){
return (*this /= NUM_TYPE(b)) ;
}
NUM_TYPE operator%(NUM_TYPE b){
if(b.zero())return move(b) ;
NUM_TYPE t,ans ;
ans.reserve(size - b.size + 1) ;
t.reserve(size) ;
t.m_op = false ;
ans.nagative = (b.nagative == nagative) ? (false) : (true) ;
b.nagative = false ;
NUM_TYPE tb[MAX_ONE] ;
for(ull i = 0;i < MAX_ONE;++ i)
tb[i] = b * pow(i) ;
for(ull i = (size - 1);i != ULL_MAX;-- i){
for(ull o = (size - i - 1);o > 0;-- o)
t.data[o] = t.data[o - 1] ;
t.data[0] = data[i] ;
for(ull o = MAX_ONE - 1;o != ULL_MAX;-- o)
while(t >= tb[o])t -= tb[o] , ans.data[i] += pow(o) ;
}
t.LessMemory() ;
return move(t) ;
}
NUM_TYPE& operator%=(NUM_TYPE b){
if(b.zero())return *this ;
*this = *this % b ;
return *this ;
}
NUM_TYPE& operator++(){
if(nagative == true){
nagative = false ;
-- *this ;
nagative = true ;
return *this ;
}
if(full())reserve(size + 1) ;
ull i = size - 1 ;
while(i != ULL_MAX && data[i] == NEAR_MAX)data[i] = 0 ;
++ data[i] ;
return *this ;
}
NUM_TYPE& operator--(){
if(nagative == true || zero()){
nagative = false ;
++ *this ;
nagative = true ;
return *this ;
}
ull i = size - 1 ;
while(i != ULL_MAX && data[i] == 0)data[i] = NEAR_MAX ;
-- data[i] ;
return *this ;
}
NUM_TYPE operator++(int){
NUM_TYPE t(*this) ;
++ *this ;
return move(t) ;
}
NUM_TYPE operator--(int){
NUM_TYPE t(*this) ;
-- *this ;
return move(t) ;
}
NUM_TYPE& operator|=(ull b){
*this = *this | b ;
return *this ;
}
ull operator|(ull b){
return ((get_data(1) * MAX + get_data(0)) | b) ;
}
NUM_TYPE& operator|=(NUM_TYPE b){
for(ull i = 0;i < size;++ i)
data[i] |= b.get_data(i) ;
return *this ;
}
NUM_TYPE operator|(NUM_TYPE b){
NUM_TYPE t(*this) ;
t |= b ;
return move(t) ;
}
NUM_TYPE& operator&=(NUM_TYPE b){
for(ull i = 0;i < size;++ i)
data[i] &= b.get_data(i) ;
return *this ;
}
NUM_TYPE operator&(NUM_TYPE b){
NUM_TYPE t(*this) ;
t &= b ;
return move(t) ;
}
NUM_TYPE& operator&=(ull b){
*this = *this & b ;
return *this ;
}
ull operator&(ull b){
return ((get_data(1) * MAX + get_data(0)) & b) ;
}
NUM_TYPE& operator^=(NUM_TYPE b){
for(ull i = 0;i < size;++ i)
data[i] ^= b.get_data(i) ;
return *this ;
}
NUM_TYPE operator^(NUM_TYPE b){
NUM_TYPE t(*this) ;
t ^= b ;
return move(t) ;
}
NUM_TYPE& operator^=(ull b){
*this = *this ^ b ;
return *this ;
}
ull operator^(ull b){
return ((get_data(1) * MAX + get_data(0)) ^ b) ;
}
NUM_TYPE operator~(){
NUM_TYPE t(*this) ;
for(ull i = 0;i < size;++ i)
t.data[i] = ~t.data[i] ;
return move(t) ;
}
NUM_TYPE operator-(){
NUM_TYPE t(*this) ;
t.nagative = (t.nagative) ? (false) : (true) ;
return t ;
}
inline void swap(NUM_TYPE& b){
uint* t = data ; data = b.data ; b.data = t ;
ull t2 = size ; size = b.size ; b.size = t2 ;
bool t3 = nagative ; nagative = b.nagative ; b.nagative = t3 ;
}
inline void swap(ll& b){
if(size < 2){
uint* new_data = new uint[2] ;
new_data[0] = new_data[1] = 0 ;
if(size){
new_data[0] = data[0] ;
delete data ;
}
data = new_data ;
size = 2 ;
}
bool t = nagative ;
nagative = (b < 0) ;
ull t2 = (get_data(0) + get_data(1) * MAX) ;
data[0] = b % MAX ;
data[1] = b / MAX ;
b = (t) ? (-t2) : (t2) ;
}
bool zero(){
for(ull i = 0;i < size;++ i)
if(data[i])return false ;
return true ;
}
bool full(){
for(ull i = 0;i < size;++ i)
if(data[i] != NEAR_MAX)return false ;
return true ;
}
inline void abs(){
nagative = false ;
}
ll to_ll(){
return (get_data(1) * MAX + get_data(0)) * ((nagative) ? (-1) : (1)) ;
}
private :
void reserve(ull new_size){
if(size == new_size)return ;
if(new_size == 0){
if(data)delete[] data ;
size = 0 ;
data = 0 ;
nagative = 0 ;
return ;
}
uint* new_data = new uint[new_size] ;
if(new_size < size){
for(ull i = 0;i < new_size;++ i)
new_data[i] = data[i] ;
}else{
for(ull i = 0;i < size;++ i)
new_data[i] = data[i] ;
for(ull i = size;i < new_size;++ i)
new_data[i] = 0 ;
}
if(data)delete[] data ;
data = new_data ;
size = new_size ;
}
inline uint get_data(ull t){
if(t < size)return data[t] ;
return 0 ;
}
char compare(NUM_TYPE b){
if(b.nagative != nagative){
bool za = zero() , zb = b.zero() ;
if(za && zb)return 0 ;
if(za)return ((nagative) ? (-1) : (1)) ;
return ((b.nagative) ? (-1) : (1)) ;
}
for(ull i = ((size > b.size) ? (size) : (b.size)) - 1;i != -1;-- i)
if(get_data(i) != b.get_data(i)){
if(nagative)return (get_data(i) < b.get_data(i)) ? (-1) : (1) ;
return (get_data(i) > b.get_data(i)) ? (-1) : (1) ;
}
return 0 ;
}
char compare(ll b){
bool bnagative = (b < 0),za = zero(),zb = (b == 0) ;
if(bnagative != nagative){
if(za && zb)return 0 ;
if(za)return ((nagative) ? (-1) : (1)) ;
return ((bnagative) ? (-1) : (1)) ;
}
for(ull i = 2;i < size;++ i)
if(data[i])return ((nagative) ? (1) : (-1)) ;
ull t = (get_data(0) + get_data(1) * MAX) ;
if(t == b)return 0 ;
return (t > b) ? (-1) : (1) ;
}
void LessMemory(){
if(!m_op)return ;
ull i = size - 1 ;
while((i != ULL_MAX) && (data[i] == 0))-- i ;
reserve((i == ULL_MAX) ? (1ULL) : (i + 1ULL)) ;
}
private :
bool nagative ;
uint* data ;
ull size ;
} ;
NUM_TYPE sqrt(NUM_TYPE x){
NUM_TYPE l(0LL),r(x) ;
while (l < r){
NUM_TYPE mid = (l + r) / 2 ;
NUM_TYPE res = mid * mid ;
if(res < x) l = mid + 1 ;
else if(res > x) r = mid - 1 ;
else return mid ;
}
return ((l * l) > x) ? (l - 1) : (l) ;
}
NUM_TYPE gcd(NUM_TYPE a,NUM_TYPE b){
while(a != b)
if(a > b)a -= b ;
else b -= a ;
return move(a) ;
}
NUM_TYPE lcm(NUM_TYPE a,NUM_TYPE b){
return (a * b / gcd(a,b)) ;
}
bool is_prime(NUM_TYPE a){
if(a < 2)return false ;
if(a == 2 || a == 3)return true ;
NUM_TYPE i(sqrt(a) + 1) ;
while(i > 1){
if((a % i) == 0)return false ;
-- i ;
}
return true ;
}
inline NUM_TYPE abs(NUM_TYPE a){
a.nagative = false ;
return move(a) ;
}
NUM_TYPE pow(NUM_TYPE a,NUM_TYPE b){
bool nagative = (a.nagative && bool(b & 1)) ;
a = abs(a) ;
NUM_TYPE t(1) ;
while(!b.zero()){
if(b & 1)t *= a ;
b /= 2 ;
a *= a ;
}
return move(t) ;
}
lenght.cpp
ull lenght(const char *str){
if(!str)return 0 ;
const char* t = str ;
while(*t)++ t ;
return t - str ;
}
move.cpp
template<typename _Tp>
struct remove_reference
{ typedef _Tp type ; } ;
//将普通类型定义为type
template<typename _Tp>
struct remove_reference<_Tp&>
{ typedef _Tp type ; } ;
//将某类型左值引用定义为类型type
template<typename _Tp>
struct remove_reference<_Tp&&>
{ typedef _Tp type ; } ;
//将某类型右值引用定义为类型type
template <typename T>
typename remove_reference<T> :: type&& move(T&& t) noexcept{
return static_cast<typename remove_reference<T> :: type&&>(t) ;
}
//返回t的右值引用
pow.cpp
constexpr ull pow(ull n){
return (n == 0) ? (1) : (10 * pow(n - 1)) ;
}
useful_type.cpp
typedef unsigned char uchar ;
typedef unsigned int uint ;
typedef unsigned long long ull ;
typedef long long ll ;
测试代码:
#include "NUM_TYPE_def.cpp"
#include <time.h>
#define N (10000)
char t[N + 5] ;
int main(){
for(int i = 0;i < N;++ i)t[i] = '9' ;
t[N] = '\0' ;
NUM_TYPE a(t) ;
clock_t start = clock() ;
a *= a ;
printf("%llums",(clock() - start)) ;
return 0 ;
}
运算时间
测试代码
#include "NUM_TYPE_def.cpp"
#include <time.h>
#define N (10000)
char t[N + 5] ;
int main(){
for(int i = 0;i < N;++ i)t[i] = '9' ;
t[N] = '\0' ;
NUM_TYPE a(t) ;
clock_t start = clock() ;
a /= 1 ;
printf("%llums",(clock() - start)) ;
return 0 ;
}
在divc++中,可以选择速度优化,这个大数类在开启速度优化之后速度应该极限可以达到原来的10倍左右,但是缺点是编译速度过慢,内存耗费过高
本人只是一名闲得没事干的六年级xi ruo,如果各位大佬能有什么意见,可以提出来,感谢看到最后