來自 [e-mail]

[[e-mail]]

// BigNum class is used for "UNSIGNED" BigNum
// with NO SAFE CHECK in the class
// Be careful if you may cover negative numbers

// if need ostream& operator<<(ostream&,BigNum&)
#include <iostream.h>

// if need BigNum::BigNum(char*)
#include <string.h>

#define MAXNEED (1000)
#define PERDIGIT (10000)
#define LOGDIGIT (4) // LOGDIGIT=log10(PERDIGIT)
#define MAXARRAY ((MAXNEED+LOGDIGIT-1)/LOGDIGIT)

// if need BigNum::BigNum(char*)
#define ISNUM(c) ((c)>='0' && (c)<='9')

class BigNum{
// Declare everything public
public:

// Data
  int nDigit;
  int digit[MAXARRAY];

// Constructors that may need
  BigNum();
  BigNum(const char* str);
  BigNum(const unsigned int num);
  BigNum(const BigNum& bn);

// Destructor does nothing
  ~BigNum(){};

// Arithmatic Operators
  friend BigNum operator+(const BigNum& first,const BigNum& second);
  friend BigNum operator-(const BigNum& first,const BigNum& second);
  friend BigNum operator*(const BigNum& first,const BigNum& second);
  friend BigNum operator/(const BigNum& first,const BigNum& second);
  friend BigNum operator%(const BigNum& first,const BigNum& second);
  BigNum sqrt();
  BigNum pow(const int n);

  BigNum& operator=(const BigNum& second);

  BigNum& operator+=(const BigNum& second);
  BigNum& operator-=(const BigNum& second);
  BigNum& operator*=(const BigNum& second);
  BigNum& operator/=(const BigNum& second);
  BigNum& operator%=(const BigNum& second);

// Compare operators  
  friend int operator==(const BigNum& first,const BigNum& second);
  friend int operator>(const BigNum& first,const BigNum& second);
  friend int operator<(const BigNum& first,const BigNum& second);

  friend int operator!=(const BigNum& first,const BigNum& second){
    return !(operator==(first,second));
  }
  friend int operator>=(const BigNum& first,const BigNum& second){
    return !(operator<(first,second));
  }
  friend int operator<=(const BigNum& first,const BigNum& second){
    return !(operator>(first,second));
  }
// Output Stream
  friend ostream& operator<<(ostream& os,BigNum& bn);

// Useful Methods
  inline void clear(){
    int i;
    for(i=0;i<MAXARRAY;i++) digit[i]=0;
    nDigit=0;
  }
  BigNum& div2(){
    int i;
    for(i=nDigit-1;i>=0;i--){
      if (digit[i] % 2 && i) digit[i-1]+=PERDIGIT;
      digit[i]/=2;
    }
    if (!digit[nDigit-1]) nDigit--;
    return (*this);
  }
};

// Compare Operators
int operator==(const BigNum& first,const BigNum& second){
  if (first.nDigit!=second.nDigit) return 0;
  int i;
  for(i=0;i<first.nDigit;i++)
    if (first.digit[i]!=second.digit[i]) return 0;
  return 1;
}

int operator>(const BigNum& first,const BigNum& second){
  if (first.nDigit>second.nDigit) return 1;
  if (first.nDigit<second.nDigit) return 0;
  int i;
  for(i=first.nDigit-1;i>=0;i--){
    if (first.digit[i]>second.digit[i]) return 1;
    if (first.digit[i]<second.digit[i]) return 0;
  }
  return 0;
}

int operator<(const BigNum& first,const BigNum& second){
  if (first.nDigit<second.nDigit) return 1;
  if (first.nDigit>second.nDigit) return 0;
  int i;
  for(i=first.nDigit-1;i>=0;i--){
    if (first.digit[i]<second.digit[i]) return 1;
    if (first.digit[i]>second.digit[i]) return 0;
  }
  return 0;
}

// Arith Operators

BigNum operator+(const BigNum& first,const BigNum& second){
// need BigNum::operator+=(BigNum&),BigNum::BigNum(BigNum&)
  BigNum temp(first);
  temp+=second;
  return temp;
}

BigNum operator-(const BigNum& first,const BigNum& second){
// need BigNum::operator-=(BigNum&),BigNum::BigNum(BigNum&)
  BigNum temp(first);
  temp-=second;
  return temp;
}

BigNum operator*(const BigNum& first,const BigNum& second){
// need BigNum::operator*=(BigNum&),BigNum::BigNum(BigNum&)
  BigNum temp(first);
  temp*=second;
  return temp;
}

BigNum operator/(const BigNum& first,const BigNum& second){
// need BigNum::operator/=(BigNum&),BigNum::BigNum(BigNum&)
  BigNum temp(first);
  temp/=second;
  return temp;
}

BigNum operator%(const BigNum& first,const BigNum& second){
// need BigNum::operator%=(BigNum&),BigNum::BigNum(BigNum&)
  BigNum temp(first);
  temp%=second;
  return temp;
}

BigNum BigNum::sqrt(){
// need BigNum::clear(),BigNum::operator-(BigNum&),
//      BigNum::operator>(BigNum&),BigNum::div2(),
//      BigNum::operator+(BigNum&),
//      BigNum::operator*(BigNum&),
//      BigNum::operator=(BigNum&),

  BigNum lower;
  BigNum higher;
  BigNum temp;
  BigNum mul;

  higher.clear();
  higher.nDigit=(nDigit+3)/2;
  higher.digit[higher.nDigit-1]=1;

  while(higher-lower>1){
    temp=(lower+higher).div2();
    mul=temp*temp;
    if (!(mul>(*this)))
      lower=temp;
    else higher=temp;
  }
  return (lower);
}

BigNum BigNum::pow(const int n){
// need BigNum::operator*(BigNum&),
//      BigNum::operator=(BigNum&)

  BigNum temp(1);
  BigNum mul(*this);
  int i;

  for(i=1;i<=n;i<<=1){
    if (i & n) temp*=mul;
    mul*=mul;
  }
  return temp;
}

BigNum& BigNum::operator=(const BigNum& second){

  for(nDigit=0;nDigit<second.nDigit;nDigit++)
    digit[nDigit]=second.digit[nDigit];
  return (*this);
}

BigNum& BigNum::operator+=(const BigNum& second){
  int i;
  digit[nDigit]=0;
  for(i=0;i<nDigit || i<second.nDigit;i++){
    if (i<second.nDigit)
      digit[i]+=second.digit[i];

    if (i<nDigit)
      digit[i+1]+=digit[i]/PERDIGIT;
    else
      digit[i+1]=digit[i]/PERDIGIT;

    digit[i]%=PERDIGIT;
  }
  nDigit=(digit[i] ? (i+1) : (i));
  return (*this);
}

BigNum& BigNum::operator-=(const BigNum& second){
  int i,j;
  for(i=0;i<second.nDigit;i++){
    if (digit[i]<second.digit[i]){
      digit[i]+=PERDIGIT;

      for(j=i+1;!(digit[j]);j++)
        digit[j]+=(PERDIGIT-1);

      digit[j]--;
    }
    digit[i]-=second.digit[i];
  }
  for(i=nDigit-1;!(digit[i]);i--);
  nDigit=i+1;
  return (*this);
}

BigNum& BigNum::operator*=(const BigNum& second){
// need BigNum::clear(),BigNum::operator=(BigNum&)
  int i,j;
  BigNum temp;
  temp.clear();
  for(i=0;i<nDigit;i++){
    for(j=0;j<second.nDigit;j++){
      temp.digit[i+j]+=digit[i]*second.digit[j];
      temp.digit[i+j+1]+=(temp.digit[i+j] / PERDIGIT);
      temp.digit[i+j]%=PERDIGIT;
    }
  }
  temp.nDigit=i+j;
  while(temp.digit[temp.nDigit-1]==0) temp.nDigit--;
  (*this)=temp;
  return *this;
}

BigNum& BigNum::operator/=(const BigNum& second){
// need BigNum::clear(),BigNum::operator-(BigNum&),
//      BigNum::operator>(BigNum&),BigNum::div2(),
//      BigNum::operator+(BigNum&),
//      BigNum::operator*(BigNum&),
//      BigNum::operator=(BigNum&),

  BigNum lower;
  BigNum higher;
  BigNum temp;
  BigNum mul;

  higher.clear();
  higher.nDigit=nDigit-second.nDigit+2;
  higher.digit[higher.nDigit-1]=1;

  if (second==2) return (*this).div2();
  while(higher-lower>1){
    temp=(lower+higher).div2();
    mul=temp*second;
    if (!(mul>(*this))) lower=temp;
    else higher=temp;
  }
  (*this)=lower;
  return (*this);
}

BigNum& BigNum::operator%=(const BigNum& second){
// need BigNum::clear(),BigNum::operator-(BigNum&),
//      BigNum::operator>(BigNum&),BigNum::div2(),
//      BigNum::operator+(BigNum&),
//      BigNum::operator*(BigNum&),
//      BigNum::operator=(BigNum&),
//      BigNum::operator-=(BigNum&),

  BigNum lower;
  BigNum higher;
  BigNum temp;
  BigNum mul;

  higher.clear();
  higher.nDigit=nDigit-second.nDigit+2;
  higher.digit[higher.nDigit-1]=1;

  if(second==2) return ((*this)=digit[0] % 2);

  while(higher-lower>1){
    temp=(lower+higher).div2();
    mul=temp*second;
    if (!(mul>(*this))) lower=temp;
    else higher=temp;
  }
  (*this)-=(lower*second);
  return (*this);
}

// Output Stream
ostream& operator<<(ostream& os,BigNum& bn){
  int i,j;

  os << bn.digit[bn.nDigit-1];
  for(i=bn.nDigit-2;i>=0;i--){
    for(j=PERDIGIT/10;j>=1;j/=10){
      if (j>bn.digit[i]) os << '0';
      else break;
    }
    if (bn.digit[i]) os << bn.digit[i];
  }
  return os;
}

// Constructors
BigNum::BigNum(){
  nDigit=1;
  digit[0]=0;
}

BigNum::BigNum(const char* str){

  int i,j,pow10;
  for(i=strlen(str),j=LOGDIGIT,nDigit=0;i>=0;i--){
    if (j == LOGDIGIT){
      j=0;
      nDigit++;
      digit[nDigit-1]=0;
      pow10=1;
    }
    if (ISNUM(str[i])){
      j++;
      digit[nDigit-1]+=pow10*(str[i]-'0');
      pow10*=10;
    }
  }
}

BigNum::BigNum(const unsigned int num){
  int n=num;

  nDigit=0;

  do{
    nDigit++;
    digit[nDigit-1]=n % PERDIGIT;
    n/=PERDIGIT;
  }while(n);
}

BigNum::BigNum(const BigNum& bn){
  for(nDigit=0;nDigit<bn.nDigit;nDigit++)
    digit[nDigit]=bn.digit[nDigit];
}

int main(void){
  BigNum b1;
  BigNum b2("9999999999999999");
  BigNum b3(13311);
  BigNum b4(b2);
// test for constructor
  cout << b1 << endl << b2 << endl << b3 << endl << b4 << endl;

// test for operators
  b1=10;
  cout << (b1=b1.pow(8).sqrt()) << endl;
  cout << b3+b2 << endl << b3*2+b3*b2-b3 << endl;
  cout << b1 << endl << b3 << endl;
  cout << b3/b1 << endl << b3%b1 << endl ;
  cout << (BigNum(1024).sqrt()).pow(3) << endl;
  return 0;
}