[Boost-commit] svn:boost r64558 - sandbox/SOC/2010/quasi_random/boost/random

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;
 }