Bi-Quinary Search

© Gerald M. Weinberg, 2004 www.geraldmweinberg.com

“1,073,741,823 lines of correct code, but one unknown bug is going to send us into that Sun.”

“Do not panic.” Peri said, using Calming Voice. “We have adequate time to find it.”

“Peri is correct,” echoed Setho. “Remain logical. We must divide the code in half and allow the simulator to find which half contains the defect. Once we repeat this process 30 times, we are guaranteed to find the culprit.”

“I know I couldn’t have designed this ship,” I said, “and you’re absolutely right about the process. But you have no concept of time. Each test will cost us 10 minutes, and in 4 hours we’ll pass the point of no return. Yes, an hour after that, we’ll be able to unlock the controls, but it will be too late. Perhaps you Zaard will be satisfied to choose your personal sunspot for cremation, but it doesn’t do much for me.”

“We will remember our ancestors,” said Peri, twisting into the Zaard meditation posture.

“Yes,” Setho agreed, in posture as in words. “Termination of existence is the only logical conclusion, so remembrance of ancestors is the only logical action.”

“Don’t go to sleep on me. There is a way, if we’re lucky.”

“Luck is a human concept,” Peri said, his voice slowing and sinking. “Do you really think you can find one out of a billion lines of code by luck?”

“Peri,” said Setho’s Chastizing Voice. “Please be respectful. We must not interfere with his religious beliefs, no matter how preposterous they are to us. Proceed with your foolishness, John, if you wish. We shall watch, and pray for your soul.”

“I could use more help than that. I figure that if I can guess a division of the code that puts the bug in the smaller half, I can accelerate the process.”

“Your assumptions are incorrect. Though you name it ‘code,’ we know it is Leethaa, not some simple computer instruction.”

“Doesn’t matter what you call it. If we find the Leethaa, or code, that’s wrong, we can change it through the console.”

“True. We can change it, but if we merely know it is wrong Leethaa, that still does not mean we know what is right Leethaa.”

“Of course you’ll know. You built it.” Peri and Setho exchanged another look, and the odor in the compartment changed. “I’m just a passenger, remember, like any human, taking advantage of your intergalactic freight service. You’re the designers.”

Setho turned several of his eye to me, but spoke to Peri. “Since we are all to end our existence, in a few hours, can there be harm in telling him?”

No, the memories of our ancestors will not be harmed.”

“Tell him what? And don’t talk about me like I’m not here.”

“We Zaard are not the designers of these ships. We, too, are passengers, enjoying these gifts from our ancestors, countless time in the past. We do not know how the Leethaa operate, but only how to repair them when they fail.”

I was quickly rearranging all I thought I knew about the Zaard. Too bad I wasn’t going to be able to tell anyone. “Then how can you repair it?”

Setho was about to reply, but Peri raised an appendage and used the Interrupting Voice. “We use the binary search, using the simulation logic, as I explained. When we locate the offending Leethaa, we alter its state - le to eth; eth to aa; aa to esu; esu to culara; culara to le. Those are the five possible states, as I believe you well know from observing us through these months we have flown together.”

I didn’t know they had been watching me watching them, but what did it matter now. “Fine,” I said. “So once I locate the right Leetha through my guessing, you can make it right.”

“True, but guessing depends on luck, and we do not believe in luck. You will not find it.”

“Moreover,” said Setho, “even if we were to assume your false premise about the existence of luck, then we would logically have to accept the existence of bad luck as well.”

“And with bad luck, your guessing process would actually take longer.”

“Hey, we’re going to fry anyway, so what more do we lose if it takes longer? Besides, I need your help.”

“We cannot help with luck. We can only remember our ancestors.”

I swept my gaze over the full circle of consoles. “Then call it ‘intuition,’ if you don’t like luck. You two know a lot more about this vehicle than I do, and your guesses may actually be better than mine.”

“But we already told you, we don’t believe in guessing.”

“Well, one thing for sure you do believe in is arguing, and arguing for sure isn’t going to save our skins. While we’ve been having this lovely philosophical discussion, I’ve been running my first guess. It should be done in 30 seconds.”

“We noticed,” said Setho, who seemed the more alert of the two. “… And there it is. You see, it seems that the flaw is in the larger of your two parts - not the smaller one chosen by your guess - and now the process will take even longer.”

“Okay, so it was bad luck. But if my luck turns better, we can make up the lost time.”

The two Zaard merely exchanged more glances that I couldn’t interpret, so I made my second guess. “I think the transporter code is the most likely place, so I’ll make that one of the halves.” I entered the cutting point and restarted to testing process. “If it’s in there, we’ll be down to less than a million lines of code.”

But it wasn’t there, and by the time we found out, I had already lost 20 precious minutes without reducing the problem significantly. Setho and Peri didn’t seem to mind, lost as they were “remembering their ancestors.”

I started feeling warm, even though I knew that the sun’s heat would not be affecting our interior temperature for another couple of hours. Setho must have noticed.

“Do not be distressed, John. Having remembered our ancestors, we are now at peace. Do you not have ancestors to remember?”

“Most of my ancestors aren’t worth remembering.”

“How sad. No wonder you solve problems by guessing. But surely your ancestors must leave you some worthy memories.”

I paused to enter my third guess. It was even more risky, but I had to make up time. I felt it was more of a gesture than anything useful. Three hours and thirty minutes - 21 guesses - was all that was left.

“None of them ever knew the Zaard even existed, so none of them ever toured effortlessly around the galaxy. What memories could they leave that would do us any good?”

“True. Your history is so strange to us that I never thought that you might not have useful memories. How unfortunate that we know each other better only now.”

“But your ancestors’ memories don’t seem any more useful than no memories at all, if they can’t help fix a failure.”

“Oh, but they can. We have memories of all ship failures in the past, and how to repair them.”

“Then why aren’t you fixing this one?”

Setho gave me a look that even on his/her strange face seemed to say, “Don’t be a stupid Human.” What s/he actually said was, “Because our ancestors never encountered a bi-quinary star system such as this one, so there is no memory of this particular failure.”

“But there were failures before?”

“Of course, but not this failure.”

“And how often do you have these failures?”

“Among the entire fleet, perhaps once every thousand of your years. Would you like to know exactly?”

“You mean you have a record of them?”

Peri now joined the conversation. “Of course. We told you that we remember our ancestors.”

“All of them?”

“Yes, of course. What would be the logic of forgetting errors. We have a saying, ‘A Zaard who forgets his/her ancestors forgets how to stay alive.”

My mind was racing, but my mouth was having a hard time keeping up because I was trying to keep my chest from swelling with hope. “Okay, how many have there been, since the beginning? Or is that too hard?”

“Why should it be difficult? Approximating the time, in the past 180,000 years, there have been 674 distinct ship errors.”

I did the arithmetic in my head. “That’s a mean time between failures of about 250 years.”

“267,” Peri corrected.

“Not bad, but not perfect, either. Maybe your ancestors weren’t as perfect as you thought.”

“We do not think our ancestors are perfect. If they were perfect, we would not have to remember them. But, to their credit, these failures are in a fleet of more than a million ships, so the mean time between failures on any one ship is greater than 267 million years. They are not perfect, but they are very, very consistent.”

I was impressed, but I wasn’t going to show it. “Sure, that’s great. But we’re on one ship, and it’s failing right now.”

“Fortunately,” said Setho, “the signals have already been broadcast, so we will be remembered. You will have the honor of becoming the first Human Zaard ancestor.”

“Oh, thanks, I hadn’t thought about that. But I’d rather live and be forgotten, so what else can you tell me about these errors?”

“What else would you like to know?”

“I’d like to know the distribution of errors across the various Leethaa components - like, which component has had the most errors per element?”

Peri paused for a moment, then announced, “That would be the Nisoog-arthl component, with 402 of the 674 errors, if I have remembered our ancestors honorably.”

“You have,” said Setho, “Most honorably.”

Now my heart was beating audibly, and fast. “And how large is the Nisoog-arthl?” I’m not superstitious, but I crossed all my fingers as I waited for their reply.

They replied in unision, in the Data Voice, “The Nisoog-arthl comprises Eight-hundred seventy-seven thousand nine-hundred and twelve Leethaa.”
As they spoke, my pad displayed the number: 877,912. I could do the necessary calculation in my head. “That’s it, then. One more guess and we’re done!”

I stopped the current simulation, now useless, and entered the boundaries of the Nisoog-arthl as my fourth guess. Now all I had to generate the patience to wait ten minutes to know whether I would live or die. Since Peri and Setho showed utter disbelief, I explained.

“You told me that your ancestors were very, very consistent, but not perfect. When they built these ships they didn’t make many mistakes, but they did make some. And if they were as consistent as you say, then their mistakes would be consistent, too. They would consistently make most of their mistakes in the same parts of the Leethaa. And the one part they most consistently made mistakes in was the Nisoog-arthl - so I’m guessing that’s where this mistake will be found. We’ll know in seven more minutes.”

“Yes, that’s quite logical, in a strange sort of logic, but what good will it do?”

“Yes,” said Peri, also using the Query Voice. “That was a logical guess, but that only narrows the problem down to the Nisoog-arthl. We have no more refined data, so what logic can you use for your next guess?”

“But if the error is indeed in the Nisoog-arthl, I won’t need any more guesses. I can switch to a pure binary search and be sure of narrowing the search to a single Leethaa in the remaining divisions.”

“Aaah,” they said in the Simultaneous Voice, “so in the end you can be logical.”

“And in two more minutes,” Setha continued alone, “we will all know logically whether or not we will visit that sun.”

About Gerald M. Weinberg

For more than 50 years, Jerry (Gerald M.) Weinberg has worked on transforming software organizations. He is author or co-author of many articles and books, including The Psychology of Computer Programming. His books cover all phases of the software life-cycle. They include Exploring Requirements, Rethinking Systems Analysis and Design, The Handbook of Walkthroughs, Inspections, and Technical Reviews, and General Principles of System Design. His books on leadership include Becoming a Technical Leader, The Secrets of Consulting, More Secrets of Consulting, and the Quality Software Management four-volume series. His book, Weinberg on Writing: The Fieldstone Method, appeared in 2005. His first techno-thriller novel, The Aremac Project (Dorset House), will appear in 2007. Jerry or visit www.geraldmweinberg.com to read excerpts of the Shape Forum. Picture (c)2004 Steven M. Smith
This entry was posted in Articles and tagged , , . Bookmark the permalink.