多倍長演算クラスのコード
bigint.h
#ifndef _BIGINT_INCLUDE_CHECK
#define _BIGINT_INCLUDE_CHECK
#include <algorithm>
#include <vector>
#include <list>
#include <iterator>
#include <iostream>
#include <iomanip>
using namespace std;
typedef unsigned long int LINT;
template <typename L>
class BIGINT {
list<L> lint;
int degree; // The num of this list
bool sign; // if this BIGINT is greater than 0, sign is true.
public:
BIGINT<L>() { lint.push_back(0); sign = true; }
BIGINT<L>(bool s, L n);
BIGINT<L>(const BIGINT<L>& org);
BIGINT<L>& operator=(const BIGINT<L>& org);
BIGINT<L> operator+(const BIGINT<L>& org);
BIGINT<L>& operator+=(const BIGINT<L>& org);
BIGINT<L> operator-(const BIGINT<L>& org);
BIGINT<L>& operator-=(const BIGINT<L>& org);
BIGINT<L>& operator++();
BIGINT<L> operator++(int dummy);
BIGINT<L>& operator--();
BIGINT<L> operator--(int dummy);
bool operator>(const BIGINT<L>& org);
bool operator<(const BIGINT<L>& org);
bool operator>=(const BIGINT<L>& org);
bool operator<=(const BIGINT<L>& org);
bool operator==(const BIGINT<L>& org);
bool operator!=(const BIGINT<L>& org);
bool absMoreEqual(const BIGINT<L>& org1, const BIGINT<L>& org2);
bool isCarryOutPlus(L x, L y, L carry);
bool isCarryOutMinus(L x, L y, L carry);
list<L> getLint() const { return lint; }
int getDegree() const { return degree; }
bool getSign() const { return sign; }
void setLint(bool s, list<L> lintOrg);
void setLint(list<L> lintOrg);
void setDegree(int d) { degree = d; }
void setSign(bool s) { sign = s; }
void show();
};
BIGINT<LINT> BIG1(true, 1);
template <typename L>
bool BIGINT<L>::isCarryOutPlus(L x, L y, L carry)
{
L temp = y + carry;
if (temp < y)
return true;
else if (x + temp < x)
return true;
return false;
}
template <typename L>
bool BIGINT<L>::isCarryOutMinus(L x, L y, L carry)
{
L temp = y + carry;
if (temp > y)
return true;
else if ( temp > x )
return true;
return false;
}
template <typename L>
BIGINT<L>::BIGINT(bool s, L n)
{
lint.push_back(n);
degree = 1;
sign = s;
}
template <typename L>
BIGINT<L>::BIGINT(const BIGINT<L>& org)
{
lint = org.getLint();
sign = org.getSign();
}
template <typename L>
BIGINT<L>& BIGINT<L>::operator=(const BIGINT<L>& org)
{
lint = org.getLint();
sign = org.getSign();
degree = org.getDegree();
return *this;
}
template <typename L>
BIGINT<L> BIGINT<L>::operator+(const BIGINT<L>& org)
{
BIGINT<L> retInt;
list<L> temp;
list<L> lint2 = org.getLint();
int degree2 = org.getDegree();
bool sign2 = org.getSign();
int longDegree;
bool longSign, smallSign;
typename list<L>::iterator iLong, iLongEnd, iSmall, iSmallEnd;
if (absMoreEqual(*this, org)) {
iLong = lint.begin();
iSmall = lint2.begin();
iLongEnd = lint.end();
iSmallEnd = lint2.end();
longDegree = degree;
longSign = sign;
smallSign = sign2;
} else {
iLong = lint2.begin();
iSmall = lint.begin();
iLongEnd = lint2.end();
iSmallEnd = lint.end();
longDegree = degree2;
longSign = sign2;
smallSign = sign;
}
L carry = 0;
if (sign == sign2) {
L small;
while (iLong != iLongEnd) {
if (iSmall == iSmallEnd)
small = 0;
else
small = *iSmall;
temp.push_back(*iLong + small + carry);
if (isCarryOutPlus(*iLong, small, carry))
carry = 1;
else
carry = 0;
iLong++;
if (iSmall != iSmallEnd)
iSmall++;
}
if (carry != 0) {
temp.push_back(carry);
retInt.setDegree(longDegree+1);
} else
retInt.setDegree(longDegree);
retInt.setSign(sign);
} else { // sign != sign2
L small;
while (iLong != iLongEnd) {
if (iSmall == iSmallEnd)
small = 0;
else
small = *iSmall;
/* example
* 1000 - 100 = 900 ... carry = 0
* 100 - 1000 = 4294966396 ... carry = 1
* 0 - 4294967295 - 1 = 0 ... carry = 1
* 0 - 4294967295 = 1 ... carry = 1
*/
temp.push_back(*iLong - small - carry);
if (isCarryOutMinus(*iLong, small, carry))
carry = 1;
else
carry = 0;
iLong++;
if (iSmall != iSmallEnd)
iSmall++;
}
// Because of checking size between lint and lint2,
// the BIGINT of return must have the longSign.
retInt.setSign(longSign);
if (temp.front() == 0) {
temp.erase(temp.begin());
retInt.setDegree(longDegree-1);
} else {
retInt.setDegree(longDegree);
}
}
retInt.setLint(temp);
return retInt;
}
template <typename L>
BIGINT<L>& BIGINT<L>::operator+=(const BIGINT<L>& org) {
*this = *this + org;
return *this;
}
template <typename L>
BIGINT<L> BIGINT<L>::operator-(const BIGINT<L>& org) {
BIGINT<L> temp = org;
temp.setSign(!temp.getSign());
return *this + temp;
}
template <typename L>
BIGINT<L>& BIGINT<L>::operator-=(const BIGINT<L>& org) {
*this = *this - org;
return *this;
}
// ++big;
template <typename L>
BIGINT<L>& BIGINT<L>::operator++() {
*this += BIG1;
return *this;
}
// big++;
template <typename L>
BIGINT<L> BIGINT<L>::operator++(int dummy) {
BIGINT<L> temp = *this;
++(*this);
return temp;
}
// --big;
template <typename L>
BIGINT<L>& BIGINT<L>::operator--() {
*this -= BIG1;
return *this;
}
// big--;
template <typename L>
BIGINT<L> BIGINT<L>::operator--(int dummy) {
BIGINT<L> temp = *this;
--(*this);
return temp;
}
template <typename L>
bool BIGINT<L>::operator>(const BIGINT<L>& org) {
list<L> lint2 = org.getLint();
bool sign2 = org.getSign();
if (sign == false && sign2 == true)
return false;
if (sign == true && sign2 == false)
return true;
if (degree < org.getDegree())
return false;
else if (degree > org.getDegree())
return true;
typename list<L>::reverse_iterator i, j, end = lint.rend();
if (sign == true) { // sign == true && sign2 == true
for (i = lint.rbegin(), j = lint2.rbegin(); i != end; i++, j++) {
if (*i > *j) return true;
}
} else { // sign == false && sign2 == false
for (i = lint.rbegin(), j = lint2.rbegin(); i != end; i++, j++) {
if (*i < *j) return true;
}
}
return false;
}
template <typename L>
bool BIGINT<L>::operator<(const BIGINT<L>& org) {
list<L> lint2 = org.getLint();
bool sign2 = org.getSign();
if (sign == true && sign2 == false)
return false;
if (sign == false && sign2 == true)
return true;
if (degree > org.getDegree())
return false;
else if (degree < org.getDegree())
return true;
typename list<L>::iterator i, j, end = lint.end();
if (sign == true) { // sign == true && sign2 == true
for (i = lint.begin(), j = lint2.begin(); i != end; i++, j++) {
if (*i < *j) return true;
}
} else { // sign == false && sign2 == false
for (i = lint.begin(), j = lint2.begin(); i != end; i++, j++) {
if (*i > *j) return true;
}
}
return false;
}
template <typename L>
bool BIGINT<L>::operator>=(const BIGINT<L>& org) {
if (*this == org || *this > org)
return true;
else
return false;
}
template <typename L>
bool BIGINT<L>::operator<=(const BIGINT<L>& org) {
if (*this == org || *this < org)
return true;
else
return false;
}
template <typename L>
bool BIGINT<L>::operator==(const BIGINT<L>& org) {
if (degree != org.getDegree())
return false;
return (lint == org.getLint());
}
template <typename L>
bool BIGINT<L>::operator!=(const BIGINT<L>& org) {
if (lint.sign != org.getSign())
return false;
if (lint.degree != org.getDegree())
return false;
return (lint != org.getLint());
}
template <typename L>
bool BIGINT<L>::absMoreEqual(const BIGINT<L>& org1, const BIGINT<L>& org2) {
BIGINT<L> t1, t2;
t1 = org1;
t2 = org2;
t1.setSign(true);
t2.setSign(true);
return t1 >= t2;
}
template <typename L>
void BIGINT<L>::setLint(bool s, list<L> lintOrg) {
sign = s;
degree = lintOrg.size();
lint = lintOrg;
}
template <typename L>
void BIGINT<L>::setLint(list<L> lintOrg) {
lint = lintOrg;
}
template <typename L>
void BIGINT<L>::show() {
typename list<L>::reverse_iterator i;
if (sign)
cout << "+";
else
cout << "-";
for (i = lint.rbegin(); i != lint.rend() ; i++) {
if (i != lint.rbegin() || lint.size() == 1)
cout << hex << setw(8) << setfill('0') << right;
cout << *i;
}
cout << endl;
cout << dec;
}
#endif // _BIGINT_INCLUDE_CHECK
main.cpp (テスト用)
#include <algorithm>
#include "bigint.h"
using namespace std;
int main()
{
BIGINT<LINT> a(true, 4294967295L), b(true, 2), c(true, 1), d, e;
ostream_iterator<LINT> out(cout, "\n");
d = b + a;
d.show();
e = d+b;
e.show();
e += a;
e.show();
e += a+a+a+a;
e.show();
d = c;
d -= a;
d.show();
d -= a;
d.show();
d -= a;
d.show();
cout << boolalpha;
cout << "d < e is " << (d < e) << endl;
cout << "b == b is " << (b == b) << endl;
cout << "e >= a is " << (e >= a) << endl;
cout << "e < a is " << (e < a) << endl;
return 0;
}
最終更新:2007年04月15日 12:47