Improving a custom integer class 2.0

Question

As sort of a follow up to my previous question from a year ago, what are some suggestions you can think of that will improve this code, whether is directly programming related or algorithm related? I know there are better algorithms for multiplication and division, but I don't understand many of them (yet).

I have improved my code a lot since last year, but its still very slow.

Sorry for the long code, but there is a lot of stuff, even after removing over 100000 characters. Also, all this modifying might have messed up some of the formatting.

Please visit http://calccrypto.wikidot.com/programming:integer for the most up to date code. The code below is only for reference and may not have the bug fixes suggested put in

// Note: All of the operators have been templated or explicitly overloaded for standard 
// integer types in the full code
// go to http://calccrypto.wikidot.com/programming:integer
// for an older version of this class because most functions haven't
// been touched for a long time

// i removed them because they took up so much space, and apparantly there
// is a limit of 300000 characters to post

#include <cstdlib>
#include <deque>
#include <iostream>

#ifndef __INTEGER__
#define __INTEGER__

class integer{
private:
  bool SIGN;                // false = positive, true = negative
  std::deque <uint8_t> value;       // holds the actual value in base256

  void clean(){               // remove 0 bytes from top of deque to save memory
    while (value.size() && !value[0])
      value.pop_front();
  }

public:
  // Constructors
  integer(){SIGN = false;}

  // similar for uint8_t, uint16_t, and uint64_t
  integer(uint32_t rhs){
    SIGN = false;
    while (rhs){
      value.push_front(rhs & 255);
      rhs >>= 8;
    }
  }

  // similar for int8_t, int16_t, and int64_t
  integer(int32_t rhs){
    SIGN = (rhs < 0);
    if (rhs < 0)
      rhs = -rhs;
    while (rhs){
      value.push_front(rhs & 255);
      rhs >>= 8;
    }
  }

  integer(const integer & rhs){
    value = rhs.value;
    SIGN = rhs.SIGN;
    clean();
  }

  integer(std::deque <uint8_t> & val){
    value = val;
    SIGN = false;
    clean();
  }

  integer(bool s, std::deque <uint8_t> & val){
    value = val;
    SIGN = value.size()?s:false;
    clean();
  }

  integer(std::string str, int base){
    integer temp = 0;
    SIGN = false;
    if (str[0] == '-'){
      SIGN = true;
      str = str.substr(1, str.size() - 1);
    }
    switch (base){
      case 2:
        for(unsigned int x = 0; x < str.size(); x++)
          temp = (temp << 1) + (str[x] - 48);
        break;
      case 8:
        for(unsigned int x = 0; x < str.size(); x++)
          temp = (temp << 3) + (str[x] - 48);
        break;
      case 10:
        for(unsigned int x = 0; x < str.size(); x++)
          temp = (temp << 3) + (temp << 1) + (str[x] - 48);
        break;
      case 16:
        for(unsigned int x = 0; x < str.size(); x++){
          temp <<= 4;
          if ((0x2f < str[x]) && (str[x] < 0x3a))     // 0 - 9
            temp += str[x] - 0x30;
          else if ((0x60 < str[x]) && (str[x] < 0x67))  // a - f
            temp += str[x] - 0x57;
          else if  ((0x40 < str[x]) && (str[x] < 0x47))   // A - F
            temp += str[x] - 0x37;
          else{
            std::cerr << "Error: Character not between 'a' and 'f' found." << std::endl;
            exit(1);
          }
        }
        break;
      case 256:
        for(unsigned int x = 0; x < str.size(); x++)
          temp.value.push_back(str[x]);
        break;
      default:
        break;
    }
    value = temp.value;
  }

  //  RHS input args only

  // Assignment Operator

  // similar for uint8_t, uint16_t, and uint64_t
  integer & operator=(uint32_t rhs){
    value.clear();
    SIGN = false;
    while (rhs){
      value.push_front(rhs & 255);
      rhs >>= 8;
    }
    return *this;
  }

  // similar for int8_t, int16_t, and int64_t
  integer & operator=(int32_t rhs){
    value.clear();
    SIGN = (rhs < 0);
    if (rhs < 0)
      rhs = -rhs;
    while (rhs){
      value.push_front(rhs & 255);
      rhs >>= 8;
    }
    return *this;
  }

  integer & operator=(integer rhs){
    value = rhs.value;
    SIGN = rhs.SIGN;
    return *this;
  }

  // Typecast Operators
  operator bool(){
    return (bool) value.size();
  }

  operator char(){
    if (!value.size())
      return 0;
    return (char) value.back();
  }

  operator uint8_t(){
    if (!value.size())
      return 0;
    return value.back();
  }

  // similar for uint16_t, and uint64_t
  operator uint32_t(){
    uint32_t out = 0;
    for(uint8_t x = 0; x < ((4 < value.size())?4:value.size()); x++)
      out = (out << 8) + (uint8_t) value[value.size() - x - 1];
    return out;
  }

  operator int8_t(){
    if (!value.size())
      return 0;
    int8_t out = value.back();
    if (SIGN)
      out = -out;
    return out;
  }

  // similar for int16_t, and int64_t
  operator int32_t(){
    int64_t out = 0;
    for(uint8_t x = 0; x < ((4 < value.size())?4:value.size()); x++)
      out = (out << 8) + (uint8_t) value[value.size() - x - 1];
    if (SIGN)
      out = -out;
    return out;
  }

  // Bitwise Operators
  integer operator&(integer rhs){
    std::deque <uint8_t> out;
    for(std::deque <uint8_t>::reverse_iterator i = value.rbegin(), j = rhs.value.rbegin(); (i != value.rend()) && (j != rhs.value.rend()); i++, j++)
      out.push_front(*i & *j);
    return integer(SIGN & rhs.SIGN, out);
  }

  integer operator|(integer rhs){
    std::deque <uint8_t> out;
    std::deque <uint8_t>::reverse_iterator i = value.rbegin(), j = rhs.value.rbegin();
    for(; (i != value.rend()) && (j != rhs.value.rend()); i++, j++)
      out.push_front(*i | *j);
    while (i != value.rend())
      out.push_front(*i++);
    while (j != rhs.value.rend())
      out.push_front(*j++);
    return integer(SIGN | rhs.SIGN, out);
  }

  integer operator^(integer rhs){
    std::deque <uint8_t> out;
    std::deque <uint8_t>::reverse_iterator i = value.rbegin(), j = rhs.value.rbegin();
    for(; (i != value.rend()) && (j != rhs.value.rend()); i++, j++)
      out.push_front(*i ^ *j);
    while (i != value.rend())
      out.push_front(*i++);
    while (j != rhs.value.rend())
      out.push_front(*j++);
    return integer(SIGN ^ rhs.SIGN, out);
  }

  integer operator&=(integer rhs){
    *this = *this & rhs;
    return *this;
  }

  integer operator|=(integer rhs){
    *this = *this | rhs;
    return *this;
  }

  integer operator^=(const integer rhs){
    *this = *this ^ rhs;
    return *this;
  }

  integer operator~(){
    std::deque <uint8_t> out = value;
    for(unsigned int i = 1; i < out.size(); i++)
      out[i] ^= 0xff;
    uint8_t mask = 128;
    while (!(out[0] & mask))
      mask >>= 1;
    while (mask){
      out[0] ^= mask;
      mask >>= 1;
    }
    return integer(SIGN, out);
  }

  // Bit Shift Operators
  // left bit shift. sign is maintained
  integer operator<<(uint64_t shift){
    if (!*this || !shift)
      return *this;
    std::deque <uint8_t> out = value;
    for(uint64_t i = 0; i < (shift >> 3); i++)
      out.push_back(0);
    shift &= 7;
    if (shift){
      out.push_back(0);
      return integer(SIGN, out) >> (8 - shift);
    }
    return integer(SIGN, out);
  }

  integer operator<<(integer shift){
    integer out = *this;
    for(integer i = 0; i < (shift >> 3); i++)
       out.value.push_back(0);
    return out << (uint64_t) (shift & 7);
  }

  // right bit shift. sign is maintained
  integer operator>>(uint64_t shift){
    if (shift >= bits())
      return integer(0);
    std::deque <uint8_t> out = value;
    for(uint64_t i = 0; i < (shift >> 3); i++)
      out.pop_back();
    shift &= 7;
    if (shift){
      std::deque <uint8_t> v;
      for(unsigned int i = out.size() - 1; i != 0; i--)
        v.push_front(((out[i] >> shift) | (out[i - 1] << (8 - shift))) & 0xff);
      v.push_front(out[0] >> shift);
      out = v;
    }
    return integer(SIGN, out);
  }

  integer operator>>(integer shift){
    integer out = *this;
    for(integer i = 0; i < (shift >> 3); i++)
       out.value.pop_back();
    return out >> (uint64_t) (shift & 7);
  }

  // Logical Operators
  bool operator!(){
    return !(bool) *this;
  }

  bool operator&&(integer rhs){
    return (bool) *this && (bool) rhs;
  }

  bool operator||(integer rhs){
    return ((bool) *this) || (bool) rhs;
  }

  // Comparison Operators
  bool operator==(integer rhs){
    return ((SIGN == rhs.SIGN) && (value == rhs.value));
  }

  bool operator!=(integer rhs){
    return !(*this == rhs);
  }

private:
  // operator> not considering signs
  bool gt(integer & lhs, integer & rhs){
    if (lhs.value.size() > rhs.value.size())
      return true;
    if (lhs.value.size() < rhs.value.size())
      return false;
    if (lhs.value == rhs.value)
      return false;
    for(unsigned int i = 0; i < lhs.value.size(); i++)
      if (lhs.value[i] != rhs.value[i])
        return lhs.value[i] > rhs.value[i];
    return false;
  }

public:
  bool operator>(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);
  }

  bool operator>=(integer rhs){
    return ((*this > rhs) | (*this == rhs));
  }

private:
  // operator< not considering signs
  bool lt(integer & lhs, integer & rhs){
    if (lhs.value.size() < rhs.value.size())
      return true;
    if (lhs.value.size() > rhs.value.size())
      return false;
    if (lhs.value == rhs.value)
      return false;
    for(unsigned int i = 0; i < lhs.value.size(); i++)
      if (lhs.value[i] != rhs.value[i])
        return lhs.value[i] < rhs.value[i];
    return false;
  }

public:
  bool operator<(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);
  }

  bool operator<=(integer rhs){
    return ((*this < rhs) | (*this == rhs));
  }

private:
  // Arithmetic Operators
  integer add(integer & lhs, integer & rhs){
    std::deque <uint8_t> out;
    std::deque <uint8_t>::reverse_iterator i = lhs.value.rbegin(), j = rhs.value.rbegin();
    bool carry = false;
    uint16_t sum;
    for(; ((i != lhs.value.rend()) && (j != rhs.value.rend())); i++, j++){
      sum = *i + *j + carry;
      out.push_front(sum);
      carry = (sum > 255);
    }
    for(; i != lhs.value.rend(); i++){
      sum = *i + carry;
      out.push_front(sum);
      carry = (sum > 255);
    }
    for(; j != rhs.value.rend(); j++){
      sum = *j + carry;
      out.push_front(sum);
      carry = (sum > 255);
    }
    if (carry)
      out.push_front(1);
    return integer(false, out);
  }

public:
  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;
      }
    }
    else{ //if (eq(out, rhs)){
      if ((SIGN & rhs.SIGN) | (!SIGN & !rhs.SIGN))
        return integer(0);
      //if ((SIGN & !rhs.SIGN) | (!SIGN & rhs.SIGN))
      out = out << 1;
      out.SIGN = SIGN;
    }
    if (!out.value.size())                  // if the value became 0
      out.SIGN = false;
    return out;
  }

  integer operator+=(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
    unsigned int lsize = lhs.value.size() - 1;
    unsigned int rsize = rhs.value.size() - 1;
    for(unsigned int x = 0; x < rsize + 1; x++){
      // if rhs digit is smaller than lhs digit, subtract
      if (rhs.value[rsize - x] <= lhs.value[lsize - x])
        lhs.value[lsize - x] -= rhs.value[rsize - x];
      else{// carry
        unsigned int y = lsize - x - 1;
        while (!lhs.value[y])
          y--;
        lhs.value[y]--;
        y++;
        for(; y < lsize - x; y++)
          lhs.value[y] = 0xff;
        lhs.value[y] = ((uint16_t) lhs.value[y]) + 256 - rhs.value[rsize - x];
      }
    }
    return lhs;
  }

    // implemented but erased here and commented out in code
//    // Two's Complement Subtraction

  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:
  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;
    }
    if (!out.value.size())                    // if the value became 0
      out.SIGN = false;
    clean();
    return out;
  }

  integer operator-=(integer rhs){
    *this = *this - rhs;
    return *this;
  }

private:
// implemented but erased here and commented out in code:
//    // Peasant Multiplication
//    // Recurseive Peasant Algorithm
//    // Recursive Multiplication
//    // Karatsuba Algorithm O(n^log2(3) = n ^ 1.585)


  // Long multiplication
  integer long_mult(integer lhs, integer rhs){
    unsigned int zeros = 0;
    integer row, out = 0;
    for(std::deque <uint8_t>::reverse_iterator i = lhs.value.rbegin(); i != lhs.value.rend(); i++){
      row.value = std::deque <uint8_t>(zeros++, 0); // zeros on the right hand side
      uint8_t carry = 0;
      for(std::deque <uint8_t>::reverse_iterator j = rhs.value.rbegin(); j != rhs.value.rend(); j++){
        uint16_t prod = (uint16_t(*i) * uint16_t(*j)) + carry;// multiply through
        row.value.push_front(prod & 0xff);
        carry = prod >> 8;
      }
      if (carry)
        row.value.push_front(carry);
      out = add(out, row);
    }
    return out;
  }

public:
  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;
    if (!out.value.size())                    // if the value became 0
      out.SIGN = false;
    return out;
  }

  integer operator*=(integer rhs){
    *this = *this * rhs;
    return *this;
  }

private:
// implemented but erased here and commented out in code:
//    // Long Division returning both quotient and remainder
//    // Recursive Division that returns both the quotient and remainder

  // Non-Recursive version of above algorithm
  std::deque <integer> divmod(integer & lhs, integer & rhs){
    std::deque <integer> qr;
    qr.push_back(0);
    qr.push_back(0);
    for(unsigned int x = lhs.bits(); x > 0; x--){
      qr[0] <<= 1;
      qr[1] <<= 1;
      if (lhs[x - 1])
        qr[1]++;
      if (qr[1] >= rhs){
        qr[1] -=rhs;
        qr[0]++;
      }
    }
    return qr;
  }

  // division ignoring signs
    std::deque <integer> dm(integer & lhs, integer & rhs){
        if (!rhs){               // divide by 0 error
            std::cerr << "Error: division or modulus by zero" << std::endl;
            exit(1);
        }
        std::deque <integer> out;
        if (rhs == 1){            // divide by 1 check
      out.push_back(lhs);
      out.push_back(0);
      return out;
        }
        if (lhs == rhs){          // divide by same value check
      out.push_back(1);
      out.push_back(0);
      return out;
        }
        if (!lhs){              // 0 / rhs check
      out.push_back(0);
      out.push_back(0);
      return out;
        }
        if (lt(lhs, rhs)){          // lhs < rhs check
      out.push_back(0);
      out.push_back(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.push_back(lhs >> s);
        out.push_back(lhs - (out[0] << s));
        return out;
      }
        }
    ////////////////////////////////////////////////
//      return long_div(lhs, rhs);
//      return recursive_divmod(lhs, rhs);
    return divmod(lhs, rhs);
    }

public:
  integer operator/(integer rhs){
    bool s = SIGN ^ rhs.SIGN;
    integer lhs = *this;
    lhs.SIGN = false;
    rhs.SIGN = false;
    integer out = dm(lhs, rhs)[0];
    out.SIGN = s;
    if (!out.value.size())                    // if the value became 0
      out.SIGN = false;
    return out;
  }

  integer operator/=(integer rhs){
    *this = *this / rhs;
    return *this;
  }

  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)[1];
    if (out.value.size())
      if (s1 == s2)
        out.SIGN = s1;
      else{
        out = rhs - out;
        out.SIGN = s2;
      }
    else //if (!out.value.size())                    // if the value became 0
      out.SIGN = false;
    return out;
  }

  integer operator%=(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+(){
    return *this;
  }

  // Flip Sign
  integer operator-(){
    integer out = *this;
    if (out.value.size())
      out.SIGN ^= true;
    return out;
  }

  // get private values
  bool sign(){
    return SIGN;          // false = pos, true = neg
  }

  unsigned int bits(){
    if (!value.size())
      return 0;
    unsigned int out = value.size() << 3;
    uint8_t mask = 128;
    while (!(value[0] & mask)){
      out--;
      mask >>= 1;
    }
    return out;
  }

  unsigned int bytes(){
    return value.size();
  }

  std::deque <uint8_t> data(){
    return value;
  }

  // Miscellaneous Functions
  integer twos_complement(unsigned int b = 0){
    std::deque <uint8_t> out = value;
    for(unsigned int i = 1; i < out.size(); i++)
      out[i] ^= 0xff;
    uint8_t mask = 128;
    while (!(out[0] & mask))
      mask >>= 1;
    integer top = integer(1) << ((uint64_t) (out.size() - 1) << 3);
    while (mask){
      out[0] ^= mask;
      mask >>= 1;
      top <<= 1;
    }
    integer OUT(SIGN, out);
    while (b){
      OUT ^= top;
      top <<= 1;
      b--;
    }
    return OUT + 1;
  }

  integer abs(){
    integer out = *this;
    out.SIGN = false;
    return out;
  }

  void fill(uint64_t b){
    // fills an integer with 1s
    value = std::deque <uint8_t>(b >> 3, 255);
    if (b & 7)
      value.push_front((1 << (b & 7)) - 1);
  }

  bool operator[](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 value, return 0
      return 0;
    return (value[value.size() - (b >> 3) - 1] >> (b & 7)) & 1;
  }

  // Output value as a string in bases 2 to 16, and 256
  std::string str(integer base = 10, unsigned int length = 0){
    std::string out = "";
    if (base == 256){
      if (!value.size())
        out = std::string(1, 0);
      for(unsigned int x = 0; x < value.size(); x++)
        out += std::string(1, value[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))  // if base outside of 2 <= base <= 16
        base = 10;          // set to default value of 10
      integer rhs = *this;
      static const std::string B16 = "0123456789abcdef";
      std::deque <integer> qr;
      do{
        qr = dm(rhs, base);
        out = B16[qr[1]] + out;
        rhs = qr[0];
      } 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 T as first arguemnt
// erased because they were taking up too much space

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

EDIT: Forgot to mention: This should be compiled with C++11 enabled

Link to working code: http://ideone.com/mYDLp

At a quick glance, operator bool() makes me uneasy. But since this is pretty large, I tried compiling and running it. I did find that evaluating (integer && anything) causes a stack overflow. — ROBOKiTTY, Jul 8 '12 at 3:24
ok. fixed that i think. i havent updated this post or the site yet, though — calccrypto, Jul 8 '12 at 3:55
found a bug with the typecase operators that i mistakenly updated incorrectly — calccrypto, Jul 8 '12 at 5:06
@calccrypto sorry, but you need to post the up-to-date version inline (faq). — codesparkle♦, Jul 8 '12 at 10:11
@calccrypto: Never mind, my compiler didn't like the lack of an #include <string>. And I think you ought to call it VeryLongInteger rather than just integer. — ROBOKiTTY, Jul 9 '12 at 1:25

Corbin · Accepted Answer · 2012-07-09 06:36:52Z

I'm not familiar with the algorithms used (or any in the same category for that matter), but I do have a few notes on style/practices.

std::cerr/exit inside of a class

If a value is unexpected or invalid for a parameter, exceptions should be used, not outputting an error and then killing the program. What if the programmer wants to be able to recover from such an error? For example, what if you had a program that was taking hex input from users and the user provided an invalid character that ended up getting passed into integer(std::string str, int base). You probably would not want the program to die in the situation.

I would do something like:

else {
    throw std::runtime_error("Error: Character not between 'a' and 'f' found");
}

Same concept applies in the dm method.

SIGN

I'm guessing this is named in all uppercase because of the conflict with the sign method. I would consider using _sign or something similar instead. Everywhere I look in the code, the all caps property jumps out at me unnecessarily.

Also, I might consider renaming sign to isPositive. true and false conveys a different meaning to me than I except for a sign. I guess the use of a high and low bit for sign is by far standard enough for people to understand this behavior though.

integer

Extremely minor thing, and 100% opinion, but I would consider renaming the class.

integer makes me think of a standard int more so than an arbitrary length integer.

typedefs

I would use typedefs for a few things both to increase readability and lesser so maintainability.

For example, I might alias std::deque<uint8_t> as value_type or something similar, and would use sign_type instead of bool.

clean

Very minor, but I would consider renaming this compact or trim.

Also, I would consider using empty instead of size since empty is constant complexity for all containers and size is only constant for some (though it is of course constant for deque).

initializer lists

It's more idiomatic to use initializer lists when possible (there's other benefits too, but in the case of your code, they're fairly insignificant).

For example:

integer() : SIGN(false) { }

integer(const integer & rhs) : SIGN(rhs.sign), value(rhs.value) {
    clean();
}

integer(std::deque <uint8_t> & val) : SIGN(false), value(val) {
    clean();
}

const correctness

There's a few places where const correctness is in place, but there's also some places where things could be const but are not.

For example:

integer(bool s, const std::deque <uint8_t> & val) {
    value = val;
    SIGN = value.size() ? s : false;
    clean();
}

type casting

I wouldn't provide the type casts (bool, uint8_t, etc). These only make sense if there is a meaningful cast to them, and in my opinion there is not. An arbitrary length integer is not meant to be cut into a smaller piece. I might expose a way to extract this data, but I would not do it via casts. (For example, a method to get the bottom N bytes or something.)

The ability to do this casting implicity especially concerns me. Imagine a method with signature void f(uint16_t). An integer being passed to by mistake could have some very odd implications.

cstdint

Not familiar enough with the C++ standard to comment on this for sure, but I suspect that you should be including cstdint explicity in integer.h rather than counting on a different header to pull it in.

integer(std::string str, int base)

This method has a few things going on.

I would try to avoid copying the string. That will of course require changing the body of the constructor.

base should have an unsigned type. A negative base has no meaning.

str shadows the method called str. In this situation, it doesn't matter, but shadowing should typically be avoided. (For what it's worth, I always compile with -Wshadow.)

match types where possible

In situations like:

for (unsigned int x = 0; x < str.size(); x++)

You should consider using:

for (std::string::size_type x = 0; x < str.size(); x++)

Also, since str.size() isn't changing, you should consider using:

for (std::string::size_type x = 0, s = str.size(); x < s; ++x)

integer(std::string str, int base) suggestion

I would get rid of the temp and rewrite it to be iterator based. This would end up being a lot more flexible while maintaining the existing functionality (and performance should be either the same, or very, very similar).

template <typename Iterator>
integer(Iterator start, const Iterator& end, uint16_t base)
{
    if (start == end) {
        return;
    }
    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::isupper(*start)) {
                        //A-F
                        *this += (*start - 'A') + 10;
                    } else if (std::isdigit(*start)) {
                        //0-9
                        *this += *start - '0';
                    } else {
                        //a-f
                        *this += (*start - 'a') + 10;
                    }
                } else {
                    throw std::runtime_error("Character not between 'a' and 'f' found");
                }
                ++start;
            }
            break;
        case 256:
            while (start != end) {
                this->value.push_back(*start);
                ++start;
            }
            break;
        default:
            throw std::runtime_error("Unknown base provided (must be 2,8, 10, 16 or 256)");
            break;
    }
}

/**
 *
 * @param val The value the integer should take
 * @param base The base that val is in
 */
integer(const std::string& val, uint16_t base) : integer(val.begin(), val.end(), base)
{ }

An example of how this could be more flexible:

const char* str = "ffff";
integer i(str, str+4, 16);

Or even:

const char* str = "0xffff";
integer i(str+2, str+6, 16);

The performance of this is still potentially bad for large containers. For example, *this = (*this << 3) + (*this << 1) + (*start - '0'); is going to end up doing a lot of extra work.

You could rewrite this to use methods that do not copy instead of operators to have better performance.

add/sub/etc

I would make methods that operate on their own objects instead of other objects. For example, instead of integer add(integer & lhs, integer & rhs) (which should probably be integer add(const integer & lhs, const integer & rhs)), I would have something like:

void add(integer & rhs) {
    //add rhs to this
}

That way you're given a choice of whether or not you want to make a copy. Let's revisit the constructor I talked about for a minute:

*this = (*this << 1) + (*start - '0');

This can be de-prettified into:

this->operator=(this->operator+(this->operator<<(1), *start - '0'));

And this is being run for every character in the string. Binary strings get huge very quickly, so this going to be doing a lot of copying.

Consider instead if there were methods that acted on the actual object:

this->shiftLeft(1);
this->add(*start - '0');

If a copy needed to be made, it of course still could be:

integer copy(*this);
copy.shiftLeft(1);
copy.add(*start - '0');

Note

This is incomplete at the moment. I've ran out of time, and am not sure when I'll be available to revisit this. I do plan on looking through the code more in the future though as I've only had a chance to glance through the entirety and then closely examine a few methods.

UPDATE #1

operator= self assignment

You should always check for self assignment in operator=. It would actually be harmless in your situation assuming that deque didn't choke on it, but it's still good practice:

integer & operator=(integer rhs) {
    if (&rhs != this) {
        value = rhs.value;
        SIGN = rhs.SIGN;
    }
    return *this;
}

UPDATE #2

Potential infinite loop (and undefined behavior) in signed primitive constructors

There's a potential infinite loop in your constructors of signed primitive types.

The fatal mistake is that -x is not well defined when -x is the largest negative number for the type of x.

Concrete example:

integer(int32_t rhs) {
    //assume rhs = -2147483648; //-2^31
    _sign = (rhs < 0);
    if (rhs < 0)
        rhs = -rhs;
        //int32_t is not guaranteed to be able to hold +2147483648
    while (rhs) {
        _value.push_front(rhs & 255);
        rhs >>= 8;
    }
}

To fix it, just use a proper unsigned type when you flip the sign:

integer(int32_t rhs) {
    _sign = (rhs < 0);
    uint32_t mag = _sign ? -rhs : rhs;
    while (mag) {
        _value.push_front(mag & 255);
        mag >>= 8;
    }
}

Be very careful with for loops

When working with primitives or non expressions, it doesn't matter, but when working with performance critical code, you should always remember to use pre-increment and avoid putting non-constant expressions as a for loop's condition.

For example:

for (integer i = 0; i < (shift >> 3); i++)

I would write as: for (integer i = 0, s = shift >> 3; i < s; ++i)

operator++(int) creates a copy whereas operator++() does not.

This can be optimized out, but it is not guaranteed to be.

(The same with the shift >> 3. I could be wrong on this, but since shift is not const, I do not believe that the compiler is required to optimize that.)

flipping a bool

out.SIGN ^= true;

I would use:

out.SIGN = !out.SIGN;

It's sometimes useful to remember that true and false are really just 1 and 0, but using bitwise operators to flip a bool just looks odd.

Comments

I would probably comment a few things. In particular, I would use docblocks for all public methods.

I'm not quite sure what twos_complement does, for example.

const correctness (revisited)

I've already mentioned this, but after looking through the code more indepth, I feel that it needs much more attention.

The basic gist of cost correctness is to default to const and then have something be non-const only when it is going to be mutated. For example, any method that is a getter or in general just doesn't change the state of an object should be const:

type method() const;

Any parameter that is not modified should be a constant reference:

type method(const T&);

(Also, a good reason to default to const is that it's a huge pain to fix const correctness in large code bases. In fact, I tried to fix it in a few places in your code for examples, and even one little change requires fixing basically all of it.)

About the copying, like in integer(std::string str, int base) and operator+(): what about if i want to do inline conversions from strings to integers? should i add an overload for integer(std::string & str, int base)? — calccrypto, Jul 9 '12 at 1:36
@calccrypto Am not sure if I understand your question correctly? I think I understand what you mean by inlining conversions from strings to integers (allowing "100" to be implicitly converted to integer(100)), and I understand what you mean about the copying (the operator<< and operator+ creating copies), but I'm not sure how the two are linked? — Corbin, Jul 9 '12 at 1:39
wont those operators have pass by reference arguments? won't that make inline conversions not work? integer operator+(integer & rhs) -> some integer + integer(f()), where f returns a string — calccrypto, Jul 9 '12 at 1:49
@calccrypto Oh, so you mean if a void add(integer& rhs) method existed, you're afraid that x.add("10") wouldn't be valid? It's actually not valid now as there's no constructor that takes only a string. For that to happen, you'd need a default value for base in the integer (str, base) constructor. — Corbin, Jul 9 '12 at 2:01

Corbin · Answer 2 · 2012-07-10 00:40:00Z

The duplicated constructors and operators have been bugging me, so I have a few suggestions to reduce code repetition.

(Note that about half of them are untested.)

Constructor #1

In C++, it's valid for an integeral type to be implicitly expanded to a larger integeral type.

For example:

void f(int64_t x) { }
void g(uint64_t x) { }
int16_t a = -12;
int64_t b = a; //Completely valid -- no warnings
f(a); //Completely valid -- no warnings
g(a); //Completely valid -- no warnings

If you read that carefully, the g line probably made you go "what?!"

Even weirder:

void f1(int64_t x) { }
void f1(uint64_t x) { }

f1(5); //Error -- int -> uint64_t and int -> int64_t are equally valid conversions

This has two implications (one useful, one that makes me scratch my head as to why C++ did this): * You don't need a different overload for every integeral type -- just the largest one * If signed and unsigned matter, then you actually do need an overload for every integral type

There is, however, the option for templates:

template <typename Numeric>
integer(const Numeric& val)
{

    //Can only be negative if the type is signed and the val is less than 0
    _sign = (std::numeric_limits<Numeric>::is_signed && val < 0);

    //mag will be of type unsigned Numeric
    typename std::make_unsigned<Numeric>::type mag;
    mag = _sign ? -val : val;

    //Could just use 255, but might as well go for generic while we'ere at it
    base256::value_type mask = std::numeric_limits<base256::value_type>::max();

    while (mag) {
        digits.push_front(mag & mask);
        //digits will be the number of digits in whatever the underlying
        //radix is.  (In other words, this will be the number of bits for
        //unsigned integral types.)
        mag >>= std::numeric_limits<base256::value_type>::digits;
    }

}

This looks a little odd at first, but it just uses some template features of C++ to determine the type.

Also, since only numeric types (or types that have specialized the templates themselves) will have make_unsigned and family defined, this constructor can't be accidentally used for a string or double.

Constructor #2

integer(bool s, const base256 & val)

If you flip this around, you can combine it with the constructor above it:

integer(const base256 & val, bool s = false): _sign(s), digits(val){
    trim();
    if (digits.empty()) {
        _sign = false;
    }
}

Constructor #3

    //need at least gcc 4.7 to compile this 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);
    }

Aside from unnecessarily requiring 4.7 (nothing here warrants breaking non-C++11 compatibility), this is wrong.

integer(const std::string & val, uint16_t base) : integer(val.begin(), val.end(), base) {}

And:

integer(const std::string & val, uint16_t base){
    *this = integer(val.begin(), val.end(), base);
}

Do completely different things.

Imagine this code:

integer i("1000", 10);

The first one silently converts this to:

const std::string s = "1000";
integer i(s.begin(), s.end(), 10);

There is no extra work here. There is no un-needed copying or anything of that nature.

Now the second one silently converts to (oversimplifying this a bit by the way):

const std::string s = "1000";
integer temp(s.begin(), s.end(), 10);
integer i(temp);

In other words, temp is copied for no reason.

operator=

The same type of template-use can reduce the number of operator= overloads from 9 to 2. I would refactor the main part of the constructor into a private method and then use that private method in the constructor and operator=:

template <typename Numeric>
void setFromNumeric(const Numeric& val)
{

    digits.clear();

    //Can only be negative if the type is signed and the val is less than 0
    _sign = (std::numeric_limits<Numeric>::is_signed && val < 0);

    //mag will be of type unsigned Numeric
    typename std::make_unsigned<Numeric>::type mag;
    mag = _sign ? -val : val;

    //Could just use 255, but might as well go for generic while we'ere at it
    base256::value_type mask = std::numeric_limits<base256::value_type>::max();

    while (mag) {
        digits.push_front(mag & mask);
        //digits will be the number of digits in whatever the underlying
        //radix is.  (In other words, this will be the number of bits for
        //unsigned integral types.)
        mag >>= std::numeric_limits<base256::value_type>::digits;
    }

}

template <typename Numeric>
integer(const Numeric& val)
{
    setFromNumeric(val);
}

template <typename Numeric>
integer& operator=(const Numeric& val)
{
    setFromNumeric(val);
    return *this;
}

Potential bug

I'm guessing that in operator+:

out = _sign;

Should be:

out._sign = _sign;

operator<<

This one you can heavily reduce without having to use templates. You only need:

integer operator<<(uint64_t shift)

That's the only operator<< that you need since anything smaller than a uint64_t will be upcasted to a uint64_t (even signed types).

This same concept applies to operator<<= and so on.

wow so much stuff. Im modifying some of the stuff now. About that constructor needing gcc 4.7. its not that the method isnt in C++11. its that it wasnt implemented in gcc until 4.7: stackoverflow.com/questions/11391108/… — calccrypto, Jul 10 '12 at 1:14
I have a slight problem with your operator=: i cant add booleans anymore, since booleans dont have signs. i have to change all of them to ints, but theres so many of them. — calccrypto, Jul 10 '12 at 1:47
Now i remember why I have so many overloads: when i compile integer, hundreds of warnings appear about ambiguity. i guess i didnt want to see them every time. Also, they take more time to display than compiling the program does — calccrypto, Jul 10 '12 at 1:56
@calccrypto Ah I understood that comment backwards then. Sorry about that. Didn't realize that calling a different constructor was new in C++11. And booleans don't have the numeric_limits defined, though you could use a more specific operator to handle them. As for the ambiguity, there must be something else going on, because nothing about it should be ambiguous. Will look into it in a few hours when I get a chance. — Corbin, Jul 10 '12 at 2:12
@calccrypto Hmm so with the ambiguous >> 3 type stuff, I wonder why that's ambiguous. I guess it can't decide between converting up to a uint64_t or converting to an integer(3)? Anyway, the templated operator= and ctor I provided will give an error at compile time for any non numeric type. Basically a specialization of numeric_limits needs to exist for the type or there will be a compile error. — Corbin, Jul 10 '12 at 23:39

asked	1 year ago
viewed	263 times
active	1 year ago

current community

your communities

more stack exchange communities

Improving a custom integer class 2.0

2 Answers

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ integer or ask your own question.

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

Improving a custom integer class 2.0

2 Answers

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ integer or ask your own question.

Linked

Related

Hot Network Questions