cpp-bignumber/src/biginteger.cpp

//
//  biginteger.cpp
//  bigdecimal
//
//  Created by Sam Jaffe on 6/30/17.
//

#include "biginteger.h"

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace math;

namespace detail {
  using data_type = biginteger::data_type;
  // 1 => GREATER, 0 => EQUAL, -1 => LESS
  int compare(data_type const & rhs, data_type const & lhs);
  void add(data_type & rhs, data_type const & lhs);
  void subtract_nounderflow(data_type & rhs, data_type const & lhs);
  void multiply(data_type & rhs, data_type const & lhs);
  std::pair<data_type, data_type> divide(data_type remainder, data_type const & divisor);
}

static void swap(biginteger & rhs, biginteger && lhs) {
  swap(rhs, lhs);
}

biginteger::biginteger()
: biginteger(false, 0) {}

biginteger::biginteger(int32_t value)
: biginteger(static_cast<int64_t>(value)) {}

biginteger::biginteger(uint32_t value)
: biginteger(static_cast<uint64_t>(value)) {}

biginteger::biginteger(int64_t value) :
biginteger(value < 0, static_cast<uint64_t>(value < 0 ? -value : value)) {}

biginteger::biginteger(uint64_t value)
: biginteger(false, value) {}

biginteger::biginteger(char const * number)
: is_negative(number[0] == '-') {
  // 999,999,996,000,000,005,999,999,996,000,000,001
  if (is_negative) ++number;
  auto len = strlen(number);
  auto elems = len/SEG_DIGITS;
  data.resize(elems);
  {
    auto small = len-(elems*SEG_DIGITS);
    if (small > 0) {
      char seg[SEG_DIGITS+1] = "";
      strncpy(seg, number, small);
      data.push_back(atoi(seg));
      number += small;
    }
  }
  for (data_type::size_type idx = elems; idx > 0; --idx, number += SEG_DIGITS) {
    char seg[SEG_DIGITS+1] = "";
    strncpy(seg, number, SEG_DIGITS);
    data[idx-1] = atoi(seg);
  }
}

biginteger::biginteger(bool neg, uint64_t value) :
is_negative(neg) {
  uint64_t next{0};
  do {
    next = value / OVER_SEG;
    data.push_back(static_cast<int32_t>(value - (OVER_SEG * next)));
  } while ((value = next) > 0);
}

biginteger::biginteger(bool neg, data_type && dt) :
is_negative(neg), data(std::move(dt)) {}

biginteger & math::operator+=(biginteger & rhs, biginteger const & lhs) {
  if (lhs == biginteger::ZERO) { return rhs; }
  else if (rhs == biginteger::ZERO) { rhs=lhs; }
  else if (rhs.is_negative == lhs.is_negative) {
    detail::add(rhs.data, lhs.data);
  } else {
    auto cmp = detail::compare(rhs.data, lhs.data);
    if (cmp == 0) {
      rhs = biginteger::ZERO;
    } else if (cmp > 0) {
      detail::subtract_nounderflow(rhs.data, lhs.data);
    } else {
      biginteger tmp{lhs};
      swap(rhs, tmp);
      detail::subtract_nounderflow(rhs.data, tmp.data);
    }
  }
  return rhs;
}

biginteger & math::operator-=(biginteger & rhs, biginteger const & lhs) {
  if (lhs == biginteger::ZERO) { return rhs; }
  else if (rhs == biginteger::ZERO) { rhs = -lhs; }
  if (rhs.is_negative != lhs.is_negative) {
    detail::add(rhs.data, lhs.data);
  } else {
    auto cmp = detail::compare(rhs.data, lhs.data);
    if (cmp == 0) {
      rhs = biginteger::ZERO;
    } else if (cmp > 0) {
      detail::subtract_nounderflow(rhs.data, lhs.data);
    } else {
      biginteger tmp{-lhs};
      swap(rhs, tmp);
      detail::subtract_nounderflow(rhs.data, tmp.data);;
    }
  }
  return rhs;
}

biginteger & math::operator*=(biginteger & rhs, biginteger const & lhs) {
  bool is_neg = rhs.is_negative != lhs.is_negative;
  if (rhs == biginteger::ZERO || lhs == biginteger::ZERO) {
    rhs = biginteger::ZERO;
  } else if (detail::compare(lhs.data, biginteger::ONE.data) == 0) {
    rhs.is_negative = is_neg;
  } else if (detail::compare(rhs.data, biginteger::ONE.data) == 0) {
    rhs = lhs;
    rhs.is_negative = is_neg;
  } else {
    detail::multiply(rhs.data, lhs.data);
  }
  return rhs;
}

biginteger & math::operator/=(biginteger & rhs, biginteger const & lhs) {
  swap(rhs, rhs / lhs);
  return rhs;
}

biginteger biginteger::operator-() const {
  return (*this) * NEGATIVE_ONE;
}

biginteger math::operator+(biginteger rhs, biginteger const & lhs) {
  return rhs += lhs;
}

biginteger math::operator-(biginteger rhs, biginteger const & lhs) {
  return rhs -= lhs;
}

biginteger math::operator*(biginteger rhs, biginteger const & lhs) {
  return rhs *= lhs;
}

biginteger math::operator/(biginteger const & rhs, biginteger const & lhs) {
  if (lhs == biginteger::ZERO) { throw std::domain_error("cannot divide by 0"); }
  else if (rhs == biginteger::ZERO) { return biginteger::ZERO; }
  else if (detail::compare(lhs.data, {1}) == 0) {
    return {rhs.is_negative != lhs.is_negative, biginteger::data_type{rhs.data}};
  } else {
    auto cmp = detail::compare(rhs.data, lhs.data);
    bool is_neg = rhs.is_negative != lhs.is_negative;
    if (cmp < 0) { return biginteger::ZERO; }
    else if (cmp == 0) { return {is_neg, {1}}; }
    else { return {is_neg, detail::divide(rhs.data, lhs.data).first}; }
  }
}

biginteger math::operator%(biginteger const & rhs, biginteger const & lhs) {
  if (lhs == biginteger::ZERO) { throw std::domain_error("cannot divide by 0"); }
  else if (detail::compare(lhs.data, biginteger::ONE.data) == 0 ||
           rhs == biginteger::ZERO) { return biginteger::ZERO; }
  else {
    auto cmp = detail::compare(rhs.data, lhs.data);
    if (cmp < 0) { return rhs; }
    else if (cmp == 0) { return biginteger::ZERO; }
    else {
      auto data = detail::divide(rhs.data, lhs.data).second;
      if (detail::compare(data, {0}) == 0) { return biginteger::ZERO; }
      else if (rhs.is_negative != lhs.is_negative) {
        auto tmp = lhs.data;
        swap(data, tmp);
        detail::subtract_nounderflow(data, tmp);
      }
      return {lhs.is_negative, std::move(data)};
    }
  }
}

namespace detail {
#define IMPL_COMPARE(expr) \
  if (rhs expr < lhs expr) return -1; \
  else if (lhs expr < rhs expr) return 1
  
  int compare(data_type const & rhs, data_type const & lhs) {
    IMPL_COMPARE(.size());
    for (size_t i = rhs.size(); i > 0; --i) {
      IMPL_COMPARE([i-1]);
    }
    return 0;
  }
#undef IMPL_COMPARE
  
  void add(data_type & rhs, data_type const & lhs) {
    rhs.resize(std::max(rhs.size(), lhs.size())+1);
    auto const lbnd = lhs.size(), ubnd = rhs.size() - 1;
    // Add
    for (size_t i = 0; i < lbnd; ++i) {
      rhs[i] += lhs[i];
    }
    // Carry
    for (size_t i = 0; i < ubnd; ++i) {
      if (rhs[i] > biginteger::MAX_SEG) {
        rhs[i] -= biginteger::OVER_SEG;
        rhs[i+1] += 1;
      }
    }
    if (rhs[ubnd] == 0) { rhs.pop_back(); }
  }
  
  void subtract_nounderflow(data_type & rhs, data_type const & lhs) {
    size_t const rbnd = rhs.size(), lbnd = lhs.size();
    // Subtract
    for (size_t i = 0; i < lbnd; ++i) {
      rhs[i] -= lhs[i];
    }
    // Borrow
    for (size_t i = 0; i < rbnd; ++i) {
      if (rhs[i] < 0) {
        rhs[i] += biginteger::OVER_SEG;
        rhs[i+1] -= 1;
      }
    }
    if (rhs[rbnd-1] == 0 && rbnd > 1) { rhs.pop_back(); }
  }
  
  void multiply(data_type & rhs, data_type const & lhs) {
    size_t const rbnd = rhs.size(), lbnd = lhs.size();
    size_t const ubnd = rbnd + lbnd;
    rhs.resize(ubnd);
    // Multiply
    for (size_t i = rbnd; i > 0; --i) {
      int32_t const value = rhs[i-1];
      for (size_t j = lbnd; j > 0; --j) {
        // Max input              999,999,999
        // Max output 999,999,998,000,000,001
        int64_t product = static_cast<int64_t>(value) * static_cast<int64_t>(lhs[j-1]);
        int64_t overflow = product / biginteger::OVER_SEG;
        rhs[i+j-2] += static_cast<int32_t>(product - (overflow * biginteger::OVER_SEG));
        rhs[i+j-1] += static_cast<int32_t>(overflow);
      }
      rhs[i-1] -= value;
    }
    // Carry
    for (size_t i = 0; i < ubnd-1; ++i) {
      if (rhs[i] > biginteger::MAX_SEG) {
        int32_t overflow = rhs[i] / biginteger::OVER_SEG;
        rhs[i] -= (overflow * biginteger::OVER_SEG);
        rhs[i+1] += overflow;
      }
    }
    while (rhs.back() == 0) { rhs.pop_back(); }
  }
  
  data_type shift10(data_type const & data, int32_t pow, size_t shift) {
    size_t const bnd = data.size();
    data_type rval(bnd + shift + 1);
    for (size_t i = 0; i < bnd; ++i) {
      int64_t product = static_cast<int64_t>(data[i]) * static_cast<int64_t>(pow);
      int64_t overflow = product / biginteger::OVER_SEG;
      rval[i+shift] += static_cast<int32_t>(product - (overflow * biginteger::OVER_SEG));
      rval[i+shift+1] += static_cast<int32_t>(overflow);
    }
    if (rval.back() == 0 && rval.size() > 1) { rval.pop_back(); }
    return rval;
  }
  
  size_t digits(int32_t val) {
    return val == 0 ? 1 : static_cast<size_t>(floor(log10(val))) + 1;
  }
  
  size_t digits(data_type const & data) {
    return biginteger::SEG_DIGITS * (data.size()-1) + digits(data.back());
  }
  
  int32_t powers[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
  
  std::pair<data_type, data_type> divide(data_type remainder, data_type const & divisor) {
    data_type accum{0};
    auto const dig = digits(divisor);
    do {
      auto const diff = std::max(1UL, digits(remainder) - dig) - 1;
      auto const shift = diff / biginteger::SEG_DIGITS;
      auto const ipow = diff - (shift * biginteger::SEG_DIGITS);
      data_type step{shift10({1}, powers[ipow], shift)};
      data_type value{shift10(divisor, powers[ipow], shift)};
      do {
        subtract_nounderflow(remainder, value);
        add(accum, step);
      } while (detail::compare(remainder, value) >= 0);
    } while (detail::compare(remainder, divisor) >= 0);
    return { std::move(accum), std::move(remainder) };
  }
}

bool math::operator==(biginteger const & rhs, biginteger const & lhs) {
  return rhs.is_negative == lhs.is_negative && detail::compare(rhs.data, lhs.data) == 0;
}

bool math::operator!=(biginteger const & rhs, biginteger const & lhs) {
  return !(rhs == lhs);
}

bool math::operator<=(biginteger const & rhs, biginteger const & lhs) {
  return !(rhs > lhs);
}

bool math::operator< (biginteger const & rhs, biginteger const & lhs) {
  if (rhs.is_negative != lhs.is_negative) { return rhs.is_negative; }
  else if (rhs.is_negative) { return detail::compare(rhs.data, lhs.data) > 0; }
  else { return detail::compare(rhs.data, lhs.data) < 0; }
}

bool math::operator>=(biginteger const & rhs, biginteger const & lhs) {
  return !(rhs < lhs);
}

bool math::operator> (biginteger const & rhs, biginteger const & lhs) {
  return lhs < rhs;
}

biginteger const biginteger::ZERO{0}, biginteger::ONE{1}, biginteger::NEGATIVE_ONE{-1};

std::string biginteger::to_string() const {
  std::vector<char> output(biginteger::SEG_DIGITS * data.size() + 1, '\0');
  std::ptrdiff_t idx = 0;
  if (is_negative) { output[0] = '-'; ++idx; }
  idx += sprintf(output.data() + idx, "%d", data[data.size()-1]);
  for (size_t i = data.size()-1; i > 0; --i, idx+=SEG_DIGITS) {
    sprintf(output.data() + idx, "%0.*d", SEG_DIGITS, data[i-1]);
  }
  return output.data();
}