/*
integer.h
An Arbitrary Precision Integer Type
by Jason Lee @ calccrypto@yahoo.com
With much help from:
Auston Sterling - Initial debugging and coding help
Corbin @ Code Review (StackExchange) - wrote a sizeable chunk of code and suggestions
Keith Nicholas @ Code Review (StackExchange)
ROBOKITTY @ Code Review (StackExchange)
Winston Ewert @ Code Review (StackExchange) - suggested many improvements
This is an implementation of an arbitrary precision integer
container. The actual limit of how large the integers can
be is std::deque <uint8_t>().max_size() * 8 bits, which should
be enormous. Most of the basic operators are implemented,
although their outputs might not necessarily be the same output
as a standard version of that operator. Anything involving
pointers and addresses should be taken care of by C++.
Data is stored in big endian, so digits[0] is the most
significant byte (MSB), and digits[digits.size() - 1] is the
least significant byte (LSB).
Negative digitss are stored as their positive digitss,
with a flag that says the value is negative.
NOTE: Build with the newest compiler. Some functions are only
supported in the latest versions of C++ compilers.
NOTE: Base256 strings are assumed to be postive when read into
integer. Use operator-() to negate the digits.
NOTE: Multiple algorithms for subtraction, multiplication, and
division have been implemented and commented out. They
should all work, but are there for educational purposes.
If one is faster than another on different systems, by
all means change which algorithm is used. Just make sure
all related functions are changed as well.
NOTE: All algorithms operate on positive digitss only. The
operators deal with the signs.
NOTE: Changing the internal representation to a std::string
makes integer run slower than using a std::deque <uint8_t>
*/
#include <deque>
#include <iostream>
#include <limits>
#include <stdexcept>
#ifndef __INTEGER__
#define __INTEGER__
typedef uint32_t digit;
typedef uint64_t double_digit;
typedef std::deque <digit> base;
typedef std::deque <digit>::size_type d_size;
typedef std::string::size_type str_size;
const digit NEG1 = -1;
const digit BITS = sizeof(digit) << 3;
const digit HIGH_BIT = 1 << (BITS - 1);
class integer{
private:
bool _sign; // false = positive, true = negative
base digits; // holds the actual digits in base
template <typename Z> void setFromZ(Z val){
digits.clear();
_sign = false;
if (val < 0){
_sign = true;
val = -val;
}
while (val){
Z mask = 1;
digit d = 0;
for(unsigned int x = 0; x < BITS; x++){
d += ((val & 1)?mask:0);
val >>= 1;
mask <<= 1;
}
digits.push_front(d);
}
trim();
}
void trim(){ // remove 0 bytes from top of deque to save memory
while (!digits.empty() && !digits[0])
digits.pop_front();
if (digits.empty()) // change sign to false if value is zero
_sign = false;
}
public:
// Constructors
integer(): _sign(false){}
integer(const bool & b): _sign(false), digits(1, b){
trim();
}
template <typename Z> integer(Z val){
setFromZ(val);
}
integer(const integer & rhs): _sign(rhs._sign), digits(rhs.digits){
trim();
}
integer(base & val, bool s = false): _sign(s), digits(val){
trim();
}
// Written by Corbin
// Slightly modified by me
template <typename Iterator> integer(Iterator start, const Iterator& end, uint16_t base){
_sign = false;
if (start == end)
return;
if (base != 256) // All base 256 inputs assumed to be positive
if (*start == '-'){
_sign = true;
++start;
}
switch (base){
case 2:
while (start != end){
*this = (*this << 1) + (*start - '0');
++start;
}
break;
case 8:
while (start != end){
*this = (*this << 3) + (*start - '0');
++start;
}
break;
case 10:
while (start != end){
*this = (*this << 3) + (*this << 1) + (*start - '0');
++start;
}
break;
case 16:
while (start != end){
*this <<= 4;
if (std::isxdigit(*start)){
if (std::isdigit(*start))
*this += *start - 0x30; //0-9
else if (std::islower(*start))
*this += *start - 0x57; //a-f
else if (std::isupper(*start))
*this += *start - 0x37; //A-F
else
throw std::runtime_error("Character not between 'a' and 'f' found");
}
++start;
}
break;
case 256:
while (start != end){
*this = (*this << 8) + (uint8_t) *start;
++start;
}
break;
default:
throw std::runtime_error("Unknown base provided (must be 2,8, 10, 16 or 256)");
break;
}
trim();
}
// need at least gcc 4.7 to compile next line, otherwise use uncommented version
// integer(const std::string & val, uint16_t base): integer(val.begin(), val.end(), base){}
integer(const std::string & val, uint16_t base){
*this = integer(val.begin(), val.end(), base);
}
// RHS input args only
// Assignment Operator
integer & operator=(const bool & b){
digits.clear();
digits.push_back(b);
_sign = false;
return *this;
}
template <typename Z>
integer& operator=(const Z & val){
setFromZ(val);
return *this;
}
// Typecast Operators
operator bool(){
return !digits.empty();
}
operator char(){
if (digits.empty())
return 0;
return (char) (digits.back() & 255);
}
operator uint8_t(){
if (digits.empty())
return 0;
return digits.back() & 255;
}
operator uint16_t(){
uint16_t out = 0;
for(uint8_t x = 0; x < std::min(digits.size(), 2 / sizeof(digit)); x++)
out += (uint16_t) digits[digits.size() - x - 1] << (x * BITS);
return out;
}
operator uint32_t(){
uint32_t out = 0;
for(uint8_t x = 0; x < std::min(digits.size(), 4 / sizeof(digit)); x++)
out += (uint32_t) digits[digits.size() - x - 1] << (x * BITS);
return out;
}
operator uint64_t(){
uint64_t out = 0;
for(uint8_t x = 0; x < std::min(digits.size(), 8 / sizeof(digit)); x++)
out += (uint64_t) digits[digits.size() - x - 1] << (x * BITS);
return out;
}
operator int8_t(){
if (digits.empty())
return 0;
int8_t out = digits.back() & 255;
if (_sign)
out = -out;
return out;
}
operator int16_t(){
int16_t out = 0;
for(uint8_t x = 0; x < std::min(digits.size(), 2 / sizeof(digit)); x++)
out += (int16_t) digits[digits.size() - x - 1] << (x * BITS);
if (_sign)
out = -out;
return out;
}
operator int32_t(){
int32_t out = 0;
for(uint8_t x = 0; x < std::min(digits.size(), 4 / sizeof(digit)); x++)
out += (int32_t) digits[digits.size() - x - 1] << (x * BITS);
if (_sign)
out = -out;
return out;
}
operator int64_t(){
int64_t out = 0;
for(uint8_t x = 0; x < std::min(digits.size(), 8 / sizeof(digit)); x++)
out += (int64_t) digits[digits.size() - x - 1] << (x * BITS);
if (_sign)
out = -out;
return out;
}
// Bitwise Operators
template <typename Z> integer operator&(const Z & rhs){
return *this & integer(rhs);
}
integer operator&(integer rhs){
base out;
for(base::reverse_iterator i = digits.rbegin(), j = rhs.digits.rbegin(); (i != digits.rend()) && (j != rhs.digits.rend()); i++, j++)
out.push_front(*i & *j);
return integer(out, _sign & rhs._sign);
}
template <typename Z> integer operator|(const Z & rhs){
return *this | integer(rhs);
}
integer operator|(integer rhs){
base out;
base::reverse_iterator i = digits.rbegin(), j = rhs.digits.rbegin();
for(; (i != digits.rend()) && (j != rhs.digits.rend()); i++, j++)
out.push_front(*i | *j);
while (i != digits.rend())
out.push_front(*i++);
while (j != rhs.digits.rend())
out.push_front(*j++);
return integer(out, _sign | rhs._sign);
}
template <typename Z> integer operator^(const Z & rhs){
return *this ^ integer(rhs);
}
integer operator^(integer rhs){
base out;
base::reverse_iterator i = digits.rbegin(), j = rhs.digits.rbegin();
for(; (i != digits.rend()) && (j != rhs.digits.rend()); i++, j++)
out.push_front(*i ^ *j);
while (i != digits.rend())
out.push_front(*i++);
while (j != rhs.digits.rend())
out.push_front(*j++);
return integer(out, _sign ^ rhs._sign);
}
template <typename Z> integer operator&=(const Z & rhs){
*this = *this & rhs;
return *this;
}
integer operator&=(const integer & rhs){
*this = *this & rhs;
return *this;
}
template <typename Z> integer operator|=(const Z & rhs){
*this = *this | rhs;
return *this;
}
integer operator|=(const integer & rhs){
*this = *this | rhs;
return *this;
}
template <typename Z> integer operator^=(const Z & rhs){
*this = *this ^ rhs;
return *this;
}
integer operator^=(const integer & rhs){
*this = *this ^ rhs;
return *this;
}
integer operator~(){
base out = digits;
for(d_size i = 1; i < out.size(); i++)
out[i] ^= NEG1;
digit mask = HIGH_BIT;
while (!(out[0] & mask))
mask >>= 1;
while (mask){
out[0] ^= mask;
mask >>= 1;
}
return integer(out, _sign);
}
// Bit Shift Operators
template <typename Z> integer operator<<(const Z & shift){
return *this << ((uint64_t) shift);
}
// left bit shift. sign is maintained
integer operator<<(uint64_t shift){
if (!*this || !shift)
return *this;
base out = digits;
for(uint64_t i = 0; i < (shift / BITS); i++)
out.push_back(0);
shift %= BITS;
if (shift){
out.push_back(0);
return integer(out, _sign) >> (BITS - shift);
}
return integer(out, _sign);
}
integer operator<<(integer shift){
integer out = *this;
for(integer i = 0, s = shift / BITS; i < s; ++i)
out.digits.push_back(0);
return out << (uint64_t) (shift % BITS);
}
template <typename Z> integer operator>>(const Z & shift){
return *this >> ((uint64_t) shift);
}
// right bit shift. sign is maintained
integer operator>>(uint64_t shift){
if (shift >= bits())
return integer(0);
base out = digits;
for(uint64_t i = 0; i < (shift / BITS); i++)
out.pop_back();
shift %= BITS;
if (shift){
base v;
for(d_size i = out.size() - 1; i != 0; i--)
v.push_front(((out[i] >> shift) | (out[i - 1] << (BITS - shift))) & NEG1);
v.push_front(out[0] >> shift);
out = v;
}
return integer(out, _sign);
}
integer operator>>(integer shift){
integer out = *this;
for(integer i = 0, s = shift / BITS; i < s; ++i)
out.digits.pop_back();
return out >> (uint64_t) (shift % BITS);
}
template <typename Z> integer operator<<=(const Z & shift){
*this = *this << shift;
return *this;
}
integer operator<<=(const integer & shift){
*this = *this << shift;
return *this;
}
template <typename Z> integer operator>>=(const Z & shift){
*this = *this >> shift;
return *this;
}
integer operator>>=(const integer & shift){
*this = *this >> shift;
return *this;
}
// Logical Operators
bool operator!(){
return !((bool) *this);
}
template <typename Z> bool operator&&(const Z & rhs){
return (bool) *this && (bool) rhs;
}
bool operator&&(integer rhs){
return (bool) *this && (bool) rhs;
}
template <typename Z> bool operator||(const Z & rhs){
return ((bool) *this) || (bool) rhs;
}
bool operator||(integer rhs){
return ((bool) *this) || (bool) rhs;
}
// Comparison Operators
template <typename Z> bool operator==(const Z & rhs){
return (*this == integer(rhs));
}
bool operator==(const integer & rhs){
return ((_sign == rhs._sign) && (digits == rhs.digits));
}
template <typename Z> bool operator!=(const Z & rhs){
return !(*this == integer(rhs));
}
bool operator!=(const integer & rhs){
return !(*this == rhs);
}
private:
// operator> not considering signs
bool gt(const integer & lhs, const integer & rhs){
if (lhs.digits.size() > rhs.digits.size())
return true;
if (lhs.digits.size() < rhs.digits.size())
return false;
if (lhs.digits == rhs.digits)
return false;
for(d_size i = 0; i < lhs.digits.size(); i++)
if (lhs.digits[i] != rhs.digits[i])
return lhs.digits[i] > rhs.digits[i];
return false;
}
public:
template <typename Z> bool operator>(const Z & rhs){
return (*this > integer(rhs));
}
bool operator>(const integer & rhs){
if (_sign & !rhs._sign) // - > +
return false;
else if (!_sign & rhs._sign) // + > -
return true;
else if (_sign & rhs._sign) // - > -
return !gt(*this, rhs);
// else (!_sign & !rhs._sign) // + > +
return gt(*this, rhs);
}
template <typename Z> bool operator>=(const Z & rhs){
return ((*this > rhs) | (*this == rhs));
}
bool operator>=(const integer & rhs){
return ((*this > rhs) | (*this == rhs));
}
private:
// operator< not considering signs
bool lt(const integer & lhs, const integer & rhs){
if (lhs.digits.size() < rhs.digits.size())
return true;
if (lhs.digits.size() > rhs.digits.size())
return false;
if (lhs.digits == rhs.digits)
return false;
for(d_size i = 0; i < lhs.digits.size(); i++)
if (lhs.digits[i] != rhs.digits[i])
return lhs.digits[i] < rhs.digits[i];
return false;
}
public:
template <typename Z> bool operator<(const Z & rhs){
return (*this < integer(rhs));
}
bool operator<(const integer & rhs){
if (_sign & !rhs._sign) // - < +
return true;
else if (!_sign & rhs._sign) // + < -
return false;
else if (_sign & rhs._sign) // - < -
return !lt(*this, rhs);
// else (!_sign & !rhs._sign) // + < +
return lt(*this, rhs);
}
template <typename Z> bool operator<=(const Z & rhs){
return ((*this < rhs) | (*this == rhs));
}
bool operator<=(const integer & rhs){
return ((*this < rhs) | (*this == rhs));
}
private:
// Arithmetic Operators
integer add(integer & lhs, integer & rhs){
base out;
base::reverse_iterator i = lhs.digits.rbegin(), j = rhs.digits.rbegin();
bool carry = false;
double_digit sum;
for(; ((i != lhs.digits.rend()) && (j != rhs.digits.rend())); i++, j++){
sum = *i + *j + carry;
out.push_front(sum);
carry = (sum > NEG1);
}
for(; i != lhs.digits.rend(); i++){
sum = *i + carry;
out.push_front(sum);
carry = (sum > NEG1);
}
for(; j != rhs.digits.rend(); j++){
sum = *j + carry;
out.push_front(sum);
carry = (sum > NEG1);
}
if (carry)
out.push_front(1);
return integer(out);
}
public:
template <typename Z> integer operator+(const Z & rhs){
return *this + integer(rhs);
}
integer operator+(integer rhs){
if (!rhs)
return *this;
if (!*this)
return rhs;
integer out = *this;
if (_sign == rhs._sign){
out = add(out, rhs);
out._sign = _sign;
}
else if (gt(out, rhs)){
if ((!_sign & rhs._sign) | (_sign & !rhs._sign)) // + + - - + +
out = sub(out, rhs);
if ((!_sign & !rhs._sign) | (_sign & rhs._sign)) // + + + - + -
out = add(out, rhs);
out._sign = _sign;
}
else if (lt(out, rhs)){
if ((!_sign & rhs._sign) | (_sign & !rhs._sign)){ // + + - - + +
out = sub(rhs, out);
out._sign = !_sign;
}
if ((_sign & rhs._sign) | (!_sign & !rhs._sign)){ // + + + - + -
out = add(rhs, out);
out._sign = _sign;
}
}
else{ //if (eq(out, rhs)){
if ((_sign & rhs._sign) | (!_sign & !rhs._sign))
return integer(0);
//if ((_sign & !rhs._sign) | (!_sign & rhs._sign))
out <<= 1;
out._sign = _sign;
}
out.trim();
return out;
}
template <typename Z> integer operator+=(const Z & rhs){
*this = *this + rhs;
return *this;
}
integer operator+=(const integer & rhs){
*this = *this + rhs;
return *this;
}
private:
// Subtraction as done by hand
integer long_sub(integer & lhs, integer & rhs){
// rhs always smaller than lhs
d_size lsize = lhs.digits.size() - 1;
d_size rsize = rhs.digits.size() - 1;
for(d_size x = 0; x < rsize + 1; x++){
// if rhs digit is smaller than lhs digit, subtract
if (rhs.digits[rsize - x] <= lhs.digits[lsize - x])
lhs.digits[lsize - x] -= rhs.digits[rsize - x];
else{// carry
d_size y = lsize - x - 1;
while (!lhs.digits[y])
y--;
lhs.digits[y]--;
y++;
for(; y < lsize - x; y++)
lhs.digits[y] = NEG1;
lhs.digits[y] = ((double_digit) lhs.digits[y]) + ((uint64_t) 1 << BITS) - rhs.digits[rsize - x];
}
}
return lhs;
}
// // Two's Complement Subtraction
// integer two_comp_sub(const integer & lhs, integer & rhs){
// rhs = rhs.twos_complement(lhs.bits());
// return add(lhs, rhs) & (~(integer(1) << lhs.bits())); // Flip bits to get max of 1 << x
// }
integer sub(integer & lhs, integer & rhs){
if (!rhs)
return lhs;
if (!lhs)
return -rhs;
if (lhs == rhs)
return 0;
return long_sub(lhs, rhs);
// return two_comp_sub(lhs, rhs);
}
public:
template <typename Z> integer operator-(const Z & rhs){
return *this - integer(rhs);
}
integer operator-(integer rhs){
integer out = *this;
if (gt(out, rhs)){
if ((!_sign & rhs._sign) | (_sign & !rhs._sign)) // + - - - - +
out = add(out, rhs);
if ((!_sign & !rhs._sign) | (_sign & rhs._sign)) // + - + - - -
out = sub(out, rhs);
out._sign = _sign;
}
else if (lt(out, rhs)){
if ((!_sign & rhs._sign) | (_sign & !rhs._sign)){ // + - - - - +
out = add(out, rhs);
out._sign = _sign;
}
if ((_sign & rhs._sign) | (!_sign & !rhs._sign)){ // + - + - - -
out = sub(rhs, out);
out._sign = !_sign;
}
}
else{ //if (eq(out, rhs)){
if ((_sign & rhs._sign) | (!_sign & !rhs._sign))
return integer(0);
//if ((_sign & !rhs._sign) | (!_sign & rhs._sign))
out <<= 1;
out._sign = _sign;
}
out.trim();
return out;
}
template <typename Z> integer operator-=(const Z & rhs){
*this = *this - rhs;
return *this;
}
integer operator-=(const integer & rhs){
*this = *this - rhs;
return *this;
}
private:
// // Peasant Multiplication
// integer peasant(integer lhs, integer rhs){
// integer SUM = 0;
// for(d_size x = 0; x < lhs.bits(); x++){
// if (lhs[x])
// SUM += rhs;
// rhs <<= 1;
// }
// return SUM;
// }
// // Recurseive Peasant Algorithm
// integer recursive_peasant(integer lhs, integer rhs){
// if (!rhs)
// return 0;
// if (rhs & 1)
// return lhs + recursive_peasant(lhs << 1, rhs >> 1);
// return recursive_peasant(lhs << 1, rhs >> 1);
// }
// // Recursive Multiplication
// integer recursive_mult(integer lhs, integer rhs){
// if (!rhs)
// return 0;
// integer z = recursive_mult(lhs, rhs >> 1);
// if (!(rhs & 1))
// return z << 1;
// return lhs + (z << 1);
// }
// // Karatsuba Algorithm O(n^log2(3) = n ^ 1.585)
// // Thanks to kjo @ stackoverflow for fixing up my original Karatsuba Algorithm implementation
// // which i then converted to C++ and made a few changes
// // http://stackoverflow.com/questions/7058838/karatsuba-algorithm-too-much-recursion
// integer karatsuba(integer lhs, integer rhs, integer bm = 0x1000000U){
// // b is base = 256
// // m is chars = 4
// // bm is max digits = b ^ m
//
// if ((lhs <= bm) | (rhs <= bm))
// return peasant(lhs, rhs);
//
// std::pair <integer, integer> x = dm(lhs, bm);
// std::pair <integer, integer> y = dm(rhs, bm);
// integer x0 = x.second;
// integer x1 = x.first;
// integer y0 = y.second;
// integer y1 = y.first;
//
// integer z0 = karatsuba(x0, y0);
// integer z2 = karatsuba(x1, y1);
// integer z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0;
// return karatsuba(karatsuba(z2, bm) + z1, bm) + z0;
// }
// Long multiplication
integer long_mult(integer & lhs, integer & rhs){
unsigned int zeros = 0;
integer row, out = 0;
for(base::reverse_iterator i = lhs.digits.rbegin(); i != lhs.digits.rend(); i++){
row.digits = base(zeros++, 0); // zeros on the right hand side
digit carry = 0;
for(base::reverse_iterator j = rhs.digits.rbegin(); j != rhs.digits.rend(); j++){
double_digit prod = (double_digit(*i) * double_digit(*j)) + carry;// multiply through
row.digits.push_front(prod & NEG1);
carry = prod >> BITS;
}
if (carry)
row.digits.push_front(carry);
out = add(out, row);
}
return out;
}
public:
template <typename Z> integer operator*(const Z & rhs){
return *this * integer(rhs);
}
integer operator*(integer rhs){
if ((!*this) || (!rhs)) // if multiplying by 0
return 0;
if (*this == 1) // if multiplying by 1
return rhs;
if (rhs == 1) // if multiplying by 1
return *this;
bool s = _sign ^ rhs._sign;
integer out = *this;
out._sign = false;
rhs._sign = false;
if (rhs.abs() == 10){ // if rhs == 10
out = (out << 3) + (out << 1);
out._sign = s;
return out;
}
if (out.abs() == 10){ // if lhs == 10
out = (rhs << 3) + (rhs << 1);
out._sign = s;
return out;
}
// while lhs is multiple of 2
// while (!(rhs & 1)){
// rhs >>= 1;
// out <<= 1;
// }
// out = peasant(out, rhs);
// out = recursive_peasant(out, rhs);
// out = recursive_mult(out, rhs);
// out = karatsuba(out, rhs);
out = long_mult(out, rhs);
out._sign = s;
out.trim();
return out;
}
template <typename Z> integer operator*=(const Z & rhs){
*this = *this * rhs;
return *this;
}
integer operator*=(const integer & rhs){
*this = *this * rhs;
return *this;
}
private:
// // Long Division returning both quotient and remainder
// std::pair <integer, integer> long_div(const integer & lhs, const integer & rhs){
// std::pair <integer, integer> qr;
// qr.first = 0;
// qr.second = lhs;
// integer copyd = rhs;
// integer adder = 1;
// while (qr.second > copyd){
// copyd <<= 1;
// adder <<= 1;
// }
// while (qr.second >= rhs){
// if (qr.second >= copyd){
// qr.second -= copyd;
// qr.first |= adder;
// }
// copyd >>= 1;
// adder >>= 1;
// }
// return qr;
// }
// // Recursive Division that returns both the quotient and remainder
// // Recursion took up way too much memory
// std::pair <integer, integer> recursive_divmod(integer lhs, const integer & rhs){
// std::pair <integer, integer> qr;
// if (!lhs){
// qr.first = 0;
// qr.second = 0;
// return qr;
// }
// qr = recursive_divmod(lhs >> 1, rhs);
// qr.first <<= 1;
// qr.second <<= 1;
// if (lhs & 1)
// qr.second++;
// if (qr.second >= rhs){
// qr.second -= rhs;
// qr.first++;
// }
// return qr;
// }
// Non-Recursive version of above algorithm
std::pair <integer, integer> non_recursive_divmod(integer & lhs, integer & rhs){
std::pair <integer, integer> qr;
qr.first = 0;
qr.second = 0;
for(size_t x = lhs.bits(); x > 0; x--){
qr.first <<= 1;
qr.second <<= 1;
if (lhs[x - 1])
qr.second++;
if (qr.second >= rhs){
qr.second -= rhs;
qr.first++;
}
}
return qr;
}
// division ignoring signs
std::pair <integer, integer> dm(integer & lhs, integer & rhs){
if (!rhs) // divide by 0 error
throw std::runtime_error("Error: division or modulus by zero");
std::pair <integer, integer> out;
if (rhs == 1){ // divide by 1 check
out.first = lhs;
out.second = 0;
return out;
}
if (lhs == rhs){ // divide by same digits check
out.first = 1;
out.second = 0;
return out;
}
if (!lhs){ // 0 / rhs check
out.first = 0;
out.second = 0;
return out;
}
if (lt(lhs, rhs)){ // lhs < rhs check
out.first = 0;
out.second = lhs;
return out;
}
// Check for powers of two /////////////////////
// Cannot do it the easy way for some reason
if (!(rhs & 1)){
uint64_t s = 0;
integer copyd(rhs);
while (!(copyd & 1)){
copyd >>= 1;
s++;
}
if (copyd == 1){
out.first = lhs >> s;
out.second = lhs - (out.first << s);
return out;
}
}
////////////////////////////////////////////////
// return long_div(lhs, rhs);
// return recursive_divmod(lhs, rhs);
return non_recursive_divmod(lhs, rhs);
}
public:
template <typename Z> integer operator/(const Z & rhs){
return *this / integer(rhs);
}
integer operator/(integer rhs){
bool s = _sign ^ rhs._sign;
integer lhs = *this;
lhs._sign = false;
rhs._sign = false;
integer out = dm(lhs, rhs).first;
out._sign = s;
out.trim();
return out;
}
template <typename Z> integer operator/=(const Z & rhs){
*this = *this / integer(rhs);
return *this;
}
integer operator/=(const integer & rhs){
*this = *this / rhs;
return *this;
}
template <typename Z> integer operator%(const Z & rhs){
return *this % integer(rhs);
}
integer operator%(integer rhs){
bool s1 = _sign;
bool s2 = rhs._sign;
integer lhs = *this;
lhs._sign = false;
rhs._sign = false;
integer out = dm(lhs, rhs).second;
out.trim();
if (!out.digits.empty()){
if (s1 == s2)
out._sign = s1;
else{
out = rhs - out;
out._sign = s2;
}
}
return out;
}
template <typename Z> integer operator%=(const Z & rhs){
*this = *this % integer(rhs);
return *this;
}
integer operator%=(const integer & rhs){
*this = *this % rhs;
return *this;
}
// Increment Operator
integer & operator++(){
*this += 1;
return *this;
}
integer operator++(int){
integer temp(*this);
++*this;
return temp;
}
// Decrement Operator
integer & operator--(){
*this -= 1;
return *this;
}
integer operator--(int){
integer temp(*this);
--*this;
return temp;
}
// Nothing done since promotion doesnt work here
integer operator+() const{
return *this;
}
// Flip Sign
integer operator-(){
integer out = *this;
if (out.digits.size())
out._sign = !out._sign;
return out;
}
// get private digitss
bool sign() const{
return _sign; // false = pos, true = neg
}
size_t bits() const{
if (digits.empty())
return 0;
unsigned int out = digits.size() * BITS;
digit mask = HIGH_BIT;
while (!(digits[0] & mask)){
out--;
mask >>= 1;
}
return out;
}
unsigned int bytes() const{
return digits.size() * sizeof(digits);
}
base data() const{
return digits;
}
// Miscellaneous Functions
integer twos_complement(unsigned int b = 0){
base out = digits;
for(d_size i = 1; i < out.size(); i++)
out[i] ^= NEG1;
digit mask = HIGH_BIT;
while (!(out[0] & mask))
mask >>= 1;
integer top = integer(1) << ((uint64_t) (out.size() - 1) * BITS);
while (mask){
out[0] ^= mask;
mask >>= 1;
top <<= 1;
}
integer OUT(out, _sign);
while (b){
OUT ^= top;
top <<= 1;
b--;
}
return OUT + 1;
}
integer abs() const{
integer out = *this;
out._sign = false;
return out;
}
void fill(const uint64_t & b){
// fills an integer with 1s
digits = base(b / BITS, NEG1);
if (b % BITS)
digits.push_front((1 << (b % BITS)) - 1);
}
bool operator[](const unsigned int & b){
// get bit, where 0 is the lsb and bits() - 1 is the msb
if (b >= bits()) // if given index is larger than bits in this digits, return 0
return 0;
return (digits[digits.size() - (b / BITS) - 1] >> (b % BITS)) & 1;
}
// Output digits as a string in bases 2 to 16, and 256
std::string str(integer base = 10, unsigned int length = 1){
std::string out = "";
// if (base == 256){
// if (digits.empty())
// out = std::string(1, 0);
// for(d_size x = 0; x < digits.size(); x++)
// out += std::string(1, digits[x]);
// while (out.size() < length)
// out = std::string(1, 0) + out;
// if (_sign){
// if (!out[0])
// out = out.substr(1, out.size() - 1);
// out = "-" + out;
// }
// }
// else{
if (((base < 2) || (base > 16)) && (base != 256)) // if base outside of 2 <= base <= 16
base = 10; // set to default digits of 10
integer rhs = *this;
static const std::string B16 = "0123456789abcdef";
std::pair <integer, integer> qr;
do{
qr = dm(rhs, base);
out = B16[qr.second] + out;
rhs = qr.first;
} while (rhs);
while (out.size() < length)
out = "0" + out;
if (_sign){
if (out[0] == '0')
out = out.substr(1, out.size() - 1);
out = "-" + out;
}
// }
return out;
}
};
// lhs type Z as first arguemnt
// Bitwise Operators
template <typename Z> Z operator&(const Z & lhs, integer rhs){
return (Z) (rhs & lhs);
}
template <typename Z> Z operator|(const Z & lhs, integer rhs){
return (Z) (rhs | lhs);
}
template <typename Z> Z operator^(const Z & lhs, integer rhs){
return (Z) (rhs ^ lhs);
}
template <typename Z> Z operator&=(Z & lhs, integer rhs){
lhs = (Z) (rhs & lhs);
return lhs;
}
template <typename Z> Z operator|=(Z & lhs, integer rhs){
lhs = (Z) (rhs | lhs);
return lhs;
}
template <typename Z> Z operator^=(Z & lhs, integer rhs){
lhs = (Z) (rhs ^ lhs);
return lhs;
}
// Comparison Operators
template <typename Z> bool operator==(const Z & lhs, integer rhs){
return (rhs == lhs);
}
template <typename Z> bool operator!=(const Z & lhs, integer rhs){
return (rhs != lhs);
}
template <typename Z> bool operator>(const Z & lhs, integer rhs){
return (rhs < lhs);
}
template <typename Z> bool operator<(const Z & lhs, integer rhs){
return (rhs > lhs);
}
template <typename Z> bool operator>=(const Z & lhs, integer rhs){
return (rhs <= lhs);
}
template <typename Z> bool operator<=(const Z & lhs, integer rhs){
return (rhs >= lhs);
}
// Arithmetic Operators
template <typename Z> Z operator+(const Z & lhs, integer rhs){
return (Z) (rhs + lhs);
}
template <typename Z> Z & operator+=(Z & lhs, integer rhs){
lhs = (Z) (rhs + lhs);
return lhs;
}
template <typename Z> Z operator-(const Z & lhs, integer rhs){
return (Z) (integer(lhs) - rhs);
}
template <typename Z> Z & operator-=(Z & lhs, integer rhs){
lhs = lhs - rhs;
return lhs;
}
template <typename Z> Z operator*(const Z & lhs, integer rhs){
return (Z) (rhs * lhs);
}
template <typename Z> Z & operator*=(Z & lhs, integer rhs){
lhs = (Z) (rhs * lhs);
return lhs;
}
template <typename Z> Z operator/(const Z & lhs, integer rhs){
return (Z) (integer(lhs) / rhs);
}
template <typename Z> Z & operator/=(Z & lhs, integer rhs){
lhs = integer(lhs) / rhs;
return lhs;
}
template <typename Z> Z operator%(const Z & lhs, integer rhs){
return (Z) (integer(lhs) % rhs);
}
template <typename Z> Z & operator%=(Z & lhs, integer rhs){
lhs = lhs % rhs;
return lhs;
}
// IO Operators
std::ostream & operator<<(std::ostream & stream, integer rhs){
if (stream.flags() & stream.oct)
stream << rhs.str(8);
else if (stream.flags() & stream.hex)
stream << rhs.str(16);
else
stream << rhs.str(10);
return stream;
}
std::istream & operator>>(std::istream & stream, integer & rhs){
uint8_t base;
if (stream.flags() & stream.oct)
base = 8;
else if (stream.flags() & stream.hex)
base = 16;
else
base = 10;
std::string in;
stream >> in;
rhs = integer(in, base);
return stream;
}
// Special functions
std::string makebin(integer digits, unsigned int size = 1){
// Changes a digits into its binary string
return digits.str(2, size);
}
std::string makehex(integer digits, unsigned int size = 1){
// Changes a digits into its hexadecimal string
return digits.str(16, size);
}
std::string makeascii(integer digits, unsigned int size = 1){
// Changes a digits into ASCII
return digits.str(256, size);
}
integer abs(integer digits){
// returns the absolute digits of the integer
return digits.abs();
}
template <typename Z>
integer POW(integer base, Z exp)
{
if (exp < 0)
return 0;
integer result = 1;
// take advantage of optimized integer * 10
if (base == 10){
for(Z x = 0; x < exp; x++)
result *= base;
return result;
}
while (exp)
{
if (exp & 1)
result *= base;
exp >>= 1;
base *= base;
}
return result;
}
#endif // INTEGER_H
int main(){
integer a("1111111111111111", 16);
std::cout << (a *a).str(16) << std::endl;
return 0;
}