The Tortoise, the Hare, and 50000 Ants

A parallel algorithm breaks a large piece of work into smaller units and solves those units at the same time. The algorithm does this by distributing the work over multiple CPUs or cores within a CPU.

"I want a rematch," screamed the hare.

"Not today," answered the turtle, "I am still tired from our race. It would not be fair."

"But… I should have won," argued the hare. "I want a rematch."

"I will race you," said a tiny voice. The hare looked around, but could not find the speaker.

"Down here," added the voice. The hare looked down and found an ant staring back at him.

"You?" the hare asked suspiciously. "You are just an ant."

"Yes," answered the ant. "I am an ant, and I would like to race you. If the turtle can win, I believe that I can too."

The hare scoffed.

"Okay," replied the hare. "I will race you. Let's make it 5,000 meters. Can you even walk that far?"

The ant thought for a moment. "That is a long way for someone as small as me. I am not sure that my legs could make it. Perhaps I could split the work with my family members. We could each race part of the way."

"Of course," replied the hare, "I am not afraid of a thousand ants."

The turtle looked at the hare in surprise. Surely, the hare had learned the price of arrogance already.

"But 5,000 meters will still take us a very long time," continued the ant. "We will be running for days. The crowd will want to see everyone finish. Perhaps my family could each run their leg of the race at the same time."

"Yes," answered the hare. "That way I will not have to wait for days to see the look on your faces when you lose."

The turtle's jaw dropped. "Really?" he asked.

The hare did not respond. He busied himself with a short warm-up jog.

Meanwhile, the ant scurried off to fetch his family. A total of 50,000 ants agreed to each run a 10 centimeter leg of the race. They lined up carefully at the start.

The turtle shuffled down the track 10 centimeters and drew a finish line with a stick. "The race is over when the hare finishes one lap and crosses the original finish line OR the last of the ants crosses this finish line. Either way a total of 5,000 meters will be run."

The turtle looked at the hare and waited for this to sink in. The hare continued stretching his legs -- there would be no rests during this race.

"On your mark," announced the turtle.

"Get set."

The hare and 50,000 ants tensed.

"Go."

The hare speed away from the line, kicking little tufts of dirt behind him as he ran. In contrast, the 50,000 ants poked along. Each pebble was a formidable obstacle, and their finish line loomed in the distance. The slowest ant, Geoffrey, lagged nearly an inch behind the leader.

Still, the ants were finished in under a minute.

As the hare rounded the final bend, he could barely hear the chorus of ant cheers. The spectators were gathered around the ant's finish line. It looked as though the race was already done.

Then, the hare realized what had happened.

--------

For other familiar tales, see Binary Searching for Cinderella or Goldilocks and the Boolean Bears.

Or see a full list of stories here.