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]
- Go to Africa.
- Start at the Cape of Good Hope [traditionally believed to be Africa's southernmost point, which is actually Cape Agulhas].
- Work northward in an orderly manner, traversing the continent alternately east and west,
- 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:
- Go to Africa.
- Put an elephant in Cairo.
- Start at the Cape of Good Hope.
- Work northward in an orderly manner, traversing the continent alternately east and west,
- During each traverse pass:
- Catch each animal seen.
- Compare each animal caught to a known elephant.
- Stop when a match is detected.
- If you are in Cairo, then there are no elephants in Africa (other than the one you placed there).
See also
References
- ↑ Olsen, Peter C. "Pachydermic Personnel Prediction", Byte, Stop Bit column, September 1989.
- ↑ Greenspun, Philip. "How to Hunt Elephants". Retrieved 2 February 2016.
- ↑ Steuben, Michael (1998). Twenty Years Before the Blackboard. Cambridge University Press. p. 62. ISBN 9780883855256.
External links
- Transcript of Stop Bit, Byte, September 1989, p. 404
- List of the other elephant hunting techniques (PDF)