In computer programming, a fencepost error – rarely called a "lamp-post error" – is a computer bug involving the discrete equivalent of a boundary condition, often exhibited in programs by iterative loops. This can also occur in a mathematical context, but is not usually named.
The following problem illustrates the error:
- "If you build a fence 100 feet long with posts 10 feet apart, how many posts do you need?"
Many people will immediately answer 10, which is incorrect. The fence certainly has 10 sections, but the posts lie at the boundaries of these sections. We can consider each section in turn and place a pole at its left-hand end: thus for each section there is one pole. However, the common error lies in that the end of the final section has not yet been given a pole: this is the 11th.
Conversely, in a row of 10 lamp-posts there are 9 gaps between them.
If the separation is circular, however, there is no "extra fencepost", since the positions for the first and the last post coincide. For example, a fence encompassing a closed square may have 4 posts, and 4 edges between posts.
Consider the subdivision of the surface of the Earth into sections 10 degrees of longitude rsp. latitude apart. The longitudinal divisions (half-circles connecting the poles) will be circularly arranged, and have no "extra fencepost" (36 half-circles produce 36 divisions), while the latitudinal divisions (circles parallel to the equator) are linearly arranged, and do exhibit this effect (19 circles – two with radius 0 – produce 18 divisions).
In computing, suppose you have a long list or array of items, and want to process items m through n; how many items are there? The obvious answer is n−m, but that is off by one; the right answer is n−m+1. The "obvious" formula exhibits a fencepost error. (This is the motivation behind the representation of ranges in computing by half-open intervals: the range from m to n (both inclusive) is very often represented by the range from m (inclusive) to n+1 (exclusive) to avoid fencepost errors.)
See also zeroth and note that not all off-by-one errors are fencepost errors. The game of Musical Chairs involves a catastrophic off-by-one error where n people try to sit in n−1 chairs, but this is not a fencepost error (see also pigeonhole principle). Fencepost errors come from counting things rather than the spaces between them, or vice versa, or by neglecting to consider whether one should count one or both ends of a row.
A rare secondary meaning is an error induced by unexpected regularities in input values, which can (for instance) completely thwart a theoretically efficient binary tree or hash function implementation. The error here involves the difference between expected and worst case behaviours of an algorithm.
An earlier version of this article was based on fencepost error at FOLDOC, used with permission.