This "Bresenham Counter" implementation uses the Bresenham line drawing algorithm to obtain N evenly distributed integer values from the integer range [0,R] using simple integer arithmetic (no multiply/divide or floating point each iteration).
After performing some rather unscientific tests on my laptop I have found this implementation to be 3.75 times faster than performing an integer multiplication/division each iteration and 6.75 times faster then doing a floating point (double) addition and integer conversion each iteration. DISCLAIMER: Performance gains (if any) will vary from platform to platform.
Here is the implementation:
template <typename T>
class bresenham_counter
{
/* operator T() returns x[0..N-1] = 0 .. R, i.e. x[n] = (R / (N-1)) * n, without
using floating point or multiplication/division each iteration */
public:
bresenham_counter(T range, T number) :
dx(number-1),
dy(dx > 0 ? range % dx : 0),
d(2*dy - dx), incrE(2*dy), incrNE(2*(dy-dx)),
incrCounter(dx > 0 ? range / dx : 0),
incrCounterPlus1(dx > 0 ?
incrCounter+1 : 0),
counter(0) {}
operator T()
{
if (d <= 0)
{
d += incrE;
T v = counter;
counter += incrCounter;
return v;
}
else
{
d += incrNE;
T v = counter;
counter += incrCounterPlus1;
return v;
}
}
private:
T dx, dy, d, incrE, incrNE;
T incrCounter;
T incrCounterPlus1;
T counter;
};
Here is an example of usage:
int main()
{
/* output 10 values from the range 0 to 255 */
bresenham_counter<int> bc(255, 10);
for (int i = 0; i < 10; ++i)
{
int value = bc;
std::cout << value << std::endl;
}
return 0;
}
The output of which is:
0
28
57
85
113
142
170
198
227
255
To support the more general range [Q,R] where Q and R can be positive or negative and/or R < Q simply add the following constructor to the above implementation:
bresenham_counter(T rangeStart, T rangeEnd, T number) :
dx(number-1),
dy(dx > 0 ? rangeEnd > rangeStart ?
(rangeEnd - rangeStart) % dx : (rangeStart - rangeEnd) % dx : 0),
d(2*dy - dx), incrE(2*dy), incrNE(2*(dy-dx)),
incrCounter(dx > 0 ? (rangeEnd - rangeStart) / dx : 0),
incrCounterPlus1(dx > 0 ? rangeEnd > rangeStart ?
incrCounter+1 : incrCounter-1 : 0),
counter(rangeStart) {}
Here is an example of usage:
int main()
{
/* output 16 values from the range 7 to -42 */
bresenham_counter<int> bc(7, -42, 16);
for (int i = 0; i < 16; ++i)
{
int value = bc;
std::cout << value << std::endl;
}
return 0;
}
The output of which is:
7
4
0
-3
-6
-9
-13
-16
-19
-22
-26
-29
-32
-35
-39
-42
Click here for an alternative implementation which is easier on the eyes but slightly slower than this implementation due to the presence of an extra subtraction.