Chris@16: /* boost random/detail/large_arithmetic.hpp header file
Chris@16:  *
Chris@16:  * Copyright Steven Watanabe 2011
Chris@16:  * Distributed under the Boost Software License, Version 1.0. (See
Chris@16:  * accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org for most recent version including documentation.
Chris@16:  *
Chris@101:  * $Id$
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_RANDOM_DETAIL_LARGE_ARITHMETIC_HPP
Chris@16: #define BOOST_RANDOM_DETAIL_LARGE_ARITHMETIC_HPP
Chris@16: 
Chris@16: #include <boost/cstdint.hpp>
Chris@16: #include <boost/integer.hpp>
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/random/detail/integer_log2.hpp>
Chris@16: 
Chris@16: #include <boost/random/detail/disable_warnings.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace random {
Chris@16: namespace detail {
Chris@16: 
Chris@16: struct div_t {
Chris@16:     boost::uintmax_t quotient;
Chris@16:     boost::uintmax_t remainder;
Chris@16: };
Chris@16: 
Chris@16: inline div_t muldivmod(boost::uintmax_t a, boost::uintmax_t b, boost::uintmax_t m)
Chris@16: {
Chris@101:     const int bits =
Chris@16:         ::std::numeric_limits< ::boost::uintmax_t>::digits / 2;
Chris@101:     const ::boost::uintmax_t mask = (::boost::uintmax_t(1) << bits) - 1;
Chris@16:     typedef ::boost::uint_t<bits>::fast digit_t;
Chris@16: 
Chris@16:     int shift = std::numeric_limits< ::boost::uintmax_t>::digits - 1
Chris@16:         - detail::integer_log2(m);
Chris@16: 
Chris@16:     a <<= shift;
Chris@16:     m <<= shift;
Chris@16: 
Chris@16:     digit_t product[4] = { 0, 0, 0, 0 };
Chris@16:     digit_t a_[2] = { digit_t(a & mask), digit_t((a >> bits) & mask) };
Chris@16:     digit_t b_[2] = { digit_t(b & mask), digit_t((b >> bits) & mask) };
Chris@16:     digit_t m_[2] = { digit_t(m & mask), digit_t((m >> bits) & mask) };
Chris@16: 
Chris@16:     // multiply a * b
Chris@16:     for(int i = 0; i < 2; ++i) {
Chris@16:         digit_t carry = 0;
Chris@16:         for(int j = 0; j < 2; ++j) {
Chris@16:             ::boost::uint64_t temp = ::boost::uintmax_t(a_[i]) * b_[j] +
Chris@16:                 carry + product[i + j];
Chris@16:             product[i + j] = digit_t(temp & mask);
Chris@16:             carry = digit_t(temp >> bits);
Chris@16:         }
Chris@16:         if(carry != 0) {
Chris@16:             product[i + 2] += carry;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     digit_t quotient[2];
Chris@16: 
Chris@16:     if(m == 0) {
Chris@16:         div_t result = {
Chris@16:             ((::boost::uintmax_t(product[3]) << bits) | product[2]),
Chris@16:             ((::boost::uintmax_t(product[1]) << bits) | product[0]) >> shift,
Chris@16:         };
Chris@16:         return result;
Chris@16:     }
Chris@16: 
Chris@16:     // divide product / m
Chris@16:     for(int i = 3; i >= 2; --i) {
Chris@16:         ::boost::uintmax_t temp =
Chris@16:             ::boost::uintmax_t(product[i]) << bits | product[i - 1];
Chris@16: 
Chris@16:         digit_t q = digit_t((product[i] == m_[1]) ? mask : temp / m_[1]);
Chris@16: 
Chris@16:         ::boost::uintmax_t rem =
Chris@16:             ((temp - ::boost::uintmax_t(q) * m_[1]) << bits) + product[i - 2];
Chris@16: 
Chris@16:         ::boost::uintmax_t diff = m_[0] * ::boost::uintmax_t(q);
Chris@16: 
Chris@16:         int error = 0;
Chris@16:         if(diff > rem) {
Chris@16:             if(diff - rem > m) {
Chris@16:                 error = 2;
Chris@16:             } else {
Chris@16:                 error = 1;
Chris@16:             }
Chris@16:         }
Chris@16:         q -= error;
Chris@16:         rem = rem + error * m - diff;
Chris@16: 
Chris@16:         quotient[i - 2] = q;
Chris@16:         product[i] = 0;
Chris@101:         product[i-1] = static_cast<digit_t>((rem >> bits) & mask);
Chris@101:         product[i-2] = static_cast<digit_t>(rem & mask);
Chris@16:     }
Chris@16: 
Chris@16:     div_t result = {
Chris@16:         ((::boost::uintmax_t(quotient[1]) << bits) | quotient[0]),
Chris@16:         ((::boost::uintmax_t(product[1]) << bits) | product[0]) >> shift,
Chris@16:     };
Chris@16:     return result;
Chris@16: }
Chris@16: 
Chris@16: inline boost::uintmax_t muldiv(boost::uintmax_t a, boost::uintmax_t b, boost::uintmax_t m)
Chris@16: { return detail::muldivmod(a, b, m).quotient; }
Chris@16: 
Chris@16: inline boost::uintmax_t mulmod(boost::uintmax_t a, boost::uintmax_t b, boost::uintmax_t m)
Chris@16: { return detail::muldivmod(a, b, m).remainder; }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: } // namespace random
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #include <boost/random/detail/enable_warnings.hpp>
Chris@16: 
Chris@16: #endif // BOOST_RANDOM_DETAIL_LARGE_ARITHMETIC_HPP