Chris@102: /* Chris@102: Copyright (c) Marshall Clow 2014. Chris@102: Chris@102: Distributed under the Boost Software License, Version 1.0. (See accompanying Chris@102: file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) Chris@102: Chris@102: Revision history: Chris@102: 2 Dec 2014 mtc First version; power Chris@102: Chris@102: */ Chris@102: Chris@102: /// \file algorithm.hpp Chris@102: /// \brief Misc Algorithms Chris@102: /// \author Marshall Clow Chris@102: /// Chris@102: Chris@102: #ifndef BOOST_ALGORITHM_HPP Chris@102: #define BOOST_ALGORITHM_HPP Chris@102: Chris@102: #include // for boost::disable_if Chris@102: #include Chris@102: Chris@102: namespace boost { namespace algorithm { Chris@102: Chris@102: template Chris@102: T identity_operation ( std::multiplies ) { return T(1); } Chris@102: Chris@102: template Chris@102: T identity_operation ( std::plus ) { return T(0); } Chris@102: Chris@102: Chris@102: /// \fn power ( T x, Integer n ) Chris@102: /// \return the value "x" raised to the power "n" Chris@102: /// Chris@102: /// \param x The value to be exponentiated Chris@102: /// \param n The exponent (must be >= 0) Chris@102: /// Chris@102: // \remark Taken from Knuth, The Art of Computer Programming, Volume 2: Chris@102: // Seminumerical Algorithms, Section 4.6.3 Chris@102: template Chris@102: typename boost::enable_if, T>::type Chris@102: power (T x, Integer n) { Chris@102: T y = 1; // Should be "T y{1};" Chris@102: if (n == 0) return y; Chris@102: while (true) { Chris@102: if (n % 2 == 1) { Chris@102: y = x * y; Chris@102: if (n == 1) Chris@102: return y; Chris@102: } Chris@102: n = n / 2; Chris@102: x = x * x; Chris@102: } Chris@102: return y; Chris@102: } Chris@102: Chris@102: /// \fn power ( T x, Integer n, Operation op ) Chris@102: /// \return the value "x" raised to the power "n" Chris@102: /// using the operaton "op". Chris@102: /// Chris@102: /// \param x The value to be exponentiated Chris@102: /// \param n The exponent (must be >= 0) Chris@102: /// \param op The operation used Chris@102: /// Chris@102: // \remark Taken from Knuth, The Art of Computer Programming, Volume 2: Chris@102: // Seminumerical Algorithms, Section 4.6.3 Chris@102: template Chris@102: typename boost::enable_if, T>::type Chris@102: power (T x, Integer n, Operation op) { Chris@102: T y = identity_operation(op); Chris@102: if (n == 0) return y; Chris@102: while (true) { Chris@102: if (n % 2 == 1) { Chris@102: y = op(x, y); Chris@102: if (n == 1) Chris@102: return y; Chris@102: } Chris@102: n = n / 2; Chris@102: x = op(x, x); Chris@102: } Chris@102: return y; Chris@102: } Chris@102: Chris@102: }} Chris@102: Chris@102: #endif // BOOST_ALGORITHM_HPP