patternMinor
Why are division/floating points inefficient in comparison to integer addition/multiplication/subtraction?
Viewed 0 times
whydivisionmultiplicationarefloatingpointsadditionsubtractioninefficientcomparison
Problem
Why does Bresenham's line algorithm eliminate dy/dx division and the multiplication of that (potentially floating point) number?
Solution
Multiplication can inherently be computed faster than division because it parallelizes better.
If you recall the multiplication and division methods of written calculation, they work by successive additions or subtractions, with shifts. Anyway, in a multiplication you can multiply the multiplicand by all digits of the multiplier simultaneously, and add the results. On the opposite, in division you have to wait until a subtraction has been performed to decide the next digit of the quotient, and the approach is much more serial.
ALU designers are working wonders to implement fast divisors, but they never reach the performance of multipliers.
In the old days, processors even had no hardware divisors at all and divisions were performed in software, orders of magnitude slower, which incited people to avoid divisions by all means.
If you look at Bresenham's algorithm, it actually computes points on a line using the standard line equation $$y=\frac{\Delta_y}{\Delta_x}x$$ for increasing integers $x$ (width a slope not exceeding $1$).
More precisely, to cope with the discrete nature of the raster, the $y$ coordinate needs to be truncated or rounded,
$$y=\left\lfloor\frac{\Delta_y}{\Delta_x}x+\epsilon\right\rfloor=\left\lfloor\frac{\Delta_yx+\Delta_x\epsilon}{\Delta_x}\right\rfloor,$$ where $\epsilon$ can be $0$ or $\frac12$.
The trick of Bresenham is to avoid performing the division on every incrementation of $x$, but instead keep the value of the quotient and remainder updated, which costs only a comparison and one or two additions (either add $\Delta_y$ to the remainder, or increment the quotient and add $\Delta_y-\Delta_x$ to the remainder).
When the line is sufficiently long, it makes sense to compare this with the one-time computation of the slope in fixed-point arithmetic, followed by successive additions and rounding. What you lose by performing a division can be regained by avoiding the conditional branch.
$$y=\left\lfloor\frac{px+e}{2^n}\right\rfloor$$ where $p=[2^n\Delta_y/\Delta_x]$ and $e=[2^n\epsilon]$. The "division" is implemented with a fast shift.
If you recall the multiplication and division methods of written calculation, they work by successive additions or subtractions, with shifts. Anyway, in a multiplication you can multiply the multiplicand by all digits of the multiplier simultaneously, and add the results. On the opposite, in division you have to wait until a subtraction has been performed to decide the next digit of the quotient, and the approach is much more serial.
ALU designers are working wonders to implement fast divisors, but they never reach the performance of multipliers.
In the old days, processors even had no hardware divisors at all and divisions were performed in software, orders of magnitude slower, which incited people to avoid divisions by all means.
If you look at Bresenham's algorithm, it actually computes points on a line using the standard line equation $$y=\frac{\Delta_y}{\Delta_x}x$$ for increasing integers $x$ (width a slope not exceeding $1$).
More precisely, to cope with the discrete nature of the raster, the $y$ coordinate needs to be truncated or rounded,
$$y=\left\lfloor\frac{\Delta_y}{\Delta_x}x+\epsilon\right\rfloor=\left\lfloor\frac{\Delta_yx+\Delta_x\epsilon}{\Delta_x}\right\rfloor,$$ where $\epsilon$ can be $0$ or $\frac12$.
The trick of Bresenham is to avoid performing the division on every incrementation of $x$, but instead keep the value of the quotient and remainder updated, which costs only a comparison and one or two additions (either add $\Delta_y$ to the remainder, or increment the quotient and add $\Delta_y-\Delta_x$ to the remainder).
When the line is sufficiently long, it makes sense to compare this with the one-time computation of the slope in fixed-point arithmetic, followed by successive additions and rounding. What you lose by performing a division can be regained by avoiding the conditional branch.
$$y=\left\lfloor\frac{px+e}{2^n}\right\rfloor$$ where $p=[2^n\Delta_y/\Delta_x]$ and $e=[2^n\epsilon]$. The "division" is implemented with a fast shift.
Context
StackExchange Computer Science Q#48525, answer score: 5
Revisions (0)
No revisions yet.