Elephant in Cairo

An elephant in Cairo is a term used in computer programming to describe a piece of data inserted at the end of a search space, which matches the search criteria, in order to make sure the search algorithm terminates; it is a humorous example of a sentinel value. The term derives from a humorous essay circulated on the Internet and published in Byte magazine in September 1989 that described how various professions would go about hunting elephants.[1]

Algorithm

When hunting elephants, the article describes programmers as following this algorithm:[2]

  1. Go to Africa.
  2. Start at the Cape of Good Hope [traditionally believed to be Africa's southernmost point, which is actually Cape Agulhas].
  3. Work northward in an orderly manner, traversing the continent alternately east and west,
  4. During each traverse pass:
    • Catch each animal seen.
    • Compare each animal caught to a known elephant.
    • Stop when a match is detected.

This algorithm has a bug, namely a bounds checking error: if no elephants are found, the programmer will continue northwards and end up in the Mediterranean sea, causing abnormal termination by drowning.

Thus experienced programmers modify the above algorithm by placing a known elephant in Cairo to ensure that the algorithm will terminate.[3] The modified algorithm is therefore as follows:

  1. Go to Africa.
  2. Put an elephant in Cairo.
  3. Start at the Cape of Good Hope.
  4. Work northward in an orderly manner, traversing the continent alternately east and west,
  5. During each traverse pass:
    • Catch each animal seen.
    • Compare each animal caught to a known elephant.
    • Stop when a match is detected.
  6. If you are in Cairo, then there are no elephants in Africa (other than the one you placed there).

See also

References

  1. Olsen, Peter C. "Pachydermic Personnel Prediction", Byte, Stop Bit column, September 1989.
  2. Greenspun, Philip. "How to Hunt Elephants". Retrieved 2 February 2016.
  3. Steuben, Michael (1998). Twenty Years Before the Blackboard. Cambridge University Press. p. 62. ISBN 9780883855256.

External links

This article is issued from Wikipedia - version of the 9/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.