The fastest calculation of the sum x ^ 5 + x ^ 4 + x ^ 3 ... + x ^ 0 (bitwise?) With x = 16

Question

For a tree layout using cache line reading _next_ cacheline ( reading _next_ cacheline cheap), I need to quickly resolve the address layout. I was able to solve this problem:

 newIndex = nowIndex + 1 + (localChildIndex*X) 

x will be, for example: X = 4 ⁵ + 4 ⁴ + 4 ³ + 4 ² +4, ⁰ .

Note: 4 - branching coefficient. In reality it will be 16, so that is power 2. Should it be useful to use bitwise things?

It would be very bad if we needed a loop to compute X ( performancewise ), etc. like division / multiplication. This attracts an interesting problem, and I could not come up with any good way to calculate it.

With its part of tree traversal, 2 modes are possible: absolute calculation, regardless of previous calculations, and incremental calculation, which begins with the fact that high X is stored in a variable, and then some minimal things done with it at each deeper level of the tree.

Hopefully I was able to clarify what mathematics should do. Not sure if there is a way to do this quickly and without a loop - but maybe someone can come up with a really smart solution. I would like to thank everyone for their help - StackOverflow has been a great teacher for me in the past, and I hope that I can return more in the future as my knowledge grows.

Answer 1

I will answer this in increasing complexity and generality.

• If x is fixed at 16, just use the constant 1118481 . Hooray! (Call him using magic numbers - bad practice)

• If you have several cases known at compile time, use several constants or even define, for example:

   #define X_2 63 #define X_4 1365 #define X_8 37449 #define X_16 1118481 ... 

• If you have several cases known at runtime, initialize and use a lookup table indexed with a metric.

   int _X[MAX_EXPONENT]; // note: give it a more meaningful name :) 

  Initialize it and then just access the known exponent 2 ^ exp at runtime.

   newIndex = nowIndex + 1 + (localChildIndex*_X[exp]); 

• How these values ​​are pre-calculated or how to efficiently calculate them "on the fly": The sum X = x^n + x^(n - 1) + ... + x^1 + x^0 is a geometric series and its final sum:

   X = x^n + x^(n - 1) + ... + x^1 + x^0 = (1-x^(n + 1))/(1-x) 

• On bitwise operations, as Oli Charlworth said, if x is a power of 2 (in binary 0..010..0) x^n also a power of 2, and the sum of different powers of two is equivalent to an OR operation. Thus, we could make an expression like:

  Let exp be an exponent, so x = 2 ^ exp. (For 16, exp = 4). Then,

   X = x^5 + ... + x^1 + x^0 X = (2^exp)^5 + ... + (2^exp)^1 + 1 X = 2^(exp*5) + ... + 2^(exp*1) + 1 

  now bitwise, 2^n = 1<<n

   X = 1<<(exp*5) | ... | 1<<exp | 1 

  In C:

   int X; int exp = 4; //for x == 16 X = 1 << (exp*5) | 1 << (exp*4) | 1 << (exp*3) | 1 << (exp*2) | 1 << (exp*1) | 1; 

• And finally, I can not help but say: if your expression was more complicated and you had to calculate an arbitrary polynomial a_n*x^n + ... + a_1*x^1 + a_0 in x instead of implementing an obvious loop, more A quick way to evaluate a polynomial is using the Horner rule.