多倍長演算クラスのコード

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;
}

タグ:

RSA C++
最終更新:2007年04月15日 12:47