056_bigN.h

#ifndef _INCL_BIGN
#define _INCL_BIGN
#include <iostream>
#include<iomanip>
using namespace std;

unsigned
reverseBit (unsigned a)
{
  unsigned b = 1;               //equals to 1(bin)
  for (; a; a >>= 1)            // a not zero
    {
      b <<= 1;
      b |= a & 1;
    }
  return b;
}

inline void
printError ()
{
  cout << "Error: overflow" << endl;
}

typedef unsigned long long verylong;
const verylong bigN_limit = 1e8;
const unsigned bigN_precision = 8;      //1e18;
const int bigN_gps = 30;        //must be even number
class bigN056
{
protected:
  verylong mantissa[bigN_gps];
public:
  bigN056 ();
  bigN056 (unsigned);
  void operator*= (unsigned);
  void operator+= (bigN056 &);
  void square ();
  verylong operator[] (int);
  void pow (unsigned);
  void printN ();
  bool isOverflow ();
};

bigN056::bigN056 ()
{
  for (int k = 0; k < bigN_gps; k++)
    mantissa[k] = 0;
}

bigN056::bigN056 (unsigned y)
{
  mantissa[0] = y;
  for (int k = 1; k < bigN_gps; k++)
    mantissa[k] = 0;
}

verylong bigN056::operator[](int i)
{
  return mantissa[i];
}

void
bigN056::square ()
{
  if (mantissa[bigN_gps / 2 + 1] != 0)  //overflow
    printError ();

  verylong mantissa2[bigN_gps];

  for (int i = 0; i < bigN_gps; i++)
    mantissa2[i] = 0;

  for (int i = 0; i < bigN_gps / 2; i++)

    for (int j = 0; j < bigN_gps / 2; j++)
      {
        mantissa2[i + j] += mantissa[i] * mantissa[j];
        if (mantissa2[i + j] >= bigN_limit)     //carry in
          {
            mantissa2[i + j + 1] += mantissa2[i + j] / bigN_limit;
            mantissa2[i + j] %= bigN_limit;
          }
      }

  if (isOverflow ())            //overflow
    printError ();

//copy back
  for (int i = 0; i < bigN_gps; i++)
    mantissa[i] = mantissa2[i];
}

void
bigN056::pow (unsigned y)
{
  bigN056 result (1);
  verylong x = mantissa[0];     //WARNING: assume the number is very small ********
  for (unsigned k = reverseBit (y); k > 1; k >>= 1)
    {
      if (k & 1)
        result *= x;

      result.square ();
    }
  for (int i = 0; i < bigN_gps; i++)
    mantissa[i] = result[i];
}

void
bigN056::operator*= (unsigned y)
{
  for (int i = 0; i < bigN_gps; i++)
    mantissa[i] *= y;

//carry in
  for (int i = 0; i < bigN_gps - 2; i++)
    if (mantissa[i] >= bigN_limit)
      {
        mantissa[i + 1] += mantissa[i] / bigN_limit;
        mantissa[i] %= bigN_limit;
      }
  if (isOverflow ())            //overflow
    printError ();
}

void
bigN056::operator+= (bigN056 & Y)
{
  for (int k = 0; k < bigN_gps; k++)
    mantissa[k] += Y[k];
  for (int k = 0; k < bigN_gps - 2; k++)
    if (mantissa[k] >= bigN_limit)
      {
        mantissa[k + 1] += mantissa[k] / bigN_limit;
        mantissa[k] %= bigN_limit;
      }
  if (isOverflow ())
    printError ();
}

void
bigN056::printN ()
{
  int k;
  for (k = bigN_gps - 1; k >= 0; k--)
    if (mantissa[k] != 0)
      break;

  cout << mantissa[k];
  for (k--; k >= 0; k--)
    cout << setfill ('0') << setw (bigN_precision) << mantissa[k];
}

bool
bigN056::isOverflow ()
{
  return (mantissa[bigN_gps - 1] >= bigN_limit);
}

ostream & operator<< (ostream & s, bigN056 & num)
{
  num.printN ();
  return s;
}

#endif