Subject: [Boost-commit] svn:boost r64558 - sandbox/SOC/2010/quasi_random/boost/random
From: jvd_at_[hidden]
Date: 2010-08-03 05:14:15
Author: qrng
Date: 2010-08-03 05:14:12 EDT (Tue, 03 Aug 2010)
New Revision: 64558
URL: http://svn.boost.org/trac/boost/changeset/64558
Log:
Exponentiation unrolled after having done the performance tests. Note, that overflows in base do not matter
much.
Text files modified:
sandbox/SOC/2010/quasi_random/boost/random/faure.hpp | 25 ++++++++++++-------------
1 files changed, 12 insertions(+), 13 deletions(-)
Modified: sandbox/SOC/2010/quasi_random/boost/random/faure.hpp
==============================================================================
--- sandbox/SOC/2010/quasi_random/boost/random/faure.hpp (original)
+++ sandbox/SOC/2010/quasi_random/boost/random/faure.hpp 2010-08-03 05:14:12 EDT (Tue, 03 Aug 2010)
@@ -72,24 +72,23 @@
return ilog;
}
-// Implements exponentiation by squaring, for p > ~4 this is computationally
-// more efficient than naïvely multiplying the base with itself repeatedly.
+// Implements unrolled exponentiation by squaring. For p > ~4 this is computationally
+// more efficient than naively multiplying the base with itself repeatedly.
// In erroneous situations, e.g., integer_pow(0, 0) the function returns 1
// and does not report the error. This is the intended behavior.
+inline std::size_t mdelta(std::size_t base, std::size_t p)
+{
+ return (p & 1) * base + !(p & 1); // (p & 1) ? base : 1
+}
+
inline std::size_t integer_pow(std::size_t base, std::size_t p)
{
std::size_t result = 1;
- for( ; p != 0; p >>= 1, base *= base )
- {
- // A typical way to implement the multiplication
- // would be something like this:
- // if( p & 1 )
- // result *= base;
- // Apart from being simple this method, however,
- // does not have a lot of other advantages, it is not, especially,
- // friendly to CPU branch prediction routines.
- std::size_t k = (p & 1); // k in {0,1}
- result *= (k * base + !k);
+ for( ; p != 0; p >>= 1, base *= base ) {
+ result *= mdelta(base, p);
+ result *= mdelta(base *= base, p >>= 1);
+ result *= mdelta(base *= base, p >>= 1);
+ result *= mdelta(base *= base, p >>= 1);
}
return result;
}