Re:The Beauty of Bresenham's Algorithm
by vanderZwan on Wednesday August 23, 2017 @07:49AM
(#15080647)
> calculating x * p/k from scratch whenever x changes doesn't always work either. You can still get significan rounding errors if the intermediate calculation of x * p is such a large number that it barely fits in a floating point.
Too late to edit that accidental markdown, so replying to myself
EDIT: I just realised I'm not actually answering your pixels question, but a more generalised question of "when would we want to use this integer arithmetic method instead of floating point multiplication and division?"
As much as the rounding error of repeated addition matters - especially with cumulative addition. The comment by white-flame only regards this from the point of view of pixels, but there are many other applications where Bresenham's algorithm is the best solution. As described on Roman Black's website from 2001:
> Bresenham's Algorithm is a system where 2 imperfect periods can be alternated to produce an average that matches any "perfect" period.
https://www.romanblack.com/one_sec.htm
I probably don't have to convince you that this can still be a serious issue in embedded systems. The most obvious use-case would be long-running code where cumulative errors add up. A famous example of this going horribly wrong is the Patriot Missile disaster:
> It turns out that the cause was an inaccurate calculation of the time since boot due to computer arithmetic errors. Specifically, the time in tenths of second as measured by the system's internal clock was multiplied by 1/10 to produce the time in seconds. This calculation was performed using a 24 bit fixed point register. In particular, the value 1/10, which has a non-terminating binary expansion, was chopped at 24 bits after the radix point. The small chopping error, when multiplied by the large number giving the time in tenths of a second, led to a significant error. Indeed, the Patriot battery had been up around 100 hours, and an easy calculation shows that the resulting time error due to the magnified chopping error was about 0.34 seconds.
http://www-users.math.umn.edu/~arnold/disasters/patriot.html
Bresenham's Algorithm avoids this rounding error altogether (but it only works as long as you have a fixed numerator/denominator ratio - or if you really push it one denominator and a set of numerators).
EDIT2: Also, this does not just apply to repeat addition: calculating xp/k from scratch whenever x changes doesn't always work either. You can still get significan rounding errors if the intermediate calculation of xp is such a large number that it barely fits in a floating point.