Tuesday, January 24, 2012

Using Binary to Warn of Snow Beasts

Binary is a number system where each digit can only take one of two values: zero or one. Binary is used within computers, because it allows the computer to encode information in a series of switches that are either on (1) or off (0). Each digit of binary represents a power of two. The first (right-most) digit represents the 1's place, the second digit represents the 2's place, the third represents the 4's place, and so forth. For example, the binary number 10110 = 1*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 0*2^0 = 22 in decimal.

The outpost of Iceton stood on the northern edge of the kingdom. It was little more than a scrawny barracks surrounded by a short fence and miles of tundra. Snow fell during most of the year, except in the winter months when it was too cold for snow. Few soldiers were stationed there by choice.

Despite the outpost's persistent recruiting problems, it was absolutely vital to the safety of the kingdom. North of Iceton roamed dangerous snow beasts. The beasts resembled elephant-sized polar bears with sharp antlers. They had nasty tempers and a particular fondness for attacking the kingdom's outposts. Iceton watched for these incoming threats and warned the cities to the south.

Since few pigeon messengers could survive Iceton's wintery conditions, giant fires signaled any impending danger. A fire atop one of Iceton's large signal towers indicated an incoming snow beast. The lack of a fire indicated the comparative safety of frostbite, hypothermia, and tundra goblins. Iceton's neighbor to the south, Garroow, watched for signals of trouble from Iceton and relayed the warning further south.

One day, a Garroow guard noticed a troubling sight: two fires burning on the Iceton signal tower. Being that Garrow's entire platoon was new to the outpost, no one knew what two fires meant. After much discussion, Garroow's commander dispatched a rider to investigate. The unlucky soldier, Mavis Yates, arrived at Iceton a few hours later.

"What news do you bring us from Garroow?" asked Iceton's commander with a note of worry.

"I came to investigate the fires," answered Mavis. "What do they mean?"

Commander Dorn looked confused. "They mean the same thing they always have -- snow beasts are heading toward Garroow."

"Why are there two of them?" asked Mavis.

"There are two snow beasts," answered the commander as though the answer was obvious; which, in retrospect, it was.

Moreover, this confirmation was certainly not worth a two hour trek through the tundra. Mavis, desperately wishing to avoid any future journeys to Iceton, decided to clarify. "And three fires would mean three snow beasts?"

"Well…" stalled the commander, "Three or more. We only have space for three signal fires. If you see three fires, you will have to come investigation. There could be five snow beasts heading in your direction."

Mavis had no intention of repeating this journey. Especially not if there were three or more snow beasts heading toward her.

"Oh, no." Mavis protested. "There has to be a better way."

Commander Dorn shook his head. "I assure you that this is how we have communicated for the last ten years. It is quite effective. We only see packs of more than two snow beasts a few times a year."

Mavis shivered involuntarily. "We can do better with three fires. Why not use binary?"

"Binary?" asked the commander.

"Binary," confirmed Mavis. "Each signal fire can indicate a power of two."

"Power of two?

"From East to West they will represent powers of 0, 1, and 2. That is 2^0=1, then 2^1=2, and then 2^2=4. We can encode a lot more information that way."

"That will only tell you that there are 1, 2, or 4 snow beasts coming. How does that help?" protested the commander.

"You add the digits that have fires," explained Mavis. "Let's say the first and last fires are lit. That means there are 1 + 4 = 5 snow beasts."

Mavis walked to the wall, grabbed her hunting knife, and began to carve the following code into the wall:
NO-FIRE, NO-FIRE, NO-FIRE = 0 snow beasts
NO-FIRE, NO-FIRE, FIRE = 1 snow beasts
NO-FIRE, FIRE, NO-FIRE = 2 snow beasts
NO-FIRE, FIRE, FIRE = 3 snow beasts
FIRE, NO-FIRE, NO-FIRE = 4 snow beasts
FIRE, NO-FIRE, FIRE = 5 snow beasts
FIRE, FIRE, NO-FIRE = 6 snow beasts
FIRE, FIRE, FIRE = 7 snow beasts
She stepped back and examined her work.

"Binary," she stated.

The commander stared at the code. "I think it will work," he remarked finally.

"What happens if there are eight snow beasts?" asked one of the commander's aids. "Should someone from Garroow come and investigate?"

"I do not think it is worth worrying about that," the commander answered without looking away from the wall. Mavis smiled. She had found a way to avoid future treks altogether.

"After six, it does not matter much," continued the commander. "When there are that many, they skip Iceton and head straight for Garroow. It is not worth their trouble here. And all that Garroow can do is warn the other cities and flee south."

Mavis's smile vanished. "Wait… what?" she asked.

"Oh… right… you are from Garroow." responded the commander. "Umm.. Good luck with that."

------------

To learn more about binary, also read Unhappy Magic Flowers and Binary. Or read about Ann's visit to Garroow in The Important of Variable Names.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.