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