Maintain x*x in C++

Question

I have the following while-loop

uint32_t x = 0;
while(x*x < STOP_CONDITION) {
    if(CHECK_CONDITION) x++
    // Do other stuff that modifies CHECK_CONDITION
}

The STOP_CONDITION is constant at run-time, but not at compile time. Is there are more efficient way to maintain x*x or do I really need to recompute it every time?

Answer 1

Note: According to the benchmark below, this code runs about 1 -- 2% slower than this option. Please read the disclaimer included at the bottom!

---

In addition to Tamas Ionut's answer, if you want to maintain STOP_CONDITION as the actual stop condition and avoid the square root calculation, you could update the square using the mathematical identity

(x + 1)² = x² + 2x + 1

whenever you change x:

uint32_t x = 0;
unit32_t xSquare = 0;
while(xSquare < STOP_CONDITION) {
    if(CHECK_CONDITION) {
      xSquare += 2 * x + 1;
      x++;
    }
    // Do other stuff that modifies CHECK_CONDITION
}

Since the 2*x + 1 is just a bit shift and an increment, the compiler should be able to optimize this fairly well.

Disclaimer: Since you asked "how can I optimize this code" I answered with one particular way to possibly make it faster. Whether the double + increment is actually faster than a single integer multiplication should be tested in practice. Whether you should optimize the code is a different question. I assume you have already benchmarked the loop and found it to be a bottleneck, or that you have a theoretical interest in the question. If you are writing production code that you wish to optimize, first measure the performance and then optimize where needed (which is probably not the x*x in this loop).