負の整数での除算と剰余を指定した挙動で
C++03では、左右両方のオペランドが正でないときは/や%の挙動が実装依存になるので、指定した挙動での除算と剰余を求める関数(+alpha)を作ってる。
hwm/arithmetic.hpp
#ifndef HWM_ARITHMETIC_HPP #define HWM_ARITHMETIC_HPP #include <cmath> #include <boost/assert.hpp> #include <boost/mpl/and.hpp> #include <boost/type_traits.hpp> #include <boost/utility/enable_if.hpp> namespace hwm { namespace arithmetic { template<int N = 0> struct sign_table { static int const n[2]; }; template<int N> int const sign_table<N>::n[2] = { -1, 1 }; template<typename T> bool odd(T const t, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { return t % 2 != 0; } template<typename T> bool odd(T const &t, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { return t % 2 != 0; } template<typename T> bool even(T const t, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { return t % 2 == 0; } template<typename T> bool even(T const &t, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { return t % 2 == 0; } inline int bool2sign(bool const b) { return sign_table<0>::n[b]; } template<typename T> int sign (T const t, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { return bool2sign(t>=0); } template<typename T> int sign (T const &t, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { return bool2sign(t>=0); } template<typename T> T abs_switch ( T const t, typename boost::enable_if< boost::mpl::and_< boost::is_signed<T>, boost::is_integral<T> > >::type* = 0 ) { return abs(t); } template<typename T> T abs_switch ( T const t, typename boost::enable_if< boost::mpl::and_< boost::is_unsigned<T>, boost::is_integral<T> > >::type* = 0 ) { return t; } template<typename T> T abs_switch ( T const t, typename boost::enable_if< boost::is_floating_point<T> >::type* = 0 ) { return fabs(t); } template<typename T> T mod_truncated(T const dividend, T const divisor, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); return (abs_switch(dividend) % abs_switch(divisor)) * sign(dividend); } template<typename T> T mod_truncated(T const ÷nd, T const &divisor, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); return (abs_switch(dividend) % abs_switch(divisor)) * sign(dividend); } template<typename T> T mod_floored(T const dividend, T const divisor, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); int const dividend_sign = sign(dividend); bool const positive_dividend = dividend >= 0; bool const positive_divisor = divisor >= 0; T const unsigned_modulo = (abs_switch(dividend)) % (abs_switch(divisor)); return unsigned_modulo * dividend_sign + ((int)((unsigned_modulo != 0) && (positive_dividend==false)) * abs_switch(divisor)) - ((int)((unsigned_modulo != 0) && (positive_divisor==false)) * abs_switch(divisor)); } template<typename T> T mod_floored(T const ÷nd, T const &divisor, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); int const dividend_sign = sign(dividend); bool const positive_dividend = dividend >= 0; bool const positive_divisor = divisor >= 0; T const unsigned_modulo = (abs_switch(dividend)) % (abs_switch(divisor)); return unsigned_modulo * dividend_sign + ((int)((unsigned_modulo != 0) && (positive_dividend==false)) * abs_switch(divisor)) - ((int)((unsigned_modulo != 0) && (positive_divisor==false)) * abs_switch(divisor)); } template<typename T> T mod_euclidean(T const dividend, T const divisor, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); int const dividend_sign = sign(dividend); bool const positive_dividend = dividend >= 0; T const unsigned_modulo = (abs_switch(dividend)) % (abs_switch(divisor)); return unsigned_modulo * dividend_sign + ((int)((unsigned_modulo != 0) && (positive_dividend==false)) * abs_switch(divisor)); } template<typename T> T mod_euclidean(T const ÷nd, T const &divisor, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); int const dividend_sign = sign(dividend); bool const positive_dividend = dividend >= 0; T const unsigned_modulo = (abs_switch(dividend)) % (abs_switch(divisor)); return unsigned_modulo * dividend_sign + ((int)((unsigned_modulo != 0) && (positive_dividend==false)) * abs_switch(divisor)); } template<typename T> T div_truncated(T const dividend, T const divisor, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); return (abs_switch(dividend) / abs_switch(divisor)) * sign(dividend) * sign(divisor); } template<typename T> T div_truncated(T const ÷nd, T const &divisor, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); return (abs_switch(dividend) / abs_switch(divisor)) * sign(dividend) * sign(divisor); } template<typename T> T div_floored(T const dividend, T const divisor, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); return (abs_switch(dividend) / abs_switch(divisor)) * sign(dividend) * sign(divisor) - (int)(dividend % divisor != 0) * ((dividend >= 0) ^ (divisor >= 0)); } template<typename T> T div_floored(T const ÷nd, T const &divisor, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); return (abs_switch(dividend) / abs_switch(divisor)) * sign(dividend) * sign(divisor) - (int)(dividend % divisor != 0) * ((dividend >= 0) ^ (divisor >= 0)); } template<typename T> T div_euclidean(T const dividend, T const divisor, typename boost::enable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); return (abs_switch(dividend) / abs_switch(divisor)) * sign(dividend) * sign(divisor) - (int)(dividend % divisor != 0) * (((dividend >= 0) ^ (divisor >= 0)) - (int)(divisor < 0)); } template<typename T> T div_euclidean(T const ÷nd, T const &divisor, typename boost::disable_if< boost::is_pod<T> >::type* = 0) { BOOST_ASSERT(divisor != 0); return (abs_switch(dividend) / abs_switch(divisor)) * sign(dividend) * sign(divisor) - (int)(dividend % divisor != 0) * (((dividend >= 0) ^ (divisor >= 0)) - (int)(divisor < 0)); } } } //namespace hwm::arithmetic #endif //HWM_ARITHMETIC_HPP
テスト
#include <iostream> #include <vector> #include <boost/timer.hpp> #include <boost/test/minimal.hpp> #include <pstade/oven/foreach.hpp> #include "hwm/arithmetic.hpp" template<typename T> void disp_mod(int n, T const &v) { namespace ha = hwm::arithmetic; PSTADE_OVEN_FOREACH_TPL(_1, v) { std::cout << _1 << " % " << n << " = " << ha::mod_truncated(_1, n) << " [mod truncated]\n"; } PSTADE_OVEN_FOREACH_TPL(_1, v) { std::cout << _1 << " % " << n << " = " << ha::mod_floored(_1, n) << " [mod floored]\n"; } PSTADE_OVEN_FOREACH_TPL(_1, v) { std::cout << _1 << " % " << n << " = " << ha::mod_euclidean(_1, n) << "[mod euclidean]\n"; } } template<typename T> void disp_div(int n, T const &v) { namespace ha = hwm::arithmetic; PSTADE_OVEN_FOREACH_TPL(_1, v) { std::cout << _1 << " % " << n << " = " << ha::div_truncated(_1, n) << " [div truncated]\n"; } PSTADE_OVEN_FOREACH_TPL(_1, v) { std::cout << _1 << " % " << n << " = " << ha::div_floored(_1, n) << " [div floored]\n"; } PSTADE_OVEN_FOREACH_TPL(_1, v) { std::cout << _1 << " % " << n << " = " << ha::div_euclidean(_1, n) << "[div euclidean]\n"; } } template<typename T> void test_div_mod(int n, T const &v) { namespace ha = hwm::arithmetic; PSTADE_OVEN_FOREACH_TPL(_1, v) { BOOST_CHECK(ha::div_truncated(_1, n) * n + ha::mod_truncated(_1, n) == _1); } PSTADE_OVEN_FOREACH_TPL(_1, v) { BOOST_CHECK(ha::div_floored(_1, n) * n + ha::mod_floored(_1, n) == _1); } PSTADE_OVEN_FOREACH_TPL(_1, v) { BOOST_CHECK(ha::div_euclidean(_1, n) * n + ha::mod_euclidean(_1, n) == _1); } } int test_main(int argc, char **argv) { BOOST_CHECK(hwm::arithmetic::abs_switch(5) == 5); BOOST_CHECK(hwm::arithmetic::abs_switch(-5) == 5); BOOST_CHECK(hwm::arithmetic::abs_switch((unsigned int)-5) == (unsigned int)-5); BOOST_CHECK(hwm::arithmetic::abs_switch(-0.5) == 0.5); BOOST_CHECK(hwm::arithmetic::odd(11) == true); BOOST_CHECK(hwm::arithmetic::even(11) == false); BOOST_CHECK(hwm::arithmetic::odd(12) == false); BOOST_CHECK(hwm::arithmetic::even(12) == true); std::vector<int> v; for(int i = -10; i < 10; ++i) { v.push_back(i); } std::cout << "----------mod----------\n"; std::cout << "disp mod(3)\n"; disp_mod(3, v); std::cout << "disp mod(1)\n"; disp_mod(1, v); std::cout << "disp mod(-1)\n"; disp_mod(-1, v); std::cout << "disp mod(-3)\n"; disp_mod(-3, v); std::cout << "----------div----------\n"; std::cout << "disp div(3)\n"; disp_div(3, v); std::cout << "disp div(1)\n"; disp_div(1, v); std::cout << "disp div(-1)\n"; disp_div(-1, v); std::cout << "disp div(-3)\n"; disp_div(-3, v); std::cout << "----------div,mod test----------\n"; std::cout << "test div,mod(3)\n"; test_div_mod(3, v); std::cout << "test div,mod(1)\n"; test_div_mod(1, v); std::cout << "test div,mod(-1)\n"; test_div_mod(-1, v); std::cout << "test div,mod(-3)\n"; test_div_mod(-3, v); std::cout << "----------performance----------\n"; { int n; //最適化時の計算省略を抑止 boost::timer tm; for(int i = 0; i < 1000000; ++i) { PSTADE_OVEN_FOREACH(_1, v) { n = _1 / 3; n--; n += _1 % 3; } } std::cout << "operator version : " << tm.elapsed() << "秒\n"; if(n == -1) { std::cout << n; } } { int n; boost::timer tm; for(int i = 0; i < 1000000; ++i) { PSTADE_OVEN_FOREACH(_1, v) { n = hwm::arithmetic::div_floored(_1, 3); n--; n += hwm::arithmetic::mod_floored(_1, 3); } } std::cout << "function version : " << tm.elapsed() << "秒\n"; if(n == -1) { std::cout << n; } } return 0; }
msvc9.0sp1とgcc4.5.0、boost1.42.0で確認
パフォーマンスについて、
最適化を掛ければ関数テンプレートの呼び出しは全部展開されてるけど、
それでもただの演算子の方と比べたら3~4倍くらいの時間かかってる。デバッグ版の方はもうちょっと差が大きい。
でもまあそんなにシビアな状況じゃなきゃ使えそう。
関数の名前はここに従っております。
http://en.wikipedia.org/wiki/Modulo_operation
Working DraftのN3126(5.6.4[expr.mul])によると整数の除算はAlgebraic Quotient(This is often called truncation toword zero.)ってなってたので、
C++0xでの除算、剰余の挙動は上の関数で言うとmod_truncated, div_truncatedに当たるのだと思います。
むやみにPOD型以外のバージョンも作ってみたけどちゃんと動くかテストしてないしなによりいらないかもですよね。ていうかPOD型もちゃんと動いてますかね。
