杭州专业网站设计,高端 旅游 网站建设,学建筑设计出来能干嘛,用网站做简历目录
目录
目录
前言
为什么要大整数
大整形的加/减法
大整形的乘法
大整形除法
大整形开方
代码实现 前言
好久没有更新博客了#xff0c;hhh。时隔三个月#xff0c;我又回来了。先来点简单的大整形#xff0c;虽说简单#xff0c;但是在编写的时候还是debug了…目录
目录
目录
前言
为什么要大整数
大整形的加/减法
大整形的乘法
大整形除法
大整形开方
代码实现 前言
好久没有更新博客了hhh。时隔三个月我又回来了。先来点简单的大整形虽说简单但是在编写的时候还是debug了好久。
申明本文代码为博主自行编写尚有不足还望海涵也希望大佬可以指点一二。 为什么要大整数
这是一个令人尴尬的问题。个人看法是除了竞赛大概率碰不上大整形或者使用c/c处理大整形的几率很小。我想有的小伙伴要问了为什么说c/c处理大整形的几率很小。请看c/c的语言标准。时至今日c/c语言标准都没有明确规定相关生产商必须提供大整形。而在实际的生产中只有GCC一方提供了“大整形” -- 128位整形。事实上128位整型并不是内嵌的、官方认定的类型换句话说只要128位系统没出现128位类型就不能内嵌一定是一个认为实现的标准库。在现实生活中64位整数已经能够处理我们日常生活中的事情。正如有人调侃微软当初使用64位整型是因为需要64位来存放比尔盖茨的财产但是32位对于我们普通人来说足够了。由此可见实际生活没有那么多的大整形。凡事皆有例外为金融、航天等机密仪器所设计的程序可能会面临大整形、高精度的需求。因此你发现python在金融称王称霸是合理的。python处理大整形、高精度有着天然优势。但是在精密仪器上应该还是c/cpp开发的程序较多。
总而言之就是当64位整数不能够满足需求时就需要按需设计一个存储结构。这个存储结构就是大整形。顺便一提这里不建议使用128位整数因为可移植性比较差。 大整形的加/减法
大整形的加减法是最为简单的简单来说就是按位相加减事后借进位。 大整形的乘法
乘法的实现也比较低相较于加减法难一丢丢。如果我们有如下的式子 那么现在有可以像如上式子表达。为了方便表示结果存储在 ,并且。
于是我们知道,进一步推导得到。 大整形除法
除法最简单的直观的方式就是位对齐减试商。这里还可以来一个小优化就是试商的时候可以不用循环尝试使用二分搜索尝试这样会快一点。因为我们的基底不一定是10。如果是大基底循环试商就太慢了而选用小基底空间上又太浪费。
当然还有数学方法如果基于数学算法大整形的运算速度都可以提升到。但是我太菜了不能理解。所以就不出来瞎掰扯了误人子弟了。 大整形开方
这里也是使用了试根法。也有数学方法来着不过是基于除法实现。so除法不懂这里就更不懂了苦笑ing...。 代码实现
1000位十进制以内目前没发现bug。仍有待测试和完善乘法计算速度尚可。里面的减法只实现了移位减法供除法使用。一般的减法设计可参看加法 移位减法中的检测机制。
里面虽然是无符号类型但是无符号和有符号的计算效果是一样的。也就是说如果你需要设计有符号的大整形可以标注最高位的无符号第1个二进制位就是符号位。
#includecstdio
#includecstring
#includeiostream
#includevector
#includequeue
#includealgorithmclass BigInt : public std::vectorunsigned long long {
public:BigInt(unsigned long long n 0) {int i 0;do {push_back(0);at(i) n % base;n / base;} while (n);};BigInt(char* s) {int len strlen(s);for (int i len - 1; i 0; i - log_10_base) {unsigned long long num 0;for (int j i - log_10_base 1 0 ? 0 : i - log_10_base 1; j i; j)num num * 10 (s[j] - 0);push_back(num);}}const int theBase() const { return base; };// 赋值号BigInt operator (const BigInt other) {for (int i 0, j 0; i other.size(); i, j) {if (i size()) push_back(0);at(j) other[i];}for (int i other.size(); i size(); i) pop_back();return *this;};// 加法类BigInt operator (const BigInt other) {int min_digital std::min(size(), other.size());int max_digital std::max(size(), other.size());BigInt ret;for (int i max_digital - 1; i 0; --i) ret.push_back(0);for (int i 0; i min_digital; i) ret[i] at(i) other[i];for (int i min_digital; i size(); i) ret[i] at(i);for (int i min_digital; i other.size(); i) ret[i] other[i];ret.process();return ret;};BigInt operator (const BigInt other) {int min_digital std::min(size(), other.size());int max_digital std::max(size(), other.size());for (int i 0; i min_digital; i) at(i) other[i];for (int i min_digital; i other.size(); i) {push_back(0);at(i) other[i];}process();return *this;};// 乘法类BigInt operator* (const BigInt other) {BigInt ret;for (int i size() other.size() - 1; i 0; --i) ret.push_back(0);for (int i 0; i size(); i)for (int j 0; j other.size(); j)ret[i j] at(i) * other[j];ret.process();return ret;};BigInt operator* (const long long num) {BigInt ret;for (int i size() - 1; i 0; --i) ret.push_back(0);for (int i 0; i size(); i)ret[i] at(i) * num;ret.process();return ret;};BigInt operator* (const int num) {for (int i 0; i size(); i)at(i) * num;process();return *this;};BigInt operator* (const BigInt other) {BigInt ret;for (int i size() other.size() - 1; i 0; --i) ret.push_back(0);for (int i 0; i size(); i)for (int j 0; j other.size(); j)ret[i j] at(i) * other[j];ret.process();for (int i 0; i ret.size(); i) {if (i size()) push_back(0);at(i) ret[i];}return *this;};// 减法类// *this - (num shl) the base is class_base void sub_with_shl(const BigInt num, int shl) {for (int i 0; i num.size(); i) {unsigned long long check at(i shl);at(i shl) - num[i];if (check - num[i] check) { // 如果发生结尾at(i shl) base;at(i shl 1) - 1;int higher i shl 1;while (at(higher) base) { // 是否会产生连续借位at(higher) base;higher 1;at(higher) - 1;} // } // }process();};// 除法类// 最简单的方法就是一直循环减// 实际上还有数学方法本人能力有限无法实现涉及到多项式环快速逆Crypto的知识。BigInt operator/ (BigInt divisor) {if (*this divisor) return BigInt((unsigned long long) 0);BigInt quotiend;BigInt remainder *this;int shl size() - divisor.size(); // 移位if (!divisor.less_equal_with_shl(*this, shl)) shl - 1;while (divisor remainder) {unsigned long long q remainder.search_quotient(divisor, shl);remainder.sub_with_shl(divisor * (q - 1), shl);quotiend[quotiend.size() - 1] q - 1;quotiend.push_back(0);if (shl) shl - 1;}quotiend.pop_back();quotiend.reverse();quotiend.process();return quotiend;}BigInt operator% (BigInt divisor) {if (*this divisor) return *this;BigInt quotiend;BigInt remainder *this;int shl size() - divisor.size(); // 移位if (!divisor.less_equal_with_shl(*this, shl)) shl - 1;while (divisor remainder) {unsigned long long q remainder.search_quotient(divisor, shl);remainder.sub_with_shl(divisor * (q - 1), shl);quotiend[quotiend.size() - 1] q - 1;quotiend.push_back(0);if (shl) shl - 1;}return remainder;}int operator% (int divisor) {int r 0;for (int i size() - 1; i 0; --i) {// r r * base at(i);r (r * (base % divisor) at(i) % divisor) % divisor;}return r;}// 开方运算 -- 1000位精确BigInt sqrt() {BigInt ret;int sz 0;if (size() % 2 0) ret.resize(sz size() 1);else ret.resize(sz (size() 1) 1);for (int i sz - 1; i 0; --i) {search_root_for_ith_digital(ret, i);}ret.process();return ret;}// 比较类bool operator(const BigInt other) const {if (size() ! other.size()) return size() other.size();for (int i size() - 1; i 0; --i)if (at(i) ! other[i]) return at(i) other[i];return false;}bool operator(const BigInt other) const {if (size() ! other.size()) return size() other.size();for (int i size() - 1; i 0; --i)if (at(i) ! other[i]) return at(i) other[i];return true;}// *this shl otherbool less_equal_with_shl(const BigInt other, int shl) const {if (size() shl ! other.size()) return size() shl other.size();for (int i size() - 1; i 0; --i)if (at(i) ! other[i shl]) return at(i) other[i shl];return true;}// 输出void output() {printf(%Id, at(size() - 1));for (int i size() - 2; i 0; --i) {for (int j base / 10; j 0; j / 10)printf(%Id, at(i) % (j * 10) / j);}puts();}
private:void process() {for (int i 0; i size(); i) {if (at(i) base) continue;if (i 1 size()) push_back(0);at(i 1) at(i) / base;at(i) % base;}for (int i size() - 1; at(i) 0 i 0; --i) pop_back();}// 为除法设计 -- 小优化long long search_quotient(BigInt divisor, int shl) {long long l 1, r base;while (l r) {long long mid l (r - l 1);BigInt tmp divisor * mid;if (tmp.less_equal_with_shl(*this, shl)) l mid 1;else r mid;}return l;}BigInt reverse() {for (int i 0, j size() - 1; i j; i, --j) {unsigned long long tmp at(i);at(i) at(j);at(j) tmp;}return *this;}void search_root_for_ith_digital(BigInt ret, int i) {long long l 1, r base;while (l r) {ret[i] l (r - l 1);BigInt tmp ret * ret;if (tmp.less_equal_with_shl(*this, 0)) l ret[i] 1;else r ret[i];}ret[i] l;unsigned long long check ret[i];ret[i] - 1;if (ret[i] check) {int higner i 1;ret[i] base;ret[higner] - 1;while (ret[higner] base) {ret[higner] base;higner 1;ret[higner] - 1;}}return;}
private:const static int base 1000000000;const static int log_10_base 9;
};
