Elephant in Cairo

Last updated

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]

Contents

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).

See also

Related Research Articles

Checksum A small-size datum computed from digital data for detecting transmission errors

A checksum is a small-sized datum derived from a block of digital data for the purpose of detecting errors that may have been introduced during its transmission or storage. By themselves, checksums are often used to verify data integrity but are not relied upon to verify data authenticity.

Cape of Good Hope Headland of Cape Peninsula, South Africa

The Cape of Good Hope is a rocky headland on the Atlantic coast of the Cape Peninsula in South Africa.

Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978. The algorithm is simple to implement and has the potential for very high throughput in hardware implementations. It is the algorithm of the widely used Unix file compression utility compress and is used in the GIF image format.

Big five game African game-hunting species

In Africa, the Big Five game animals are the lion, leopard, rhinoceros, elephant, and Cape buffalo. The term was coined by big-game hunters, and refers to the five most difficult animals in Africa to hunt on foot, but is now also widely used by safari tour operators.

The written history of the Cape Colony in what is now South Africa began when Portuguese navigator Bartolomeu Dias became the first modern European to round the Cape of Good Hope in 1488. In 1497, Vasco da Gama sailed along the whole coast of South Africa on his way to India, landed at St Helena Bay for 8 days, and made a detailed description of the area. The Portuguese, attracted by the riches of Asia, made no permanent settlement at the Cape Colony. However, the Dutch East India Company (VOC) settled the area as a location where vessels could restock water and provisions.

The Lempel–Ziv–Markov chain algorithm (LZMA) is an algorithm used to perform lossless data compression. It has been under development since either 1996 or 1998 by Igor Pavlov and was first used in the 7z format of the 7-Zip archiver. This algorithm uses a dictionary compression scheme somewhat similar to the LZ77 algorithm published by Abraham Lempel and Jacob Ziv in 1977 and features a high compression ratio and a variable compression-dictionary size, while still maintaining decompression speed similar to other commonly used compression algorithms.

rzip is a huge-scale data compression computer program designed around initial LZ77-style string matching on a 900 MB dictionary window, followed by bzip2-based Burrows–Wheeler transform and entropy coding (Huffman) on 900 kB output chunks.

Radix tree data structure that represents a space-optimized trie in which each node that is the only child is merged with its parent

In computer science, a radix tree is a data structure that represents a space-optimized trie in which each node that is the only child is merged with its parent. The result is that the number of children of every internal node is at most the radix r of the radix tree, where r is a positive integer and a power x of 2, having x ≥ 1. Unlike regular trees, edges can be labeled with sequences of elements as well as single elements. This makes radix trees much more efficient for small sets and for sets of strings that share long prefixes.

Frederick Selous British explorer, officer, hunter, and conservationist

Frederick Courteney Selous, DSO, was a British explorer, officer, professional hunter, and conservationist, famous for his exploits in Southeast Africa. His real-life adventures inspired Sir Henry Rider Haggard to create the fictional Allan Quatermain character. Selous was also a friend of Theodore Roosevelt, Cecil Rhodes and Frederick Russell Burnham. He was pre-eminent within a select group of big game hunters that included Abel Chapman and Arthur Henry Neumann. He was the older brother of ornithologist and writer Edmund Selous.

Trophy hunting Hunting of wild animals for recreational purposes

Trophy hunting or sport hunting is hunting of wild game for human recreation. The trophy is the animal or part of the animal kept and usually displayed, to represent the success of the hunt. The game sought is typically a large or impressively ornamented male, such as one having large horns or antlers. Generally, only parts of the animal are kept as trophies and the carcass itself is used for food.

Working animal Animal domesticated, that is kept by the humans and trained to perform tasks

A working animal or draughtanimal is an animal, usually domesticated, that is kept by humans and trained to perform tasks. They may be pets or draft animals trained to achieve certain tasks, such as guide dogs, assistance dogs, draft horses or logging elephants. Most working animals are either service animals or draft animals. They may also be used for milking or herding. Some, at the end of their working lives, may also be used for meat or other products such as leather.

In computer programming, a sentinel value is a special value in the context of an algorithm which uses its presence as a condition of termination, typically in a loop or recursive algorithm.

A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree. Bounding volume hierarchies are used to support several operations on sets of geometric objects efficiently, such as in collision detection and ray tracing.

Recursion (computer science) Use of functions that call themselves (on smaller inputs)

In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

Big-game hunting is the hunting of large game animals for meat, commercially valuable by-products, trophy/taxidermy, or simply just for recreation ("sporting"). The term is often associated with the hunting of Africa's "Big Five" game, and with tigers and rhinoceroses on the Indian subcontinent. Many other species of big game are hunted including kudu, antelope, and hartebeest. Whale, moose, elk, caribou, bison, mule deer, and white-tailed deer are the largest game hunted in North America, where most big-game hunting is conducted today.

<i>Wild Africa</i> television series

Wild Africa is a British nature documentary series created and produced by the BBC. It explores the natural history of the African continent. It was first transmitted on 7 November 2001 on BBC Two in the United Kingdom and comprises six episodes. Each concentrates on a particular environment. The producers use aerial photography and wildlife footage to show how natural phenomena such as seasonal changes influence the patterns of life. Wild Africa was produced by the BBC Natural History Unit and narrated by Fergal Keane.

In computer science, artificial intelligence, and mathematical optimization, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.

Boar hunting hunting activity, specifically for wild boar or feral pigs

Pig hunting is generally the practice of hunting wild boars, but can also extend to feral pigs and peccaries. A full-sized boar is a large, powerful animal, often having sharp tusks which it uses to defend itself. Boar hunting has often been a test of bravery.

Jackal coursing

Jackal coursing involves the pursuit of jackals with dogs.

Computer humour is humour on the subject of computers or their users.

References

  1. 1 2 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.