fork download
copy 
  1. /*
  2. integer.h
  3. An Arbitrary Precision Integer Type
  4. by Jason Lee @ calccrypto@yahoo.com
  5.  
  6. With much help from:
  7.     Auston Sterling - Initial debugging and coding help
  8.     Corbin @ Code Review (StackExchange) - wrote a sizeable chunk of code and suggestions
  9.     Keith Nicholas  @ Code Review (StackExchange)
  10.     ROBOKITTY @ Code Review (StackExchange)
  11.     Winston Ewert @ Code Review (StackExchange) - suggested many improvements
  12.  
  13. This is an implementation of an arbitrary precision integer
  14. container. The actual limit of how large the integers can
  15. be is std::deque <uint8_t>().max_size() * 8 bits, which should
  16. be enormous. Most of the basic operators are implemented,
  17. although their outputs might not necessarily be the same output
  18. as a standard version of that operator. Anything involving
  19. pointers and addresses should be taken care of by C++.
  20.  
  21. Data is stored in big endian, so digits[0] is the most
  22. significant byte (MSB), and digits[digits.size() - 1] is the
  23. least significant byte (LSB).
  24.  
  25. Negative digitss are stored as their positive digitss,
  26. with a flag that says the value is negative.
  27.  
  28. NOTE: Build with the newest compiler. Some functions are only
  29.       supported in the latest versions of C++ compilers.
  30.  
  31. NOTE: Base256 strings are assumed to be postive when read into
  32.       integer. Use operator-() to negate the digits.
  33.  
  34. NOTE: Multiple algorithms for subtraction, multiplication, and
  35.       division have been implemented and commented out. They
  36.       should all work, but are there for educational purposes.
  37.       If one is faster than another on different systems, by
  38.       all means change which algorithm is used. Just make sure
  39.       all related functions are changed as well.
  40.  
  41. NOTE: All algorithms operate on positive digitss only. The
  42.       operators deal with the signs.
  43.  
  44. NOTE: Changing the internal representation to a std::string
  45.       makes integer run slower than using a std::deque <uint8_t>
  46. */
  47.  
  48. #include <deque>
  49. #include <iostream>
  50. #include <limits>
  51. #include <stdexcept>
  52.  
  53. #ifndef __INTEGER__
  54. #define __INTEGER__
  55.  
  56. typedef uint32_t                           digit;
  57. typedef uint64_t                          double_digit;
  58.  
  59. typedef std::deque <digit>                base;
  60. typedef std::deque <digit>::size_type     d_size;
  61. typedef std::string::size_type            str_size;
  62.  
  63. const digit NEG1 = -1;
  64. const digit BITS = sizeof(digit) << 3;
  65. const digit HIGH_BIT = 1 << (BITS - 1);
  66.  
  67. class integer{
  68.     private:
  69.         bool _sign;                              // false = positive, true = negative
  70.         base digits;                             // holds the actual digits in base
  71.  
  72.         template <typename Z> void setFromZ(Z val){
  73.             digits.clear();
  74.             _sign = false;
  75.             if (val < 0){
  76.                 _sign = true;
  77.                 val = -val;
  78.             }
  79.             while (val){
  80.                 Z mask = 1;
  81.                 digit d = 0;
  82.                 for(unsigned int x = 0; x < BITS; x++){
  83.                     d += ((val & 1)?mask:0);
  84.                     val >>= 1;
  85.                     mask <<= 1;
  86.                 }
  87.                 digits.push_front(d);
  88.             }
  89.             trim();
  90.         }
  91.  
  92.         void trim(){                             // remove 0 bytes from top of deque to save memory
  93.             while (!digits.empty() && !digits[0])
  94.                 digits.pop_front();
  95.             if (digits.empty())                  // change sign to false if value is zero
  96.                 _sign = false;
  97.         }
  98.  
  99.     public:
  100.         // Constructors
  101.         integer(): _sign(false){}
  102.  
  103.         integer(const bool & b): _sign(false), digits(1, b){
  104.             trim();
  105.         }
  106.  
  107.         template <typename Z> integer(Z val){
  108.             setFromZ(val);
  109.         }
  110.  
  111.         integer(const integer & rhs): _sign(rhs._sign), digits(rhs.digits){
  112.             trim();
  113.         }
  114.  
  115.         integer(base & val, bool s = false): _sign(s), digits(val){
  116.             trim();
  117.         }
  118.  
  119.         // Written by Corbin
  120.         // Slightly modified by me
  121.         template <typename Iterator> integer(Iterator start, const Iterator& end, uint16_t base){
  122.             _sign = false;
  123.             if (start == end)
  124.                 return;
  125.             if (base != 256)            // All base 256 inputs assumed to be positive
  126.                 if (*start == '-'){
  127.                     _sign = true;
  128.                     ++start;
  129.                 }
  130.             switch (base){
  131.                 case 2:
  132.                     while (start != end){
  133.                         *this = (*this << 1) + (*start - '0');
  134.                         ++start;
  135.                     }
  136.                     break;
  137.                 case 8:
  138.                     while (start != end){
  139.                         *this = (*this << 3) + (*start - '0');
  140.                         ++start;
  141.                     }
  142.                     break;
  143.                 case 10:
  144.                     while (start != end){
  145.                         *this = (*this << 3) + (*this << 1) + (*start - '0');
  146.                         ++start;
  147.                     }
  148.                     break;
  149.                 case 16:
  150.                     while (start != end){
  151.                         *this <<= 4;
  152.                         if (std::isxdigit(*start)){
  153.                             if (std::isdigit(*start))
  154.                                 *this += *start - 0x30;                //0-9
  155.                             else if (std::islower(*start))
  156.                                 *this += *start - 0x57;                //a-f
  157.                             else if (std::isupper(*start))
  158.                                 *this += *start - 0x37;                //A-F
  159.                             else
  160.                                 throw std::runtime_error("Character not between 'a' and 'f' found");
  161.                         }
  162.                         ++start;
  163.                     }
  164.                     break;
  165.                 case 256:
  166.                     while (start != end){
  167.                         *this = (*this << 8) + (uint8_t) *start;
  168.                         ++start;
  169.                     }
  170.                     break;
  171.                 default:
  172.                     throw std::runtime_error("Unknown base provided (must be 2,8, 10, 16 or 256)");
  173.                     break;
  174.             }
  175.             trim();
  176.         }
  177.  
  178.         // need at least gcc 4.7 to compile next line, otherwise use uncommented version
  179.         // integer(const std::string & val, uint16_t base): integer(val.begin(), val.end(), base){}
  180.         integer(const std::string & val, uint16_t base){
  181.             *this = integer(val.begin(), val.end(), base);
  182.         }
  183.  
  184.         //  RHS input args only
  185.  
  186.         // Assignment Operator
  187.         integer & operator=(const bool & b){
  188.             digits.clear();
  189.             digits.push_back(b);
  190.             _sign = false;
  191.             return *this;
  192.         }
  193.  
  194.         template <typename Z>
  195.         integer& operator=(const Z & val){
  196.             setFromZ(val);
  197.             return *this;
  198.         }
  199.  
  200.         // Typecast Operators
  201.         operator bool(){
  202.             return !digits.empty();
  203.         }
  204.  
  205.         operator char(){
  206.             if (digits.empty())
  207.                 return 0;
  208.             return (char) (digits.back() & 255);
  209.         }
  210.  
  211.         operator uint8_t(){
  212.             if (digits.empty())
  213.                 return 0;
  214.             return digits.back() & 255;
  215.         }
  216.  
  217.         operator uint16_t(){
  218.             uint16_t out = 0;
  219.             for(uint8_t x = 0; x < std::min(digits.size(), 2 / sizeof(digit)); x++)
  220.                 out += (uint16_t) digits[digits.size() - x - 1] << (x * BITS);
  221.             return out;
  222.         }
  223.  
  224.         operator uint32_t(){
  225.             uint32_t out = 0;
  226.             for(uint8_t x = 0; x < std::min(digits.size(), 4 / sizeof(digit)); x++)
  227.                 out += (uint32_t) digits[digits.size() - x - 1] << (x * BITS);
  228.             return out;
  229.         }
  230.  
  231.         operator uint64_t(){
  232.             uint64_t out = 0;
  233.             for(uint8_t x = 0; x < std::min(digits.size(), 8 / sizeof(digit)); x++)
  234.                 out += (uint64_t) digits[digits.size() - x - 1] << (x * BITS);
  235.             return out;
  236.         }
  237.  
  238.         operator int8_t(){
  239.             if (digits.empty())
  240.                 return 0;
  241.             int8_t out = digits.back() & 255;
  242.             if (_sign)
  243.                 out = -out;
  244.             return out;
  245.         }
  246.  
  247.         operator int16_t(){
  248.             int16_t out = 0;
  249.             for(uint8_t x = 0; x < std::min(digits.size(), 2 / sizeof(digit)); x++)
  250.                 out += (int16_t) digits[digits.size() - x - 1] << (x * BITS);
  251.             if (_sign)
  252.                 out = -out;
  253.             return out;
  254.         }
  255.  
  256.         operator int32_t(){
  257.             int32_t out = 0;
  258.             for(uint8_t x = 0; x < std::min(digits.size(), 4 / sizeof(digit)); x++)
  259.                 out += (int32_t) digits[digits.size() - x - 1] << (x * BITS);
  260.             if (_sign)
  261.                 out = -out;
  262.             return out;
  263.         }
  264.  
  265.         operator int64_t(){
  266.             int64_t out = 0;
  267.             for(uint8_t x = 0; x < std::min(digits.size(), 8 / sizeof(digit)); x++)
  268.                 out += (int64_t) digits[digits.size() - x - 1] << (x * BITS);
  269.             if (_sign)
  270.                 out = -out;
  271.             return out;
  272.         }
  273.  
  274.         // Bitwise Operators
  275.         template <typename Z> integer operator&(const Z & rhs){
  276.             return *this & integer(rhs);
  277.         }
  278.  
  279.         integer operator&(integer rhs){
  280.             base out;
  281.             for(base::reverse_iterator i = digits.rbegin(), j = rhs.digits.rbegin(); (i != digits.rend()) && (j != rhs.digits.rend()); i++, j++)
  282.                 out.push_front(*i & *j);
  283.             return integer(out, _sign & rhs._sign);
  284.         }
  285.  
  286.         template <typename Z> integer operator|(const Z & rhs){
  287.             return *this | integer(rhs);
  288.         }
  289.  
  290.         integer operator|(integer rhs){
  291.             base out;
  292.             base::reverse_iterator i = digits.rbegin(), j = rhs.digits.rbegin();
  293.             for(; (i != digits.rend()) && (j != rhs.digits.rend()); i++, j++)
  294.                 out.push_front(*i | *j);
  295.             while (i != digits.rend())
  296.                 out.push_front(*i++);
  297.             while (j != rhs.digits.rend())
  298.                 out.push_front(*j++);
  299.             return integer(out, _sign | rhs._sign);
  300.         }
  301.  
  302.         template <typename Z> integer operator^(const Z & rhs){
  303.             return *this ^ integer(rhs);
  304.         }
  305.  
  306.         integer operator^(integer rhs){
  307.             base out;
  308.             base::reverse_iterator i = digits.rbegin(), j = rhs.digits.rbegin();
  309.             for(; (i != digits.rend()) && (j != rhs.digits.rend()); i++, j++)
  310.                 out.push_front(*i ^ *j);
  311.             while (i != digits.rend())
  312.                 out.push_front(*i++);
  313.             while (j != rhs.digits.rend())
  314.                 out.push_front(*j++);
  315.             return integer(out, _sign ^ rhs._sign);
  316.         }
  317.  
  318.         template <typename Z> integer operator&=(const Z & rhs){
  319.             *this = *this & rhs;
  320.             return *this;
  321.         }
  322.  
  323.         integer operator&=(const integer & rhs){
  324.             *this = *this & rhs;
  325.             return *this;
  326.         }
  327.  
  328.         template <typename Z> integer operator|=(const Z & rhs){
  329.             *this = *this | rhs;
  330.             return *this;
  331.         }
  332.  
  333.         integer operator|=(const integer & rhs){
  334.             *this = *this | rhs;
  335.             return *this;
  336.         }
  337.  
  338.         template <typename Z> integer operator^=(const Z & rhs){
  339.             *this = *this ^ rhs;
  340.             return *this;
  341.         }
  342.  
  343.         integer operator^=(const integer & rhs){
  344.             *this = *this ^ rhs;
  345.             return *this;
  346.         }
  347.  
  348.         integer operator~(){
  349.             base out = digits;
  350.             for(d_size i = 1; i < out.size(); i++)
  351.                 out[i] ^= NEG1;
  352.             digit mask = HIGH_BIT;
  353.             while (!(out[0] & mask))
  354.                 mask >>= 1;
  355.             while (mask){
  356.                 out[0] ^= mask;
  357.                 mask >>= 1;
  358.             }
  359.             return integer(out, _sign);
  360.         }
  361.  
  362.         // Bit Shift Operators
  363.         template <typename Z> integer operator<<(const Z & shift){
  364.             return *this << ((uint64_t) shift);
  365.         }
  366.  
  367.         // left bit shift. sign is maintained
  368.         integer operator<<(uint64_t shift){
  369.             if (!*this || !shift)
  370.                 return *this;
  371.             base out = digits;
  372.             for(uint64_t i = 0; i < (shift / BITS); i++)
  373.                 out.push_back(0);
  374.             shift %= BITS;
  375.             if (shift){
  376.                 out.push_back(0);
  377.                 return integer(out, _sign) >> (BITS - shift);
  378.             }
  379.             return integer(out, _sign);
  380.         }
  381.  
  382.         integer operator<<(integer shift){
  383.             integer out = *this;
  384.             for(integer i = 0, s = shift / BITS; i < s; ++i)
  385.                out.digits.push_back(0);
  386.             return out << (uint64_t) (shift % BITS);
  387.         }
  388.  
  389.         template <typename Z> integer operator>>(const Z & shift){
  390.             return *this >> ((uint64_t) shift);
  391.         }
  392.  
  393.         // right bit shift. sign is maintained
  394.         integer operator>>(uint64_t shift){
  395.             if (shift >= bits())
  396.                 return integer(0);
  397.             base out = digits;
  398.             for(uint64_t i = 0; i < (shift / BITS); i++)
  399.                 out.pop_back();
  400.             shift %= BITS;
  401.             if (shift){
  402.                 base v;
  403.                 for(d_size i = out.size() - 1; i != 0; i--)
  404.                     v.push_front(((out[i] >> shift) | (out[i - 1] << (BITS - shift))) & NEG1);
  405.                 v.push_front(out[0] >> shift);
  406.                 out = v;
  407.             }
  408.             return integer(out, _sign);
  409.         }
  410.  
  411.         integer operator>>(integer shift){
  412.             integer out = *this;
  413.             for(integer i = 0, s = shift / BITS; i < s; ++i)
  414.                out.digits.pop_back();
  415.             return out >> (uint64_t) (shift % BITS);
  416.         }
  417.  
  418.         template <typename Z> integer operator<<=(const Z & shift){
  419.             *this = *this << shift;
  420.             return *this;
  421.         }
  422.  
  423.         integer operator<<=(const integer & shift){
  424.             *this = *this << shift;
  425.             return *this;
  426.         }
  427.  
  428.         template <typename Z> integer operator>>=(const Z & shift){
  429.             *this = *this >> shift;
  430.             return *this;
  431.         }
  432.  
  433.         integer operator>>=(const integer & shift){
  434.             *this = *this >> shift;
  435.             return *this;
  436.         }
  437.  
  438.         // Logical Operators
  439.         bool operator!(){
  440.             return !((bool) *this);
  441.         }
  442.  
  443.         template <typename Z> bool operator&&(const Z & rhs){
  444.             return (bool) *this && (bool) rhs;
  445.         }
  446.  
  447.         bool operator&&(integer rhs){
  448.             return (bool) *this && (bool) rhs;
  449.         }
  450.  
  451.         template <typename Z> bool operator||(const Z & rhs){
  452.             return ((bool) *this) || (bool) rhs;
  453.         }
  454.  
  455.         bool operator||(integer rhs){
  456.             return ((bool) *this) || (bool) rhs;
  457.         }
  458.  
  459.         // Comparison Operators
  460.         template <typename Z> bool operator==(const Z & rhs){
  461.             return (*this == integer(rhs));
  462.         }
  463.  
  464.         bool operator==(const integer & rhs){
  465.             return ((_sign == rhs._sign) && (digits == rhs.digits));
  466.         }
  467.  
  468.         template <typename Z> bool operator!=(const Z & rhs){
  469.             return !(*this == integer(rhs));
  470.         }
  471.  
  472.         bool operator!=(const integer & rhs){
  473.             return !(*this == rhs);
  474.         }
  475.  
  476.     private:
  477.         // operator> not considering signs
  478.         bool gt(const integer & lhs, const integer & rhs){
  479.             if (lhs.digits.size() > rhs.digits.size())
  480.                 return true;
  481.             if (lhs.digits.size() < rhs.digits.size())
  482.                 return false;
  483.             if (lhs.digits == rhs.digits)
  484.                 return false;
  485.             for(d_size i = 0; i < lhs.digits.size(); i++)
  486.                 if (lhs.digits[i] != rhs.digits[i])
  487.                     return lhs.digits[i] > rhs.digits[i];
  488.             return false;
  489.         }
  490.  
  491.     public:
  492.         template <typename Z> bool operator>(const Z & rhs){
  493.             return (*this > integer(rhs));
  494.         }
  495.  
  496.         bool operator>(const integer & rhs){
  497.             if (_sign & !rhs._sign)               // - > +
  498.                 return false;
  499.             else if (!_sign & rhs._sign)          // + > -
  500.                 return true;
  501.             else if (_sign & rhs._sign)           // - > -
  502.                 return !gt(*this, rhs);
  503. //            else (!_sign & !rhs._sign)          // + > +
  504.             return gt(*this, rhs);
  505.         }
  506.  
  507.         template <typename Z> bool operator>=(const Z & rhs){
  508.             return ((*this > rhs) | (*this == rhs));
  509.         }
  510.  
  511.         bool operator>=(const integer & rhs){
  512.             return ((*this > rhs) | (*this == rhs));
  513.         }
  514.  
  515.     private:
  516.         // operator< not considering signs
  517.         bool lt(const integer & lhs, const integer & rhs){
  518.             if (lhs.digits.size() < rhs.digits.size())
  519.                 return true;
  520.             if (lhs.digits.size() > rhs.digits.size())
  521.                 return false;
  522.             if (lhs.digits == rhs.digits)
  523.                 return false;
  524.             for(d_size i = 0; i < lhs.digits.size(); i++)
  525.                 if (lhs.digits[i] != rhs.digits[i])
  526.                     return lhs.digits[i] < rhs.digits[i];
  527.             return false;
  528.         }
  529.  
  530.     public:
  531.         template <typename Z> bool operator<(const Z & rhs){
  532.             return (*this < integer(rhs));
  533.         }
  534.  
  535.         bool operator<(const integer & rhs){
  536.             if (_sign & !rhs._sign)                   // - < +
  537.                 return true;
  538.             else if (!_sign & rhs._sign)              // + < -
  539.                 return false;
  540.             else if (_sign & rhs._sign)               // - < -
  541.                 return !lt(*this, rhs);
  542. //            else (!_sign & !rhs._sign)              // + < +
  543.             return lt(*this, rhs);
  544.         }
  545.  
  546.         template <typename Z> bool operator<=(const Z & rhs){
  547.             return ((*this < rhs) | (*this == rhs));
  548.         }
  549.  
  550.         bool operator<=(const integer & rhs){
  551.             return ((*this < rhs) | (*this == rhs));
  552.         }
  553.  
  554.     private:
  555.         // Arithmetic Operators
  556.         integer add(integer & lhs, integer & rhs){
  557.             base out;
  558.             base::reverse_iterator i = lhs.digits.rbegin(), j = rhs.digits.rbegin();
  559.             bool carry = false;
  560.             double_digit sum;
  561.             for(; ((i != lhs.digits.rend()) && (j != rhs.digits.rend())); i++, j++){
  562.                 sum = *i + *j + carry;
  563.                 out.push_front(sum);
  564.                 carry = (sum > NEG1);
  565.             }
  566.             for(; i != lhs.digits.rend(); i++){
  567.                 sum = *i + carry;
  568.                 out.push_front(sum);
  569.                 carry = (sum > NEG1);
  570.             }
  571.             for(; j != rhs.digits.rend(); j++){
  572.                 sum = *j + carry;
  573.                 out.push_front(sum);
  574.                 carry = (sum > NEG1);
  575.             }
  576.             if (carry)
  577.                 out.push_front(1);
  578.             return integer(out);
  579.         }
  580.  
  581.     public:
  582.         template <typename Z> integer operator+(const Z & rhs){
  583.             return *this + integer(rhs);
  584.         }
  585.  
  586.         integer operator+(integer rhs){
  587.             if (!rhs)
  588.                 return *this;
  589.             if (!*this)
  590.                 return rhs;
  591.             integer out = *this;
  592.             if (_sign == rhs._sign){
  593.                 out = add(out, rhs);
  594.                 out._sign = _sign;
  595.             }
  596.             else if (gt(out, rhs)){
  597.                 if ((!_sign & rhs._sign) | (_sign & !rhs._sign))         // + + -    - + +
  598.                     out = sub(out, rhs);
  599.                 if ((!_sign & !rhs._sign) | (_sign & rhs._sign))         // + + +    - + -
  600.                     out = add(out, rhs);
  601.                 out._sign = _sign;
  602.             }
  603.             else if (lt(out, rhs)){
  604.                 if ((!_sign & rhs._sign) | (_sign & !rhs._sign)){        // + + -    - + +
  605.                     out = sub(rhs, out);
  606.                     out._sign = !_sign;
  607.                 }
  608.                 if ((_sign & rhs._sign) | (!_sign & !rhs._sign)){        // + + +    - + -
  609.                     out = add(rhs, out);
  610.                     out._sign = _sign;
  611.                 }
  612.             }
  613.             else{ //if (eq(out, rhs)){
  614.                 if ((_sign & rhs._sign) | (!_sign & !rhs._sign))
  615.                     return integer(0);
  616.                 //if ((_sign & !rhs._sign) | (!_sign & rhs._sign))
  617.                 out <<= 1;
  618.                 out._sign = _sign;
  619.             }
  620.             out.trim();
  621.             return out;
  622.         }
  623.  
  624.         template <typename Z> integer operator+=(const Z & rhs){
  625.             *this = *this + rhs;
  626.             return *this;
  627.         }
  628.  
  629.         integer operator+=(const integer & rhs){
  630.             *this = *this + rhs;
  631.             return *this;
  632.         }
  633.  
  634.     private:
  635.         // Subtraction as done by hand
  636.         integer long_sub(integer & lhs, integer & rhs){
  637.             // rhs always smaller than lhs
  638.             d_size lsize = lhs.digits.size() - 1;
  639.             d_size rsize = rhs.digits.size() - 1;
  640.             for(d_size x = 0; x < rsize + 1; x++){
  641.                 // if rhs digit is smaller than lhs digit, subtract
  642.                 if (rhs.digits[rsize - x] <= lhs.digits[lsize - x])
  643.                     lhs.digits[lsize - x] -= rhs.digits[rsize - x];
  644.                 else{// carry
  645.                     d_size y = lsize - x - 1;
  646.                     while (!lhs.digits[y])
  647.                         y--;
  648.                     lhs.digits[y]--;
  649.                     y++;
  650.                     for(; y < lsize - x; y++)
  651.                         lhs.digits[y] = NEG1;
  652.                     lhs.digits[y] = ((double_digit) lhs.digits[y]) + ((uint64_t) 1 << BITS) - rhs.digits[rsize - x];
  653.                 }
  654.             }
  655.             return lhs;
  656.         }
  657.  
  658. //        // Two's Complement Subtraction
  659. //        integer two_comp_sub(const integer & lhs, integer & rhs){
  660. //            rhs = rhs.twos_complement(lhs.bits());
  661. //            return add(lhs, rhs) & (~(integer(1) << lhs.bits()));   // Flip bits to get max of 1 << x
  662. //        }
  663.  
  664.         integer sub(integer & lhs, integer & rhs){
  665.             if (!rhs)
  666.                 return lhs;
  667.             if (!lhs)
  668.                 return -rhs;
  669.             if (lhs == rhs)
  670.                 return 0;
  671.             return long_sub(lhs, rhs);
  672. //            return two_comp_sub(lhs, rhs);
  673.         }
  674.  
  675.     public:
  676.         template <typename Z> integer  operator-(const Z & rhs){
  677.             return *this - integer(rhs);
  678.         }
  679.  
  680.         integer operator-(integer rhs){
  681.             integer out = *this;
  682.             if (gt(out, rhs)){
  683.                 if ((!_sign & rhs._sign) | (_sign & !rhs._sign))             // + - -         - - +
  684.                     out = add(out, rhs);
  685.                 if ((!_sign & !rhs._sign) | (_sign & rhs._sign))             // + - +         - - -
  686.                     out = sub(out, rhs);
  687.                 out._sign = _sign;
  688.             }
  689.             else if (lt(out, rhs)){
  690.                 if ((!_sign & rhs._sign) | (_sign & !rhs._sign)){            // + - -         - - +
  691.                     out = add(out, rhs);
  692.                     out._sign = _sign;
  693.                 }
  694.                 if ((_sign & rhs._sign) | (!_sign & !rhs._sign)){            // + - +         - - -
  695.                     out = sub(rhs, out);
  696.                     out._sign = !_sign;
  697.                 }
  698.             }
  699.             else{ //if (eq(out, rhs)){
  700.                 if ((_sign & rhs._sign) | (!_sign & !rhs._sign))
  701.                     return integer(0);
  702.                 //if ((_sign & !rhs._sign) | (!_sign & rhs._sign))
  703.                 out <<= 1;
  704.                 out._sign = _sign;
  705.             }
  706.             out.trim();
  707.             return out;
  708.         }
  709.  
  710.         template <typename Z> integer operator-=(const Z & rhs){
  711.             *this = *this - rhs;
  712.             return *this;
  713.         }
  714.  
  715.         integer operator-=(const integer & rhs){
  716.             *this = *this - rhs;
  717.             return *this;
  718.         }
  719.  
  720.     private:
  721. //        // Peasant Multiplication
  722. //        integer peasant(integer lhs, integer rhs){
  723. //            integer SUM = 0;
  724. //            for(d_size x = 0; x < lhs.bits(); x++){
  725. //                if (lhs[x])
  726. //                    SUM += rhs;
  727. //                rhs <<= 1;
  728. //            }
  729. //            return SUM;
  730. //        }
  731.  
  732. //        // Recurseive Peasant Algorithm
  733. //        integer recursive_peasant(integer lhs, integer rhs){
  734. //            if (!rhs)
  735. //                return 0;
  736. //            if (rhs & 1)
  737. //                return lhs + recursive_peasant(lhs << 1, rhs >> 1);
  738. //            return recursive_peasant(lhs << 1, rhs >> 1);
  739. //        }
  740.  
  741. //        // Recursive Multiplication
  742. //        integer recursive_mult(integer lhs, integer rhs){
  743. //            if (!rhs)
  744. //                return 0;
  745. //            integer z = recursive_mult(lhs, rhs >> 1);
  746. //            if (!(rhs & 1))
  747. //                return z << 1;
  748. //            return lhs + (z << 1);
  749. //        }
  750.  
  751. //        // Karatsuba Algorithm O(n^log2(3) = n ^ 1.585)
  752. //        // Thanks to kjo @ stackoverflow for fixing up my original Karatsuba Algorithm implementation
  753. //        // which i then converted to C++ and made a few changes
  754. //        // http://stackoverflow.com/questions/7058838/karatsuba-algorithm-too-much-recursion
  755. //        integer karatsuba(integer lhs, integer rhs, integer bm = 0x1000000U){
  756. //            // b is base = 256
  757. //            // m is chars = 4
  758. //            // bm is max digits = b ^ m
  759. //
  760. //            if ((lhs <= bm) | (rhs <= bm))
  761. //                return peasant(lhs, rhs);
  762. //
  763. //            std::pair <integer, integer> x = dm(lhs, bm);
  764. //            std::pair <integer, integer> y = dm(rhs, bm);
  765. //            integer x0 = x.second;
  766. //            integer x1 = x.first;
  767. //            integer y0 = y.second;
  768. //            integer y1 = y.first;
  769. //
  770. //            integer z0 = karatsuba(x0, y0);
  771. //            integer z2 = karatsuba(x1, y1);
  772. //            integer z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0;
  773. //            return karatsuba(karatsuba(z2, bm) + z1, bm) + z0;
  774. //        }
  775.  
  776.         // Long multiplication
  777.         integer long_mult(integer & lhs, integer & rhs){
  778.             unsigned int zeros = 0;
  779.             integer row, out = 0;
  780.             for(base::reverse_iterator i = lhs.digits.rbegin(); i != lhs.digits.rend(); i++){
  781.                 row.digits = base(zeros++, 0); // zeros on the right hand side
  782.                 digit carry = 0;
  783.                 for(base::reverse_iterator j = rhs.digits.rbegin(); j != rhs.digits.rend(); j++){
  784.                     double_digit prod = (double_digit(*i) * double_digit(*j)) + carry;// multiply through
  785.                     row.digits.push_front(prod & NEG1);
  786.                     carry = prod >> BITS;
  787.                 }
  788.                 if (carry)
  789.                     row.digits.push_front(carry);
  790.                 out = add(out, row);
  791.             }
  792.             return out;
  793.         }
  794.  
  795.     public:
  796.         template <typename Z> integer operator*(const Z & rhs){
  797.             return *this * integer(rhs);
  798.         }
  799.  
  800.         integer operator*(integer rhs){
  801.             if ((!*this) || (!rhs))             // if multiplying by 0
  802.                 return 0;
  803.             if (*this == 1)                     // if multiplying by 1
  804.                 return rhs;
  805.             if (rhs == 1)                       // if multiplying by 1
  806.                 return *this;
  807.             bool s = _sign ^ rhs._sign;
  808.             integer out = *this;
  809.             out._sign = false;
  810.             rhs._sign = false;
  811.             if (rhs.abs() == 10){               // if rhs == 10
  812.                 out = (out << 3) + (out << 1);
  813.                 out._sign = s;
  814.                 return out;
  815.             }
  816.             if (out.abs() == 10){               // if lhs == 10
  817.                 out = (rhs << 3) + (rhs << 1);
  818.                 out._sign = s;
  819.                 return out;
  820.             }
  821.             // while lhs is multiple of 2
  822. //            while (!(rhs & 1)){
  823. //                rhs >>= 1;
  824. //                out <<= 1;
  825. //            }
  826. //            out = peasant(out, rhs);
  827. //            out = recursive_peasant(out, rhs);
  828. //            out = recursive_mult(out, rhs);
  829. //            out = karatsuba(out, rhs);
  830.             out = long_mult(out, rhs);
  831.             out._sign = s;
  832.             out.trim();
  833.             return out;
  834.         }
  835.  
  836.         template <typename Z> integer operator*=(const Z & rhs){
  837.             *this = *this * rhs;
  838.             return *this;
  839.         }
  840.  
  841.         integer operator*=(const integer & rhs){
  842.             *this = *this * rhs;
  843.             return *this;
  844.         }
  845.  
  846.     private:
  847. //        // Long Division returning both quotient and remainder
  848. //        std::pair <integer, integer> long_div(const integer & lhs, const integer & rhs){
  849. //            std::pair <integer, integer> qr;
  850. //            qr.first = 0;
  851. //            qr.second = lhs;
  852. //            integer copyd = rhs;
  853. //            integer adder = 1;
  854. //            while (qr.second > copyd){
  855. //                copyd <<= 1;
  856. //                adder <<= 1;
  857. //            }
  858. //            while (qr.second >= rhs){
  859. //                if (qr.second >= copyd){
  860. //                    qr.second -= copyd;
  861. //                    qr.first |= adder;
  862. //                }
  863. //                copyd >>= 1;
  864. //                adder >>= 1;
  865. //            }
  866. //            return qr;
  867. //        }
  868.  
  869. //        // Recursive Division that returns both the quotient and remainder
  870. //        // Recursion took up way too much memory
  871. //        std::pair <integer, integer> recursive_divmod(integer lhs, const integer & rhs){
  872. //            std::pair <integer, integer> qr;
  873. //            if (!lhs){
  874. //                qr.first = 0;
  875. //                qr.second = 0;
  876. //                return qr;
  877. //            }
  878. //            qr = recursive_divmod(lhs >> 1, rhs);
  879. //            qr.first <<= 1;
  880. //            qr.second <<= 1;
  881. //            if (lhs & 1)
  882. //                qr.second++;
  883. //            if (qr.second >= rhs){
  884. //                qr.second -= rhs;
  885. //                qr.first++;
  886. //            }
  887. //            return qr;
  888. //        }
  889.  
  890.         // Non-Recursive version of above algorithm
  891.         std::pair <integer, integer> non_recursive_divmod(integer & lhs, integer & rhs){
  892.             std::pair <integer, integer> qr;
  893.             qr.first = 0;
  894.             qr.second = 0;
  895.             for(size_t x = lhs.bits(); x > 0; x--){
  896.                 qr.first <<= 1;
  897.                 qr.second <<= 1;
  898.                 if (lhs[x - 1])
  899.                     qr.second++;
  900.                 if (qr.second >= rhs){
  901.                     qr.second -= rhs;
  902.                     qr.first++;
  903.                 }
  904.             }
  905.             return qr;
  906.         }
  907.  
  908.         // division ignoring signs
  909.         std::pair <integer, integer> dm(integer & lhs, integer & rhs){
  910.             if (!rhs)                           // divide by 0 error
  911.                 throw std::runtime_error("Error: division or modulus by zero");
  912.             std::pair <integer, integer> out;
  913.             if (rhs == 1){                      // divide by 1 check
  914.                 out.first = lhs;
  915.                 out.second = 0;
  916.                 return out;
  917.             }
  918.             if (lhs == rhs){                    // divide by same digits check
  919.                 out.first = 1;
  920.                 out.second = 0;
  921.                 return out;
  922.             }
  923.             if (!lhs){                          // 0 / rhs check
  924.                 out.first = 0;
  925.                 out.second = 0;
  926.                 return out;
  927.             }
  928.             if (lt(lhs, rhs)){                  // lhs < rhs check
  929.                 out.first = 0;
  930.                 out.second = lhs;
  931.                 return out;
  932.             }
  933.  
  934.             // Check for powers of two /////////////////////
  935.             // Cannot do it the easy way for some reason
  936.             if (!(rhs & 1)){
  937.                 uint64_t s = 0;
  938.                 integer copyd(rhs);
  939.                 while (!(copyd & 1)){
  940.                     copyd >>= 1;
  941.                     s++;
  942.                 }
  943.                 if (copyd == 1){
  944.                     out.first = lhs >> s;
  945.                     out.second = lhs - (out.first << s);
  946.                     return out;
  947.                 }
  948.             }
  949.             ////////////////////////////////////////////////
  950. //            return long_div(lhs, rhs);
  951. //            return recursive_divmod(lhs, rhs);
  952.             return non_recursive_divmod(lhs, rhs);
  953.         }
  954.  
  955.     public:
  956.         template <typename Z> integer operator/(const Z & rhs){
  957.             return *this / integer(rhs);
  958.         }
  959.  
  960.         integer operator/(integer rhs){
  961.             bool s = _sign ^ rhs._sign;
  962.             integer lhs = *this;
  963.             lhs._sign = false;
  964.             rhs._sign = false;
  965.             integer out = dm(lhs, rhs).first;
  966.             out._sign = s;
  967.             out.trim();
  968.             return out;
  969.         }
  970.  
  971.         template <typename Z> integer operator/=(const Z & rhs){
  972.             *this = *this / integer(rhs);
  973.             return *this;
  974.         }
  975.  
  976.         integer operator/=(const integer & rhs){
  977.             *this = *this / rhs;
  978.             return *this;
  979.         }
  980.  
  981.         template <typename Z> integer operator%(const Z & rhs){
  982.             return *this % integer(rhs);
  983.         }
  984.  
  985.         integer operator%(integer rhs){
  986.             bool s1 = _sign;
  987.             bool s2 = rhs._sign;
  988.             integer lhs = *this;
  989.             lhs._sign = false;
  990.             rhs._sign = false;
  991.             integer out = dm(lhs, rhs).second;
  992.             out.trim();
  993.             if (!out.digits.empty()){
  994.                 if (s1 == s2)
  995.                     out._sign = s1;
  996.                 else{
  997.                     out = rhs - out;
  998.                     out._sign = s2;
  999.                 }
  1000.             }
  1001.             return out;
  1002.         }
  1003.  
  1004.         template <typename Z> integer operator%=(const Z & rhs){
  1005.             *this = *this % integer(rhs);
  1006.             return *this;
  1007.         }
  1008.  
  1009.         integer operator%=(const integer & rhs){
  1010.             *this = *this % rhs;
  1011.             return *this;
  1012.         }
  1013.  
  1014.         // Increment Operator
  1015.         integer & operator++(){
  1016.             *this += 1;
  1017.             return *this;
  1018.         }
  1019.  
  1020.         integer operator++(int){
  1021.             integer temp(*this);
  1022.             ++*this;
  1023.             return temp;
  1024.         }
  1025.  
  1026.         // Decrement Operator
  1027.         integer & operator--(){
  1028.             *this -= 1;
  1029.             return *this;
  1030.         }
  1031.  
  1032.         integer operator--(int){
  1033.             integer temp(*this);
  1034.             --*this;
  1035.             return temp;
  1036.         }
  1037.  
  1038.         // Nothing done since promotion doesnt work here
  1039.         integer operator+() const{
  1040.             return *this;
  1041.         }
  1042.  
  1043.         // Flip Sign
  1044.         integer operator-(){
  1045.             integer out = *this;
  1046.             if (out.digits.size())
  1047.                 out._sign = !out._sign;
  1048.             return out;
  1049.         }
  1050.  
  1051.         // get private digitss
  1052.         bool sign() const{
  1053.             return _sign;                    // false = pos, true = neg
  1054.         }
  1055.  
  1056.         size_t bits() const{
  1057.             if (digits.empty())
  1058.                 return 0;
  1059.             unsigned int out = digits.size() * BITS;
  1060.             digit mask = HIGH_BIT;
  1061.             while (!(digits[0] & mask)){
  1062.                 out--;
  1063.                 mask >>= 1;
  1064.             }
  1065.             return out;
  1066.         }
  1067.  
  1068.         unsigned int bytes() const{
  1069.             return digits.size() * sizeof(digits);
  1070.         }
  1071.  
  1072.         base data() const{
  1073.             return digits;
  1074.         }
  1075.  
  1076.         // Miscellaneous Functions
  1077.         integer twos_complement(unsigned int b = 0){
  1078.             base out = digits;
  1079.             for(d_size i = 1; i < out.size(); i++)
  1080.                 out[i] ^= NEG1;
  1081.             digit mask = HIGH_BIT;
  1082.             while (!(out[0] & mask))
  1083.                 mask >>= 1;
  1084.             integer top = integer(1) << ((uint64_t) (out.size() - 1) * BITS);
  1085.             while (mask){
  1086.                 out[0] ^= mask;
  1087.                 mask >>= 1;
  1088.                 top <<= 1;
  1089.             }
  1090.             integer OUT(out, _sign);
  1091.             while (b){
  1092.                 OUT ^= top;
  1093.                 top <<= 1;
  1094.                 b--;
  1095.             }
  1096.             return OUT + 1;
  1097.         }
  1098.  
  1099.         integer abs() const{
  1100.             integer out = *this;
  1101.             out._sign = false;
  1102.             return out;
  1103.         }
  1104.  
  1105.         void fill(const uint64_t & b){
  1106.             // fills an integer with 1s
  1107.             digits = base(b / BITS, NEG1);
  1108.             if (b % BITS)
  1109.                 digits.push_front((1 << (b % BITS)) - 1);
  1110.         }
  1111.  
  1112.         bool operator[](const unsigned int & b){
  1113.             // get bit, where 0 is the lsb and bits() - 1 is the msb
  1114.             if (b >= bits()) // if given index is larger than bits in this digits, return 0
  1115.                 return 0;
  1116.             return (digits[digits.size() - (b / BITS) - 1] >> (b % BITS)) & 1;
  1117.         }
  1118.  
  1119.         // Output digits as a string in bases 2 to 16, and 256
  1120.         std::string str(integer base = 10, unsigned int length = 1){
  1121.             std::string out = "";
  1122. //            if (base == 256){
  1123. //                if (digits.empty())
  1124. //                    out = std::string(1, 0);
  1125. //                for(d_size x = 0; x < digits.size(); x++)
  1126. //                    out += std::string(1, digits[x]);
  1127. //                while (out.size() < length)
  1128. //                    out = std::string(1, 0) + out;
  1129. //                if (_sign){
  1130. //                    if (!out[0])
  1131. //                        out = out.substr(1, out.size() - 1);
  1132. //                    out = "-" + out;
  1133. //                }
  1134. //            }
  1135. //            else{
  1136.                 if (((base < 2) || (base > 16)) && (base != 256))   // if base outside of 2 <= base <= 16
  1137.                     base = 10;                                      // set to default digits of 10
  1138.                 integer rhs = *this;
  1139.                 static const std::string B16 = "0123456789abcdef";
  1140.                 std::pair <integer, integer> qr;
  1141.                 do{
  1142.                     qr = dm(rhs, base);
  1143.                     out = B16[qr.second] + out;
  1144.                     rhs = qr.first;
  1145.                 } while (rhs);
  1146.  
  1147.                 while (out.size() < length)
  1148.                     out = "0" + out;
  1149.                 if (_sign){
  1150.                     if (out[0] == '0')
  1151.                         out = out.substr(1, out.size() - 1);
  1152.                     out = "-" + out;
  1153.                 }
  1154. //            }
  1155.             return out;
  1156.         }
  1157. };
  1158. // lhs type Z as first arguemnt
  1159.  
  1160. // Bitwise Operators
  1161. template <typename Z> Z operator&(const Z & lhs, integer rhs){
  1162.     return (Z) (rhs & lhs);
  1163. }
  1164.  
  1165. template <typename Z> Z operator|(const Z & lhs, integer rhs){
  1166.     return (Z) (rhs | lhs);
  1167. }
  1168.  
  1169. template <typename Z> Z operator^(const Z & lhs, integer rhs){
  1170.     return (Z) (rhs ^ lhs);
  1171. }
  1172.  
  1173. template <typename Z> Z operator&=(Z & lhs, integer rhs){
  1174.     lhs = (Z) (rhs & lhs);
  1175.     return lhs;
  1176. }
  1177.  
  1178. template <typename Z> Z operator|=(Z & lhs, integer rhs){
  1179.     lhs = (Z) (rhs | lhs);
  1180.     return lhs;
  1181. }
  1182.  
  1183. template <typename Z> Z operator^=(Z & lhs, integer rhs){
  1184.     lhs = (Z) (rhs ^ lhs);
  1185.     return lhs;
  1186. }
  1187.  
  1188. // Comparison Operators
  1189. template <typename Z> bool operator==(const Z & lhs, integer rhs){
  1190.     return (rhs == lhs);
  1191. }
  1192.  
  1193. template <typename Z> bool operator!=(const Z & lhs, integer rhs){
  1194.     return (rhs != lhs);
  1195. }
  1196.  
  1197. template <typename Z> bool operator>(const Z & lhs, integer rhs){
  1198.     return (rhs < lhs);
  1199. }
  1200.  
  1201. template <typename Z> bool operator<(const Z & lhs, integer rhs){
  1202.     return (rhs > lhs);
  1203. }
  1204.  
  1205. template <typename Z> bool operator>=(const Z & lhs, integer rhs){
  1206.     return (rhs <= lhs);
  1207. }
  1208.  
  1209. template <typename Z> bool operator<=(const Z & lhs, integer rhs){
  1210.     return (rhs >= lhs);
  1211. }
  1212.  
  1213. // Arithmetic Operators
  1214. template <typename Z> Z operator+(const Z & lhs, integer rhs){
  1215.     return (Z) (rhs + lhs);
  1216. }
  1217.  
  1218. template <typename Z> Z & operator+=(Z & lhs, integer rhs){
  1219.     lhs = (Z) (rhs + lhs);
  1220.     return lhs;
  1221. }
  1222.  
  1223. template <typename Z> Z operator-(const Z & lhs, integer rhs){
  1224.     return (Z) (integer(lhs) - rhs);
  1225. }
  1226.  
  1227. template <typename Z> Z & operator-=(Z & lhs, integer rhs){
  1228.     lhs = lhs - rhs;
  1229.     return lhs;
  1230. }
  1231.  
  1232. template <typename Z> Z operator*(const Z & lhs, integer rhs){
  1233.     return (Z) (rhs * lhs);
  1234. }
  1235.  
  1236. template <typename Z> Z & operator*=(Z & lhs, integer rhs){
  1237.     lhs = (Z) (rhs * lhs);
  1238.     return lhs;
  1239. }
  1240.  
  1241. template <typename Z> Z operator/(const Z & lhs, integer rhs){
  1242.     return (Z) (integer(lhs) / rhs);
  1243. }
  1244.  
  1245. template <typename Z> Z & operator/=(Z & lhs, integer rhs){
  1246.     lhs = integer(lhs) / rhs;
  1247.     return lhs;
  1248. }
  1249. template <typename Z> Z operator%(const Z & lhs, integer rhs){
  1250.     return (Z) (integer(lhs) % rhs);
  1251. }
  1252.  
  1253. template <typename Z> Z & operator%=(Z & lhs, integer rhs){
  1254.     lhs = lhs % rhs;
  1255.     return lhs;
  1256. }
  1257.  
  1258. // IO Operators
  1259. std::ostream & operator<<(std::ostream & stream, integer rhs){
  1260.     if (stream.flags() & stream.oct)
  1261.         stream << rhs.str(8);
  1262.     else if (stream.flags() & stream.hex)
  1263.         stream << rhs.str(16);
  1264.     else
  1265.         stream << rhs.str(10);
  1266.     return stream;
  1267. }
  1268.  
  1269. std::istream & operator>>(std::istream & stream, integer & rhs){
  1270.     uint8_t base;
  1271.     if (stream.flags() & stream.oct)
  1272.         base = 8;
  1273.     else if (stream.flags() & stream.hex)
  1274.         base = 16;
  1275.     else
  1276.         base = 10;
  1277.     std::string in;
  1278.     stream >> in;
  1279.     rhs = integer(in, base);
  1280.     return stream;
  1281. }
  1282.  
  1283. // Special functions
  1284. std::string makebin(integer digits, unsigned int size = 1){
  1285.     // Changes a digits into its binary string
  1286.     return digits.str(2, size);
  1287. }
  1288.  
  1289. std::string makehex(integer digits, unsigned int size = 1){
  1290.     // Changes a digits into its hexadecimal string
  1291.     return digits.str(16, size);
  1292. }
  1293.  
  1294. std::string makeascii(integer digits, unsigned int size = 1){
  1295.     // Changes a digits into ASCII
  1296.     return digits.str(256, size);
  1297. }
  1298.  
  1299. integer abs(integer digits){
  1300.     // returns the absolute digits of the integer
  1301.     return digits.abs();
  1302. }
  1303.  
  1304. template <typename Z>
  1305. integer POW(integer base, Z exp)
  1306. {
  1307.     if (exp < 0)
  1308.         return 0;
  1309.     integer result = 1;
  1310.     // take advantage of optimized integer * 10
  1311.     if (base == 10){
  1312.         for(Z x = 0; x < exp; x++)
  1313.             result *= base;
  1314.         return result;
  1315.     }
  1316.  
  1317.     while (exp)
  1318.    {
  1319.         if (exp & 1)
  1320.             result *= base;
  1321.         exp >>= 1;
  1322.         base *= base;
  1323.     }
  1324.     return result;
  1325. }
  1326.  
  1327. #endif // INTEGER_H
  1328.  
  1329. int main(){
  1330.     integer a("1111111111111111", 16);
  1331.     std::cout << (a *a).str(16) << std::endl;
  1332.     return 0;
  1333. }
  1334.  
  1335.  
Success #stdin #stdout 0s 3136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
123456789abcdef0fedcba987654321
https://ideone.com/WjA0ZS
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!