高精度大數運算的實作

一個簡單的高精度大數運算的實作，實作了加法，乘法，乘方

#include <string>

#include <sstream>

#include <iostream>

#include <cctype>

#include <algorithm>

using namespace std;

#define sz(a) int((a).size())

class BigNum {

public:

BigNum() : integer("0"), dec_digits("0") {}

BigNum(string digit) {

int n = count(digit.begin(), digit.end(), '.');

if (n == 0) {

get_BigNum(digit, "0");

}

else if (n == 1) {

if (digit[0] == '.') {

get_BigNum("0", digit.substr(1, sz(digit) - 1));

}

else {

*find(digit.begin(), digit.end(), '.') = ' ';

istringstream is(digit);

string a, b;

is >> a >> b;

get_BigNum(a, b);

}

}

else {

integer = "0";

dec_digits = "0";

}

}

BigNum(string a, string b) {

get_BigNum(a, b);

}

BigNum operator +(BigNum rhs) {

int overflow = 0;

string b = add_decimal(dec_digits, rhs.dec_digits, overflow);

string a = add_integer(integer, rhs.integer, overflow);

while ( *b.rbegin() == '0' && sz(b) != 1) {

b.erase(b.end() - 1);

}

return BigNum(a, b);

}

BigNum operator *(BigNum b) {

BigNum total("0");

for ( int i = 0 ; i < sz(b.integer) ; ++i ) {

total = total + multi_bignum_leftshift(b.integer[i] - '0', sz(b.integer) - i - 1);

}

for ( int i = 0 ; i < sz(b.dec_digits) ; ++i ) {

total = total + multi_bignum_rightshift(b.dec_digits[i] - '0', i + 1);

}

return total;

}

BigNum operator ^(int n) {

BigNum total("1");

for ( int i = 0 ; i < n ; ++i ) {

total = *this * total;

}

return total;

}

friend ostream &operator <<(ostream &os, BigNum a);

private:

string integer;

string dec_digits;

void get_BigNum(string a = "0", string b = "0") {

if (sz(a) == 0) {

a = "0";

}

if (sz(b) == 0) {

b = "0";

}

integer = a;

dec_digits = b;

if (!valid_string(integer)) {

integer = "0";

}

else {

while (integer[0] == '0' && sz(integer) != 1 ) {

integer.erase(integer.begin());

}

}

if (!valid_string(dec_digits)) {

dec_digits = "0";

}

else {

while (*dec_digits.rbegin() == '0' && sz(dec_digits) != 1 ) {

dec_digits.erase(dec_digits.end() - 1);

}

}

}

bool valid_string(const string s) {

for ( int i = 0 ; i < sz(s) ; ++i ) {

if (!isdigit(s[i]) ) {

return false;

}

}

return true;

}

string add_decimal(string a, string b, int &overflow) {

int m = max(sz(a), sz(b));

a += string(m - sz(a), '0');

b += string(m - sz(b), '0');

return add_string(a, b, overflow, false);

}

string add_integer(string a, string b, int &overflow) {

int m = max(sz(a), sz(b));

a = string(m - sz(a), '0') + a;

b = string(m - sz(b), '0') + b;

return add_string(a, b, overflow, true);

}

string add_string(string a, string b, int &overflow, bool carry) {

for ( int i = sz(a) - 1; i >= 0; --i) {

int k = a[i] - '0' + b[i] - '0' + overflow;

overflow = k / 10;

k %= 10;

a[i] = char(k + '0');

}

if (overflow != 0 && carry) {

a = char(overflow + '0') + a;

}

return a;

}

string multi_string(string a, int n, int &overflow, bool carry) {

for ( int i = sz(a) - 1 ; i >= 0 ; --i ) {

int k = (a[i] - '0') * n + overflow;

overflow = k / 10;

k %= 10;

a[i] = char(k + '0');

}

if (overflow != 0 && carry ) {

a = char(overflow + '0') + a;

}

return a;

}

BigNum multi_bignum_leftshift(int j, int n) { //*this * j * 10^n

int overflow = 0;

string d = multi_string(dec_digits, j, overflow, false);

string i = multi_string(integer, j, overflow, true);

while (sz(d) <= n ) {

d += "0";

}

return BigNum(i + d.substr(0, n), d.substr(n, sz(d) -n));

}

BigNum multi_bignum_rightshift(int j, int n) { //*this * j / 10^n

int overflow = 0;

string d = multi_string(dec_digits, j, overflow, false);

string i = multi_string(integer, j, overflow, true);

while (sz(i) <= n ) {

i = "0" + i;

}

return BigNum(i.substr(0, sz(i) - n), i.substr(sz(i) - n, n) + d);

}

};

ostream &operator <<(ostream &os, BigNum a) {

os << a.integer << "." << a.dec_digits;

return os;

}

int main(int argc, char *argv[]) {

BigNum a("111111111111111111111111111111.422");

BigNum b("1.17800000000000");

BigNum c(".456");

BigNum d(".3x5.");

cout << a << endl;

cout << b << endl;

cout << c << endl;

cout << d << endl;

cout << a + b << endl;

cout << a * b << endl;

cout << (a ^ 5) << endl;

return 0;

}

E:/>make

g++ -Wall -O2 -o a.exe BigNum.cpp

111111111111111111111111111111.422

1.178

0.456

0.0

111111111111111111111111111112.6

130888888888888888888888888889.255116

16935087808430286711036596724990939728022489796609595420753582415282223238327490

728039428594047924943690833036969296690993088119224372978373892868.6374280665456

32