高精度算法之大整数类
2019-08-16 07:55:29来源:博客园 阅读 ()
高精度算法之大整数类
思想:
由于编程语言提供的基本数值数据类型表示的数值范围有限,不能满足较大规模的高精度数值计算,因此需要利用其他方法实现高精度数值的计算,于是产生了大数运算。大数运算主要有加、减、乘三种方法。
考虑用数组存储整数,并模拟手算的方法进行加减乘除四则运算。为了能像int一样方便的使用大整数,可以定义结构体,大整数类。
结构体BigInteger可用于存储高精度非负整数。这里存储的方案是每8位存在一个数组的元素里,所用base为1亿,也就是1e8这么多,从低位向高位存储
比如:123456789123456789 存储为| 23456789 |34567891 |12|在一个数组中。
大数结构体:
代码:
1 struct BigInteger 2 { 3 static const int BASE = 100000000; 4 static const int WIDTH = 8; 5 vector<int> s; 6 7 BigInteger(long long num = 0) {*this = num;}//构造函数 8 BigInteger operator=(long long num)//赋值运算符 9 { 10 s.clear(); 11 do 12 { 13 s.push_back(num%BASE); 14 num /= BASE; 15 }while(num>0); 16 return *this; 17 } 18 BigInteger operator=(const string& str)//赋值运算符 19 { 20 s.clear(); 21 int x,len = (str.length()-1)/WIDTH+1; 22 for(int i = 0;i<len;i++) 23 { 24 int end = str.length()-i*WIDTH; 25 int start = max(0,end-WIDTH); 26 sscanf(str.substr(start,end-start).c_str(),"%d",&x); 27 s.push_back(x); 28 } 29 return *this; 30 } 31 }
大数类的输入输出运算符重载:
还可以重载“<<”和“>>”运算符,使用方便
代码:
1 friend ostream& operator<<(ostream &out,const BigInteger& x) 2 { 3 out << x.s.back(); 4 for(int i = x.s.size()-2;i>=0;i--) 5 { 6 char buf[20]; 7 sprintf(buf,"%8d",x.s[i]); 8 for(int j = 0;j<strlen(buf);j++) 9 { 10 out << buf[j]; 11 } 12 } 13 return out; 14 } 15 friend istream& operator>>(istream &in,BigInteger& x) 16 { 17 string s; 18 if(!(in >> s)) return in; 19 x = s; 20 return in; 21 }
由于c++的继承机制,现在istream类和ostream类都可以使用它来输出输入大整数了
上述代码中BASE是静态成员变量,属于这个类型而不属于静态对象,用static修饰
大数类的加法:
1 BigInteger operator+(const BigInteger& b) const 2 { 3 BigInteger c; 4 c.s.clear(); 5 for(int i = 0,g = 0;;i++) 6 { 7 if(g==0&&i>=s.size()&&i>=b.s.size())//当进位为零并且加完了,退出。如果加完了进位不为零,就继续把进位补上,在退出 8 { 9 break; 10 } 11 int x = g;//g为进位数,满一个BASE才向下进一位 12 if(i<s.size()) x+=s[i]; 13 if(i<b.s.size()) x+=b.s[i]; 14 c.s.push_back(x%BASE);//进位后本位上的数 15 g = x/BASE;//更新进位数 16 } 17 return c; 18 } 19 BigInteger operator+=(const BigInteger& b) 20 { 21 *this = *this+b; 22 return *this; 23 }
大数类的比较:
一开始就比较两个数的位数,不相等直接返回,否则从后往前比(低位在前)。注意这是在没有前导零的情况下才能这样比,有前导零最后一位还要单独处理。
代码:
bool operator<(const BigInteger& b) const { if(s.size()!=b.s.size()) { return s.size()<b.s.size(); } for(int i = s.size()-1;i>=0;i--) { if(s[i]!=b.s[i]) { return s[i]<b.s[i]; } } return false; } bool operator>(const BigInteger& b) const { return b<*this; } bool operator<=(const BigInteger& b) const { return !(b<*this); } bool operator>=(const BigInteger& b) const { return !(*this<b); } bool operator!=(const BigInteger& b) const { return (b< *this||*this<b); } bool operator==(const BigInteger& b) const { return !(b<*this)&&!(*this<b); }
这时依赖比较运算符的容器函数就可以支持大整数类了。
代码汇总:
1 #include <cstdio> 2 #include <iostream> 3 #include <vector> 4 #include <cstring> 5 #include<set> 6 #include<map> 7 using namespace std; 8 struct BigInteger 9 { 10 static const int BASE = 100000000; 11 static const int WIDTH = 8; 12 vector<int> s; 13 14 BigInteger(long long num = 0) {*this = num;}//构造函数 15 BigInteger operator=(long long num)//赋值运算符 16 { 17 s.clear(); 18 do 19 { 20 s.push_back(num%BASE); 21 num /= BASE; 22 }while(num>0); 23 return *this; 24 } 25 BigInteger operator=(const string& str)//赋值运算符 26 { 27 s.clear(); 28 int x,len = (str.length()-1)/WIDTH+1; 29 for(int i = 0;i<len;i++) 30 { 31 int end = str.length()-i*WIDTH; 32 int start = max(0,end-WIDTH); 33 sscanf(str.substr(start,end-start).c_str(),"%d",&x); 34 s.push_back(x); 35 } 36 return *this; 37 } 38 friend ostream& operator<<(ostream &out,const BigInteger& x) 39 { 40 out << x.s.back(); 41 for(int i = x.s.size()-2;i>=0;i--) 42 { 43 char buf[20]; 44 sprintf(buf,"%8d",x.s[i]); 45 for(int j = 0;j<strlen(buf);j++) 46 { 47 out << buf[j]; 48 } 49 } 50 return out; 51 } 52 friend istream& operator>>(istream &in,BigInteger& x) 53 { 54 string s; 55 if(!(in >> s)) return in; 56 x = s; 57 return in; 58 } 59 60 bool operator<(const BigInteger& b) const 61 { 62 if(s.size()!=b.s.size()) 63 { 64 return s.size()<b.s.size(); 65 } 66 for(int i = s.size()-1;i>=0;i--) 67 { 68 if(s[i]!=b.s[i]) 69 { 70 return s[i]<b.s[i]; 71 } 72 } 73 return false; 74 } 75 bool operator>(const BigInteger& b) const 76 { 77 return b<*this; 78 } 79 bool operator<=(const BigInteger& b) const 80 { 81 return !(b<*this); 82 } 83 bool operator>=(const BigInteger& b) const 84 { 85 return !(*this<b); 86 } 87 bool operator!=(const BigInteger& b) const 88 { 89 return (b< *this||*this<b); 90 } 91 bool operator==(const BigInteger& b) const 92 { 93 return !(b<*this)&&!(*this<b); 94 } 95 BigInteger operator+(const BigInteger& b) const 96 { 97 BigInteger c; 98 c.s.clear(); 99 for(int i = 0,g = 0;;i++) 100 { 101 if(g==0&&i>=s.size()&&i>=b.s.size())//当进位为零并且加完了,退出。如果加完了进位不为零,就继续把进位补上,在退出 102 { 103 break; 104 } 105 int x = g;//g为进位数,满一个BASE才向下进一位 106 if(i<s.size()) x+=s[i]; 107 if(i<b.s.size()) x+=b.s[i]; 108 c.s.push_back(x%BASE);//进位后本位上的数 109 g = x/BASE;//更新进位数 110 } 111 return c; 112 } 113 BigInteger operator+=(const BigInteger& b) 114 { 115 *this = *this+b; 116 return *this; 117 } 118 }; 119 set<BigInteger> s; 120 map<BigInteger, int> m; 121 int main() 122 { 123 BigInteger y; 124 BigInteger x = y; 125 BigInteger z = 123; 126 127 BigInteger a, b; 128 cin >> a >> b; 129 cout << a + b << "\n"; 130 cout << BigInteger::BASE << "\n"; 131 return 0; 132 }View Code
参考代码:https://github.com/aoapc-book/aoapc-bac2nd/blob/master/ch5/BigInteger.cpp
参考文章:
关于sscanf,sprintf的使用:
https://www.runoob.com/cprogramming/c-function-sscanf.html
https://www.runoob.com/cprogramming/c-function-sprintf.html
原文链接:https://www.cnblogs.com/zhanhonhao/p/11255454.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash