Replace for the cycle with the formula

Question

I have this loop that works in O (end-start), and I would like to replace it with something O (1).
If the "width" were not reduced, it would be quite simple.

for (int i = start; i <= end; i++, width--) if (i % 3 > 0) // 1 or 2, but not 0 z += width; 

start, end and width are positive

Answer 1

note that

 width == initial_width - (i - start) 

therefore, summation can be rewritten as

  end ————— \ (initial_width + start - i) / ————— i=start i mod 3 ≠ 0 end ⌊end/3⌋ ————— ————— == \ (initial_width + start - i) —— \ (initial_width + start - 3j) / / ————— ————— i=start j=⌈start/3⌉ 

The rest should be simple.

Answer 2

As already mentioned, this is perhaps the easiest to consider as the sum of two series.

  x x+3 x+6 ... x+3N + x+3N x+3(N-1) x+3(N-2) ... x ----------------------------------- 2x+3N 2x+3N 2x+3N ... 2x+3N 

The above can be simplified to (2x + 3N) (N + 1)

This means that the sum of one of them is really ... (2x + 3N) (N + 1) / 2

This equation must be applied to both series. It is possible that N will be different for both.

Thus, all you have to do is determine the starting point and the number of elements in the series. This should be considered by the student.

Hope this helps.

Answer 3

It is probably easiest to think of this as the sum of two separate series, one for which i%3 = 1 and the other for i%3=2 . Alternatively, you can represent it as the sum for all i values ​​minus the sum for i%3=0 . For argumentation, we consider the first half of the last approach: we summarize all the width values.

In this case, width will start from some initial value, and each iteration its value will be reduced by 1. In the last iteration, its value will be reduced by (end-start) . Perhaps the easiest way to think of it is as a triangle. Just to make everything simple, we will use small numbers - we will start with width = 5, start = 1 and end = 5. Perhaps the easiest way is to draw a diagram:

Width Values:

 * ** *** **** ***** 

What we are really looking for is the area of ​​this triangle - a fairly well-known formula from elementary geometry - 1 / 2ab, where a and b are the lengths of two sides (in this case, determined by the initial value of width and end-start ). This suggests that it is indeed a triangle, though, i.e. That it decreases to 0. In fact, there is a good chance that we are dealing with a truncated triangle, but the formula for this is also well known (1 / 2a ₁ b + 1 / 2a ₂ b, where a are the heights of the right and left sides , and b is the width.

Answer 4

I came up with this ugly method:

 int start; // = some number int end; // = ... int initialwidth; // = ... int each = (end+1)/3 - (start-1)/3 - 1; int loop = 2*(3-(start+2)%3)+1; int total = each*loop + 3*each*(each-1) + (start%3==1) + (end-start)*(end%3==1); int result = -total + initialwidth*(1 + end - start - end/3 + (start-1)/3); 

total will give the sum (i-start) s when (i% 3> 0) for i = it starts to end.

Result

will give the sum of the width added to z.

Answer 5

The closed form of the sum (i = 1 ... n) i is equal to (n) (n + 1) / 2. You should be able to use this with little algebra to find a closed form that provides you with the result you are looking for.

Answer 6

Do you want something like z = 2 * width * (start - end) / 3 + (start - end) % 3 ? (Not quite right, but close enough for you to be on the right track.

Answer 7

This is not a complete answer, but you should note that:

 x = end - start; k = ~(-1 << x); // I think (width * k)>>x would be your z except if you didn't have the contidional 

and that the value which of LSB up has two bits, one bit is cleared, two bits are set, one bit is cleared (0x ... 011011011) can be used to calculate where% 3 is 0.

 R = k - (k & 0x...011011011); // This is the series 3 + (3 << 3) + (3 << 6) ... z = (R * width)>>x; // I think. 

Just give it a try. I probably made some kind of mistake.