Skip to content

Commit d473435

Browse files
mclowmclow
committed
Added more general power functionality as requested by Sean Parent. Also added enable_if to make sure the exponent is an integral type.
1 parent 85adf4c commit d473435

4 files changed

Lines changed: 91 additions & 31 deletions

File tree

‎include/boost/algorithm/algorithm.hpp‎

Lines changed: 53 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -18,32 +18,68 @@
1818
#define BOOST_ALGORITHM_HPP
1919

2020
#include <boost/utility/enable_if.hpp> // for boost::disable_if
21+
#include <boost/type_traits/is_integral.hpp>
2122

2223
namespace boost { namespace algorithm {
2324

25+
template <typename T>
26+
T identity_operation ( std::multiplies<T> ) { return T(1); }
27+
28+
template <typename T>
29+
T identity_operation ( std::plus<T> ) { return T(0); }
30+
31+
2432
/// \fn power ( T x, Integer n )
2533
/// \return the value "x" raised to the power "n"
2634
///
2735
/// \param x The value to be exponentiated
28-
/// \param n The exponent
36+
/// \param n The exponent (must be >= 0)
2937
///
30-
// \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
31-
// Seminumerical Algorithms, Section 4.6.3
38+
// \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
39+
// Seminumerical Algorithms, Section 4.6.3
3240
template <typename T, typename Integer>
33-
T power (T x, Integer n) {
34-
T y = 1; // Should be "T y{1};"
35-
if (n == 0) return y;
36-
while (true) {
37-
if (n % 2 == 1) {
38-
y = x * y;
39-
if (n == 1)
40-
return y;
41-
}
42-
n = n / 2;
43-
x = x * x;
44-
}
45-
return y;
46-
}
41+
typename boost::enable_if<boost::is_integral<Integer>, T>::type
42+
power (T x, Integer n) {
43+
T y = 1; // Should be "T y{1};"
44+
if (n == 0) return y;
45+
while (true) {
46+
if (n % 2 == 1) {
47+
y = x * y;
48+
if (n == 1)
49+
return y;
50+
}
51+
n = n / 2;
52+
x = x * x;
53+
}
54+
return y;
55+
}
56+
57+
/// \fn power ( T x, Integer n, Operation op )
58+
/// \return the value "x" raised to the power "n"
59+
/// using the operaton "op".
60+
///
61+
/// \param x The value to be exponentiated
62+
/// \param n The exponent (must be >= 0)
63+
/// \param op The operation used
64+
///
65+
// \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
66+
// Seminumerical Algorithms, Section 4.6.3
67+
template <typename T, typename Integer, typename Operation>
68+
typename boost::enable_if<boost::is_integral<Integer>, T>::type
69+
power (T x, Integer n, Operation op) {
70+
T y = identity_operation(op);
71+
if (n == 0) return y;
72+
while (true) {
73+
if (n % 2 == 1) {
74+
y = op(x, y);
75+
if (n == 1)
76+
return y;
77+
}
78+
n = n / 2;
79+
x = op(x, x);
80+
}
81+
return y;
82+
}
4783

4884
}}
4985

‎test/Jamfile.v2‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@ alias unit_test_framework
3030
# Misc tests
3131
[ run clamp_test.cpp unit_test_framework : : : : clamp_test ]
3232
[ run power_test.cpp unit_test_framework : : : : power_test ]
33+
[ compile-fail power_fail1.cpp : : : : ]
3334

3435
# Cxx11 tests
3536
[ run all_of_test.cpp unit_test_framework : : : : all_of_test ]

‎test/power_fail1.cpp‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/*
2+
Copyright (c) Marshall Clow 2014.
3+
4+
Distributed under the Boost Software License, Version 1.0. (See accompanying
5+
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6+
7+
For more information, see http://www.boost.org
8+
*/
9+
10+
#include <iostream>
11+
12+
#include <boost/config.hpp>
13+
#include <boost/algorithm/algorithm.hpp>
14+
15+
#define BOOST_TEST_MAIN
16+
#include <boost/test/unit_test.hpp>
17+
18+
namespace ba = boost::algorithm;
19+
20+
BOOST_AUTO_TEST_CASE( test_main )
21+
{
22+
// Second argument must be an integral value
23+
BOOST_CHECK ( ba::power(1, 1.0) == 1);
24+
}

‎test/power_test.cpp‎

Lines changed: 13 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -15,22 +15,21 @@
1515
#define BOOST_TEST_MAIN
1616
#include <boost/test/unit_test.hpp>
1717

18-
#include <string>
19-
#include <vector>
20-
#include <list>
21-
2218
namespace ba = boost::algorithm;
2319

2420
BOOST_AUTO_TEST_CASE( test_main )
2521
{
26-
BOOST_CHECK ( ba::power(0, 0) == 1);
27-
BOOST_CHECK ( ba::power(5, 0) == 1);
28-
BOOST_CHECK ( ba::power(1, 1) == 1);
29-
BOOST_CHECK ( ba::power(1, 4) == 1);
30-
BOOST_CHECK ( ba::power(3, 2) == 9);
31-
BOOST_CHECK ( ba::power(2, 3) == 8);
32-
BOOST_CHECK ( ba::power(3, 3) == 27);
33-
BOOST_CHECK ( ba::power(2, 30) == 0x40000000);
34-
BOOST_CHECK ( ba::power(5L, 10) == 3125*3125);
35-
BOOST_CHECK ( ba::power(18, 3) == 18*18*18);
22+
BOOST_CHECK ( ba::power(0, 0) == 1);
23+
BOOST_CHECK ( ba::power(5, 0) == 1);
24+
BOOST_CHECK ( ba::power(1, 1) == 1);
25+
BOOST_CHECK ( ba::power(1, 4) == 1);
26+
BOOST_CHECK ( ba::power(3, 2) == 9);
27+
BOOST_CHECK ( ba::power(2, 3) == 8);
28+
BOOST_CHECK ( ba::power(3, 3) == 27);
29+
BOOST_CHECK ( ba::power(2, 30) == 0x40000000);
30+
BOOST_CHECK ( ba::power(5L, 10) == 3125*3125);
31+
BOOST_CHECK ( ba::power(18, 3) == 18*18*18);
32+
33+
BOOST_CHECK ( ba::power(3,2) == ba::power(3,2, std::multiplies<int>()));
34+
BOOST_CHECK ( ba::power(3,2, std::plus<int>()) == 6);
3635
}

0 commit comments

Comments
 (0)