Minimum non-negative reminder (tools/mod.hpp)

template <typename M, typename N>
constexpr std::common_type_t<M, N> mod(M a, N b) noexcept;

Given $a$ and $b (\neq 0)$, a pair of values $(q, r)$ satisfying the following conditions is uniquely determined.

\[\begin{align*} \left\{\begin{array}{l} a = qb + r\\ q \in \mathbb{Z}\\ 0 \leq r < |b| \end{array}\right.& \end{align*}\]

It returns $r$.

Constraints

<M> is a built-in integral type, tools::int128_t or tools::uint128_t.
<N> is a built-in integral type, tools::int128_t or tools::uint128_t.
$b \neq 0$

Time Complexity

$O(1)$

License

Author

anqooqie

Depends on

std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)

Required by

Verified with

Code

#ifndef TOOLS_MOD_HPP
#define TOOLS_MOD_HPP

#include <cassert>
#include <type_traits>
#include "tools/is_integral.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> mod(const M a, const N b) noexcept {
    assert(b != 0);

    using UM = ::std::make_unsigned_t<M>;
    using UN = ::std::make_unsigned_t<N>;
    const UM ua = a >= 0 ? a : static_cast<UM>(-(a + 1)) + 1;
    const UN ub = b >= 0 ? b : static_cast<UN>(-(b + 1)) + 1;
    auto r = ua % ub;
    if (a < 0 && r > 0) {
      r = ub - r;
    }
    return r;
  }
}

#endif

#line 1 "tools/mod.hpp"



#include <cassert>
#include <type_traits>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 7 "tools/mod.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> mod(const M a, const N b) noexcept {
    assert(b != 0);

    using UM = ::std::make_unsigned_t<M>;
    using UN = ::std::make_unsigned_t<N>;
    const UM ua = a >= 0 ? a : static_cast<UM>(-(a + 1)) + 1;
    const UN ub = b >= 0 ? b : static_cast<UN>(-(b + 1)) + 1;
    auto r = ua % ub;
    if (a < 0 && r > 0) {
      r = ub - r;
    }
    return r;
  }
}