math Common summations in computer science Fencepost Sums
Example
Here we consider sums of the form
a + b + a + b + ... a
vs.
a + b + a + b + ... b
To visualize these sums, imagine a section of fence alternating between posts and rails. Three scenarios are possible.
-
Imagine a section of fence with posts at each end, connected by rails. n rails require n+1 posts. Conversely p posts are joined by p-1 rails.
|—|—|—|
-
Imagine a section of fence with a post at one end, but but an open rail at the other. n rails require n posts.
|—|—|—
or
—|—|—|
-
Imagine a section of fence with open rails at both ends. n rails require n-1 posts. Conversely, p posts are joined by p+1 rails.
—|—|—
Calculations like this arise in situations such as the layout of graphical objects where the sizes of the objects must be summed and the spaces between the objects must also be summed. In such situations it is important to be aware of whether or not the intent is to have spaces at each end.
The total width of such a fence will always be:
(width of post) x (number of posts) + (width of rail) x (number of rails)
But caution must be used in computing the number of posts and number of rails so as to avoid a so-called off-by-one error. Mistakes of this kind are common.
