fencepost error

2 definitions found

fencepost error - Free On-line Dictionary of Computing (26 May 2007) :

  fencepost error
  lamp-post error
  
     1. (Rarely "lamp-post error") A problem with the discrete
     equivalent of a boundary condition, often exhibited in
     programs by iterative loops.  From the following problem: "If
     you build a fence 100 feet long with posts 10 feet apart, how
     many posts do you need?"  (Either 9 or 11 is a better answer
     than the obvious 10).
  
     For example, 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.
  
     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 it's not a fencepost error.  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.
  
     2. (Rare) An error induced by unexpected regularities in input
     values, which can (for instance) completely thwart a
     theoretically efficient binary tree or hash coding
     implementation.  The error here involves the difference
     between expected and worst case behaviours of an algorithm.
  
     [Jargon File]
  
     (1994-12-01)
  

fencepost error - Jargon File (4.4.4, 14 Aug 2003) :

  fencepost error
   n.
  
     1. [common] A problem with the discrete equivalent of a boundary
     condition, often exhibited in programs by iterative loops. From the
     following problem: "If you build a fence 100 feet long with posts 10
     feet apart, how many posts do you need?" (Either 9 or 11 is a better
     answer than the obvious 10.) For example, 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. A program that used the `obvious'
     formula would have a fencepost error in it. See also zeroth and
     off-by-one error, 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 it's
     not a fencepost error. 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.
  
     2. [rare] An error induced by unexpected regularities in input
  values,
     which can (for instance) completely thwart a theoretically efficient
     binary tree or hash table implementation. (The error here involves
  the
     difference between expected and worst case behaviors of an
  algorithm.)