Elephant in Cairo

An elephant in Cairo is a term used in computer programming to describe a piece of data that matches the search criteria purposefully inserted at the end of a search space, 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 that was published in Byte magazine on September 1989, describing how various professions would go about hunting elephants.[1]

Algorithm

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

  1. Go to Africa.
  2. Start at the Cape of Good Hope.[2]
  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).
gollark: They had designed ARM CPUs for ages for their phones. Recently they got good enough and/or Intel annoyed them enough that they switched over.
gollark: ARM is an instruction set. "Traditional CPU[s]" use the x86 instruction set. People argue a lot over which design is best but broadly speaking there doesn't seem to be *that* much difference, although x86 has some advantages like I think greater code density and downsides like variable length instructions being annoying to decode.
gollark: That's not a very valid comparison. But Apple's cores are somewhat better than available x86 ones.
gollark: Apparently they did lose most of their CPU design team to some other company recently, so who knows.
gollark: It's really annoying to me that you can only get the best CPUs with Apple's ridiculous ecosystem and design.

See also
  • Elephant test

References
  1. Olsen, Peter C. (September 1989), "Pachydermic Personnel Prediction", Stop Bit, Byte, p. 404
  2. The Cape of Good Hope has been traditionally believed to be Africa's southernmost point, but that is actually Cape Agulhas.
  3. Steuben, Michael (1998). Twenty Years Before the Blackboard. Cambridge University Press. pp. 62. ISBN 9780883855256.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.