Calculate the number of iterations of a cycle with a varying increment

Question

for (; i < limit; i += x) { x += 100; } 

Is there an elegant solution to calculate i and x without using a loop construct?

My thoughts:

I can use the popular Gauss summation formula 1+2+3+4+...+n = (n*(n+1))/2 and binary search to reduce complexity from O (N) to O (log N) .

 Assume i = 0, x = 0 then: i = 0*100 + 1*100 + 2*100 + 3*100 + ... + (n-1)*100 = ((n-1)*n)/2*100 if (i != 0 && x != 0) then: i = i + x+0*100 + x+1*100 + x+2*100 + ... + x+(n-1)*100 = i+x*n + ((n-1)*n)/2*100 Thus (i < limit) = (i+x*n+((n-1)*n)/2*100 < limit) 

Now use some kind of binary search to find the largest n that satisfies the above inequality.

 if (i < limit) for (n = 1; i+x*n+((n-1)*n)/2*100 < limit; n -= j, n += 1) for (j = 1; i+x*n+((n-1)*n)/2*100 < limit; n += j, j += j); 

Now that I have found the number of iterations n original loop, i and x can be calculated using:

 i += x*n+((n-1)*n)/2*100 x += 100*n 

Any suggestions? Is there a faster solution to O (1)?

O (1) solution:

 const int d = 100; while (i < limit) { i += x; x += d; } 

With Daniel, answer how to calculate the number of iterations n , and then i and x in steps O (1). i = i+x*n+((n-1)*n)/2*d (see above), so we can now solve:

 i < limit = i+x*n+(n*(n+1))/2*d < limit = d*n^2 + (2*xd)*n - 2*(limit-i) < 0 

The above formula is a quadratic inequality and can be solved using a quadratic formula :

 (-b ± (b^2-4ac)^0.5) / 2a 

Thus, the number of iterations n is equal to:

 a = d b = 2*xd c = -2*(limit-i) n = ceil((-b + sqrt(b*b-4*a*c)) / (2*a)) 

Now that we have found the number of iterations n initial while (for) loop, we can calculate i and x using two formulas (see above):

 i += x*n+((n-1)*n)/2*d x += d*n 

I tested these formulas with a simple C program and they give the same results as the while (for) loop.

Answer 1

This is a quadratic inequality, so you can solve it in O (1) if you can calculate the square roots in O (1). Depending on the types of numbers involved, which may or may not be possible.

If i >= limit at the beginning, you trivially have no iterations, n = 0 . Therefore, suppose that i < limit at the beginning and suppose that x increases by a fixed positive value d at each step.

The inequality you want to solve, then

 n*(n+1)*d/2 + n*x >= limit - i 

The solution by standard methods gives

 n >= sqrt( (1/2 + x/d)^2 + 2*(limit - i)/d ) - (1/2 + x/d) 

Smallest n > 0 with this property

 ceiling( sqrt( (1/2 + x/d)^2 + 2*(limit - i)/d ) - (1/2 + x/d) ) 

If all quantities can be represented with sufficient accuracy as double s, that is, the calculation of O (1). However, if any of the values ​​is large, it is possible that the floating-point calculation does not work a bit. Then you have to adapt. For moderate sizes, one step is sufficient.

But if all values ​​are of moderate size, the binary search is also almost O (1) - logarithms are limited and quite small then - and can be faster.