big_int.cpp

#include <boost/hana.hpp>

namespace h = boost::hana;

using uint_t = unsigned;
constexpr auto uint_zero =
  h::zero<h::integral_constant_tag<uint_t>>();

template <uint_t... xs>
using big_int = h::tuple<h::uint<xs>...>;

template <uint_t... xs>
constexpr big_int<xs...> big_int_c{};

struct usum_carry_t {
  template <uint_t xs, uint_t ys>
  constexpr auto operator () (h::uint<xs>, h::uint<ys>) const
    { return h::uint_c<static_cast<uint_t>(~xs < ys)>; }
};
constexpr usum_carry_t usum_carry{};

struct drop_leading_zeros_t {
  template <uint_t... xs>
  constexpr auto operator () (big_int<xs...> x) const // nasty
    { return h::reverse(h::drop_while(h::reverse(x), h::equal.to(uint_zero))); }
};
constexpr drop_leading_zeros_t drop_leading_zeros{};

struct bit_not_t {
  template <uint_t... xs>
  constexpr auto operator () (big_int<xs...>) const {
    return big_int_c<~xs...>;
  }
};
constexpr bit_not_t bit_not{};

struct uinc_t {
  template <uint_t x0, uint_t x1, uint_t... xs>
  constexpr auto operator () (big_int<x0, x1, xs...>) const {
    auto inc_first = (*this)(big_int_c<x0>);
    auto has_carry = !h::is_empty(h::drop_front(inc_first));

    auto tail = big_int_c<x1, xs...>;
    auto tail_with_carry =
      h::if_(has_carry, (*this)(tail), tail);

    return h::prepend(tail_with_carry, h::front(inc_first));
  }

  template <uint_t x0>
  constexpr auto operator () (big_int<x0>) const {
    auto carry = usum_carry(h::uint_c<x0>, h::uint_c<1u>);
    auto partial_sum = big_int_c<x0 + 1u>;
    auto sum = h::if_(h::equal(carry, uint_zero),
      partial_sum, h::append(partial_sum, 1u));

    return sum;
  }
};
constexpr uinc_t uinc{};

struct additive_inverse_t {
  template <uint_t... xs>
  constexpr auto operator () (big_int<xs...> x) const {
    auto partial = uinc(bit_not(x));
    auto result = h::if_(h::size(partial) != h::size(x),
      h::drop_back(partial), partial);

    return result;
  }
};
constexpr additive_inverse_t additive_inverse{};

struct usum_t {
template <uint_t... xs, uint_t... ys>
  constexpr auto operator ()
    (big_int<xs...> x, big_int<ys...> y) const
  {
    using namespace boost::hana;

    auto x_size = size(x);
    auto y_size = size(y);

    auto min_size = min(x_size, y_size);
    auto x_smaller = min_size == x_size;
    auto biggest_seq = if_(x_smaller, y, x);

    auto partial_sums = zip_shortest_with(plus, x, y);
    auto carries = zip_shortest_with(usum_carry, x, y);

    auto rest = drop_front_exactly(biggest_seq, min_size);
    auto next = if_(is_empty(rest), make_tuple(uint_zero), take_c<1>(rest));
    auto psums_next = concat(partial_sums, next);
    auto shifted_carries = prepend(carries, uint_zero);

    auto last_carry = usum_carry(back(psums_next), back(shifted_carries));
    auto sums = zip_with(plus, psums_next, shifted_carries);
    auto tail = append(drop_front(rest), last_carry);

    return drop_leading_zeros(concat(sums, tail));
  }
};
constexpr usum_t usum{};

int main(void) {
  static_assert(usum(big_int_c<0xffffffffu, 0xffffffffu>, big_int_c<1u>) == big_int_c<0u, 0u, 1u>, "");
  static_assert(usum(big_int_c<0xffffffffu>, big_int_c<1u>) == big_int_c<0u, 1u>, "");
  static_assert(usum(big_int_c<1u>, big_int_c<1u>) == big_int_c<2u>, "");
  static_assert(usum(big_int_c<1u>, big_int_c<1u, 1u>) == big_int_c<2u, 1u>, "");
  static_assert(uinc(big_int_c<0xffffffff, 0xffffffff>) == big_int_c<0u, 0u, 1u>, "");
  static_assert(uinc(big_int_c<0xffffffff>) == big_int_c<0u, 1u>, "");
  static_assert(uinc(big_int_c<1u>) == big_int_c<2u>, "");
  static_assert(uinc(big_int_c<1u, 1u>) == big_int_c<2u, 1u>, "");
  static_assert(bit_not(big_int_c<0u>) == big_int_c<0xffffffffu>, "");
  static_assert(bit_not(big_int_c<0xffffffffu>) == big_int_c<0u>, "");
  static_assert(bit_not(big_int_c<0xf0f0f0f0u>) == big_int_c<0x0f0f0f0fu>, "");
  static_assert(bit_not(big_int_c<0x0f0f0f0fu>) == big_int_c<0xf0f0f0f0u>, "");
  static_assert(bit_not(big_int_c<0x0f0f0f0fu, 0xf0f0f0f0u>)
                        == big_int_c<0xf0f0f0f0u, 0x0f0f0f0fu>, "");
  static_assert(bit_not(big_int_c<1u>) == big_int_c<0xfffffffeu>, "");
  static_assert(bit_not(big_int_c<0xfffffffeu>) == big_int_c<1u>, "");
  static_assert(additive_inverse(big_int_c<1u>) == big_int_c<0xffffffffu>, "");
  static_assert(additive_inverse(big_int_c<0xffffffffu>) == big_int_c<1u>, "");
  static_assert(additive_inverse(big_int_c<0u>) == big_int_c<0u>, "");

  return 0;
}