I have this loop that runs in O(end - start) and I would like to replace it with something O(1).
If "width" wouldn't be decreasing, it would be pretty 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 have positive values
Do you want something like z = 2 * width * (start - end) / 3 + (start - end) % 3? (not quite right, but close enough to get you on the right track.
Notice that
width == initial_width - (i - start)
so the 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.
It's probably easiest to think of this as the sum of two separate series, one for when i%3 = 1 and the other for when i%3=2. Alternatively, you could figure it as the sum for all values of i minus the sum for i%3=0. For the sake of argument, let's look at the first half of the latter approach: summing all the values of width.
In this case, width will start at some initial value, and each iteration its value will be reduced by 1. In the last iteration, its value will have been reduced by (end-start). Perhaps it's easiest to think of it as a triangle. Just to keep things simple, we'll use small numbers -- we'll start with width = 5, start = 1 and end = 5. Perhaps it's easiest to draw a diagram:
Values of width:
*
**
***
****
*****
What we're really looking for is the area of that triangle -- which is a pretty well-known formula from elementary geometry -- 1/2ab, where a and b are the lengths of the two sides (in this case, defined by the initial value of width and end-start). That assumes it really is a triangle though -- i.e. that it decrements down to 0. In reality, there's a good chance that we're dealing with a truncated triangle -- but the formula for that is also well known (1/2a1b + 1/2a2b, where the a's are the heights of the right and left sides, and b is the width.
This isn't a full answer, but you should notice 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 a value that from LSB up has two bits set, one bit cleared, two bits set, one bit cleared (0x...011011011) could be used to compute where the %3 is 0.
R = k - (k & 0x...011011011); // This is the series 3 + (3 << 3) + (3 << 6) ...
z = (R * width)>>x; // I think.
Just something to try. I've probably made some kind of mistake.
As someone else mentioned, this is probably easiest to think of 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)
Which means the sum of one of them is really ... (2x+3N)(N+1)/2
This equation would need to be applied for both series. It is possible that N would be different for both.
Thus, all you have to do is determine your starting point, and the number of items in the series. That shall be left as an exercise for the student.
Hope this helps.
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 of (i-start)s when (i%3 > 0) for i=start to end.
result will give the sum of widths added to z.
The closed form of sum(i=1 ... n) i is (n)(n+1)/2. You should be able to use this with a little algebra to find a closed form that provides you with the result you're looking for.