Wiki

verylong.cpp

/*
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <limits>
#include <string>
*/
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
 
#include "verylong.h"
 
// Class Data
const Verylong Verylong::zero = Verylong("0");
const Verylong Verylong::one = Verylong("1");
const Verylong Verylong::two = Verylong("2");
 
 
// Constructors, Destructors and Conversion operators.
 
Verylong::Verylong(const std::string &value = "0")
{
	std::string s = (value == "") ? "0" : value;
 
	vlsign = (s[0] == '-') ? 1 : 0;        // check for negative sign
	if (ispunct(s[0]))                     // if the first character
		vlstr = s.substr(1, s.length() - 1); // is a punctuation mark.
	else 
		vlstr = s;
}
 
 
Verylong::Verylong(int n)
{
	if (n < 0)                           // check for sign and convert the
	{                                    // number to positive if it is negative
		vlsign = 1; 
		n = (-n); 
	} 
	else 
		vlsign = 0;                        
 
	if (n > 0)
	  while (n >= 1)                     // extract the number digit by digit and store 
	  {                                  // internally
		  vlstr = char(n % 10 + '0') + vlstr;
		  n /= 10;
	  }
	  else 
		  vlstr = std::string("0");          // else number is zero
}
 
 
Verylong::Verylong(const Verylong &x) : vlstr(x.vlstr), vlsign(x.vlsign) 
{ 
}
 
 
Verylong::~Verylong() 
{ 
}
 
 
Verylong::operator int() const
{
	int number, factor = 1;
	static Verylong max0(INT_MAX);
	static Verylong min0(INT_MIN + 1);
	std::string::const_reverse_iterator j = vlstr.rbegin();
 
	if (*this > max0)
	{
		std::cerr << "Error : Conversion Verylong->integer is not possible" << std::endl;
		return INT_MAX;
	}
	else 
	if (*this < min0)
	{
		std::cerr << "Error : Conversion Verylong->integer is not possible" << std::endl;
		return INT_MIN;
	}
 
	number = *j - '0';
 
	for (j++; j != vlstr.rend(); j++)
	{
		factor *= 10;
		number += (*j - '0') * factor;
	}
 
	if (vlsign) 
		return -number;
 
	return number;
}
 
 
Verylong::operator double() const
{
	double sum, factor = 1.0;
	std::string::const_reverse_iterator i = vlstr.rbegin();
 
	sum = double(*i) - '0';
 
	for (i++; i != vlstr.rend(); i++)
	{
		factor *= 10.0;
		sum += double(*i - '0') * factor;
	}
 
	if (vlsign) 
		return -sum;
 
	return sum;
}
 
 
Verylong::operator std::string() const
{
	if (vlstr.length() == 0) 
		return std::string("0");
 
	return vlstr;
}
 
 
 
// Various member operators
 
const Verylong & Verylong::operator = (const Verylong &rhs)
{
	if (this == &rhs) 
		return *this;
 
	vlstr = rhs.vlstr;
	vlsign = rhs.vlsign;
 
	return *this;
}
 
 
// Unary - operator
Verylong Verylong::operator -() const
{
	Verylong temp(*this);
 
	if (temp != zero)  
		temp.vlsign = !vlsign;
 
	return temp;
}
 
 
// Prefix increment operator
Verylong Verylong::operator ++ ()
{
	return *this = *this + one;
}
 
 
// Postfix increment operator
Verylong Verylong::operator ++ (int)
{
	Verylong result(*this);
 
	*this = *this + one;
	return result;
}
 
 
// Prefix decrement operator
Verylong Verylong::operator -- ()
{
	return *this = *this - one;
}
 
 
// Postfix decrement operator
Verylong Verylong::operator -- (int)
{
	Verylong result(*this);
 
	*this = *this - one;
	return result;
}
 
 
Verylong Verylong::operator += (const Verylong &v)
{
	return *this = *this + v;
}
 
 
Verylong Verylong::operator -= (const Verylong &v)
{
	return *this = *this - v;
}
 
 
Verylong Verylong::operator *= (const Verylong &v)
{
	return *this = *this * v;
}
 
 
Verylong Verylong::operator /= (const Verylong &v)
{
	return *this = *this / v;
}
 
 
Verylong Verylong::operator %= (const Verylong &v)
{
	return *this = *this % v;
}
 
 
Verylong Verylong::operator ^= (const Verylong &degree)
{
	Verylong N(degree);
	Verylong Y("1");
 
	if (N == Verylong::zero)
		return Verylong::one;
 
	if (N < Verylong::zero)
		return Verylong::zero;
 
	while (1)
	{
		if (N == Verylong::zero)
		{
			*this = Y;
			break;
		}
 
		Y = Y * *this;
		N = N - Verylong::one;
	}
 
	return *this;
}
 
 
 
// Various friendship operators and functions.
 
Verylong operator + (const Verylong &u, const Verylong &v)
{
	char digitsum, d1, d2, carry = 0;
	std::string temp;
	std::string::const_reverse_iterator j, k;
 
	if (u.vlsign ^ v.vlsign)
	{
		if (u.vlsign == 0) 
			return u - abs(v);
		else               
			return v - abs(u);
	}
 
	for (j = u.vlstr.rbegin(), k = v.vlstr.rbegin();
		j != u.vlstr.rend() || k != v.vlstr.rend();)
	{
		d1 = (j == u.vlstr.rend()) ? 0 : *(j++) - '0'; // get digit
		d2 = (k == v.vlstr.rend()) ? 0 : *(k++) - '0'; // get digit
		digitsum = d1 + d2 + carry;                    // add digits
 
		carry = (digitsum >= 10) ? 1 : 0;
		digitsum -= 10 * carry;
 
		temp = char(digitsum + '0') + temp;
	}
 
	if (carry) // if carry at end, last digit is 1
		temp = '1' + temp;  
 
	if (u.vlsign) 
		temp = '-' + temp;
 
	return Verylong(temp);
}
 
 
Verylong operator - (const Verylong &u, const Verylong &v)
{
	char d, d1, d2, borrow = 0;
	int negative;
	std::string temp, temp2;
	std::string::reverse_iterator i, j;
 
	if (u.vlsign ^ v.vlsign)
	{
		if (u.vlsign == 0) 
			return u + abs(v);
		else
			return -(v + abs(u));
	}
 
	Verylong w, y;
 
	if (u.vlsign == 0)                   // both u,v are positive
		if (u<v) 
		{ 
			w = v; 
			y = u; 
			negative = 1; 
		}
		else    
		{ 
			w = u; 
			y = v; 
			negative = 0; 
		}
		else                               // both u,v are negative
		if (u<v) 
		{ 
			w = u; 
			y = v; 
			negative = 1; 
		}
		else    
		{ 
			w = v; 
			y = u; 
			negative = 0; 
		}
 
	for (i = w.vlstr.rbegin(), j = y.vlstr.rbegin();
		i != w.vlstr.rend() || j != y.vlstr.rend();)
	{
		d1 = (i == w.vlstr.rend()) ? 0 : *(i++) - '0';
		d2 = (j == y.vlstr.rend()) ? 0 : *(j++) - '0';
 
		d = d1 - d2 - borrow;
		borrow = (d < 0) ? 1 : 0;
		d += 10 * borrow;
 
		temp = char(d + '0') + temp;
	}
 
	while (temp[0] == '0') 
		temp = temp.substr(1);
 
	if (negative) 
		temp = '-' + temp;
 
	return Verylong(temp);
}
 
 
Verylong operator * (const Verylong &u, const Verylong &v)
{
	Verylong pprod("1"), tempsum("0");
	std::string::const_reverse_iterator r = v.vlstr.rbegin();
 
	for (int j = 0; r != v.vlstr.rend(); j++, r++)
	{
		int digit = *r - '0';              // extract a digit
 
		pprod = u.multdigit(digit);        // multiplied by the digit
		pprod = pprod.mult10(j);           // "adds" suitable zeros behind
		tempsum = tempsum + pprod;         // result added to tempsum
	}
 
	tempsum.vlsign = u.vlsign^v.vlsign;  // to determine sign
	return tempsum;
}
 
 
//  This algorithm is the long division algorithm.
Verylong operator / (const Verylong &u, const Verylong &v)
{
	int len = u.vlstr.length() - v.vlstr.length();
	std::string temp;
	Verylong w, y, b, c, d, quotient = Verylong::zero;
 
	if (v == Verylong::zero)
	{
		std::cerr << "Error : division by zero" << std::endl;
		return Verylong::zero;
	}
 
	w = abs(u); 
	y = abs(v);
 
	if (w < y) 
		return Verylong::zero;
 
	c = Verylong(w.vlstr.substr(0, w.vlstr.length() - len));
 
	for (int i = 0; i <= len; i++)
	{
		quotient = quotient.mult10(1);
 
		b = d = Verylong::zero;            // initialize b and d to 0
 
		while (b < c)
		{
			b = b + y; d = d + Verylong::one;
		}
 
		if (c < b)                           // if b>c, then
		{                                    // we have added one count too many 
			b = b - y;
			d = d - Verylong::one;
		}
 
		quotient = quotient + d;             // add to the quotient
 
		if (i < len)
		{
			// partial remainder * 10 and add to next digit
			c = (c - b).mult10(1);
			c += Verylong(w.vlstr[w.vlstr.length() - len + i] - '0');
		}
	}
 
	quotient.vlsign = u.vlsign^v.vlsign;   // to determine sign
 
	return quotient;
}
 
 
Verylong operator % (const Verylong &u, const Verylong &v)
{
	return (u - v*(u / v));
}
 
 
Verylong operator ^ (const Verylong &u, const Verylong &v)
{
	//return (u - v*(u / v));
 
	Verylong temp(u);
 
	return temp ^= v;
}
 
 
 
int operator == (const Verylong &u, const Verylong &v)
{
	return (u.vlsign == v.vlsign && u.vlstr == v.vlstr);
}
 
 
int operator != (const Verylong &u, const Verylong &v)
{
	return !(u == v);
}
 
 
int operator < (const Verylong &u, const Verylong &v)
{
	if (u.vlsign < v.vlsign) 
		return 0;
	else 
	if (u.vlsign > v.vlsign) 
		return 1;
 
	// exclusive or (^) to determine sign
	if (u.vlstr.length() < v.vlstr.length()) 
		return (1 ^ u.vlsign);
	else 
	if (u.vlstr.length() > v.vlstr.length()) 
		return (0 ^ u.vlsign);
 
	return (u.vlstr < v.vlstr && !u.vlsign) ||
		(u.vlstr > v.vlstr && u.vlsign);
}
 
 
int operator <= (const Verylong &u, const Verylong &v)
{
	return (u<v || u == v);
}
 
 
int operator >(const Verylong &u, const Verylong &v)
{
	return (!(u<v) && u != v);
}
 
 
int operator >= (const Verylong &u, const Verylong &v)
{
	return (u>v || u == v);
}
 
 
// Calculate the absolute value of a number
Verylong abs(const Verylong &v)
{
	Verylong u(v);
 
	if (u.vlsign) 
		u.vlsign = 0;
 
	return u;
}
 
// Calculate the integer square root of a number
//    based on the formula (a+b)^2 = a^2 + 2ab + b^2
Verylong sqrt(const Verylong &v)
{
	// if v is negative, error is reported
	if (v.vlsign) 
	{ 
		std::cerr << "NaN" << std::endl; 
		return Verylong::zero; 
	}
 
	int j, k = v.vlstr.length() + 1, num = k >> 1;
	Verylong y, z, sum, tempsum, digitsum;
 
	std::string temp, w(v.vlstr);
 
	k = 0;
	j = 1;
 
	// segment the number 2 digits by 2 digits
	if (v.vlstr.length() % 2) 
		digitsum = Verylong(w[k++] - '0');
	else
	{
		digitsum = Verylong((w[k] - '0') * 10 + w[k + 1] - '0');
		k += 2;
	}
 
	// find the first digit of the integer square root
	sum = z = Verylong(int(sqrt(double(digitsum))));
 
	// store partial result
	temp = char(int(z) + '0');
	digitsum = digitsum - z*z;
 
	for (; j<num; j++)
	{
		// get next digit from the number
		digitsum = digitsum.mult10(1) + Verylong(w[k++] - '0');
		y = z + z;        // 2*a
		z = digitsum / y;
		tempsum = digitsum.mult10(1) + Verylong(w[k++] - '0');
		digitsum = -y*z.mult10(1) + tempsum - z*z;
 
		// decrease z by 1 and re-calculate when it is over-estimated.
		while (digitsum < Verylong::zero)
		{
			--z;
			digitsum = -y*z.mult10(1) + tempsum - z*z;
		}
 
		temp = temp + char(int(z) + '0');  // store partial result
		z = sum = sum.mult10(1) + z;       // update value of the partial result
	}
 
	Verylong result(temp);
 
	return result;
}
 
 
// Raise a number X to a power of degree
Verylong pow(const Verylong &X, const Verylong &degree)
{
	Verylong N(degree), Y("1"), x(X);
 
	if (N == Verylong::zero) 
		return Verylong::one;
 
	if (N < Verylong::zero) 
		return Verylong::zero;
 
	while (1)
	{
		if (N%Verylong::two != Verylong::zero)
		{
			Y = Y * x;
			N = N / Verylong::two;
			if (N == Verylong::zero) 
				return Y;
		}
		else  
			N = N / Verylong::two;
 
		x = x * x;
	}
}
 
 
// Double division function
double div(const Verylong &u, const Verylong &v)
{
	double qq = 0.0, qqscale = 1.0;
	Verylong w, y, b, c;
	int d, count,
		decno = std::numeric_limits<double>::digits; // number of significant digits
 
	if (v == Verylong::zero)
	{
		std::cerr << "ERROR : Division by zero" << std::endl;
		return 0.0;
	}
 
	if (u == Verylong::zero) 
		return 0.0;
 
	w = abs(u); 
	y = abs(v);
 
	while (w<y) 
	{ 
		w = w.mult10(1); 
		qqscale *= 0.1; 
	}
 
	int len = w.vlstr.length() - y.vlstr.length();
	std::string temp = w.vlstr.substr(0, w.vlstr.length() - len);
 
	c = Verylong(temp);
 
	for (int i = 0; i <= len; i++)
	{
		qq *= 10.0;
 
		b = Verylong::zero; d = 0;         // initialize b and d to 0
 
		while (b < c)
		{
			b += y; d += 1;
		}
 
		if (c < b)                         // if b>c, then
		{                                  // we have added one count too many
			b -= y; 
			d -= 1;
		}                                
 
		qq += double(d);                   // add to the quotient
 
		c = (c - b).mult10(1);             // the partial remainder * 10
 
		if (i < len)                       // and add to next digit
			c += Verylong(w.vlstr[w.vlstr.length() - len + i] - '0');
	}
 
	qq *= qqscale; count = 0;
 
	while (c != Verylong::zero && count < decno)
	{
		qqscale *= 0.1;
 
		b = Verylong::zero; d = 0;         // initialize b and d to 0
 
		while (b < c)
		{
			b += y; d += 1;
		}
 
		if (c < b)                         // if b>c, then
		{                                  // we have added one count too many
			b -= y; d -= 1;
		}           
 
		qq += double(d)*qqscale;
 
		c = (c - b).mult10(1);
		count++;
	}
 
	if (u.vlsign^v.vlsign)               // check for the sign
		qq *= (-1.0); 
 
	return qq;
}
 
 
std::ostream & operator << (std::ostream &s, const Verylong &v)
{
	if (v.vlstr.length() > 0)
	{
		if (v.vlsign) s << "-";
		s << v.vlstr;
	}
	else 
		s << "0";
 
	return s;
}
 
 
std::istream & operator >> (std::istream &s, Verylong &v)
{
	std::string temp(10000, ' ');
 
	s >> temp;
	v = Verylong(temp);
 
	return s;
}
 
 
//
// Private member functions: multdigit(), mult10().
//
 
// Multiply this Verylong number by num
Verylong Verylong::multdigit(int num) const
{
	int carry = 0;
	std::string::const_reverse_iterator r;
 
	if (num)
	{
		std::string temp;
 
		for (r = vlstr.rbegin(); r != vlstr.rend(); r++)
		{
			int d1 = *r - '0',               // get digit and multiplied by
				digitprod = d1*num + carry;    // that digit plus carry
 
			if (digitprod >= 10)             // if there's a new carry,
			{
				carry = digitprod / 10;        // carry is high digit
				digitprod -= carry * 10;       // result is low digit
			}
			else 
				carry = 0;                     // otherwise carry is 0
 
			temp = char(digitprod + '0') + temp;   // insert char in string
		}
 
		if (carry) //if carry at end,
			temp = char(carry + '0') + temp; 
 
		Verylong result(temp);
		return result;
	}
	else 
		return zero;
}
 
 
// Multiply this Verylong number by 10*num
Verylong Verylong::mult10(int num) const
{
	int j;
 
	if (*this != zero)
	{
		std::string temp;
 
		for (j = 0; j<num; j++) 
			temp = temp + '0';
 
		Verylong result(vlstr + temp);
 
		if (vlsign) 
			result = -result;
 
		return result;
	}
	else 
		return zero;
}
 
 
//template <> Verylong zero(Verylong) { return Verylong::zero; }
//template <> Verylong one(Verylong) { return Verylong::one; }