Ricochet is the best place on the internet to discuss the issues of the day, either through commenting on posts or writing your own for our active and dynamic community in a fully moderated environment. In addition, the Ricochet Audio Network offers over 50 original podcasts with new episodes released every day.
How to Build a Computer 11: The Binary Search Algorithm
We’re taking a break from the manufacturing process to cover some ideas in programming. Algorithms, what that means and why. Sounds fancy, doesn’t it? It ain’t as bad as it sounds. Let’s jump right in:
What’s An Algorithm?
It sure as heck ain’t Al Gore’s killer dance moves. The word “Algorithm” means something like a recipe. It’s a series of rules, and if you follow the rules you get the promised result. Computer jerks talk about them because you have to break your instructions down into very simple bits in order to make a machine understand what it needs to do. Let’s try a very simple algorithm.
The MakeStuffBigger algorithm; pass in stuff, get bigger stuff out.
- Pass in some stuff
- Add one to it.
- Return your enbiggened stuff.
That’s all it takes. You MakeStuffBigger on 17 and you get 18 out of it. This is the sort of thing a third grader uses when he’s saying “nuh-uh infinity-plus-one times!”, a practice upon which I’ve discoursed previously.
You can see how the recipe comparison works; a recipe is an algorithm for making a food. Let’s take a look at that.
The PizzaMe algorithm; Pass in dough, sauce, cheese, and one or more toppings. Returns one Pizza
- Roll out pizza dough so it’s flat.
- Apply sauce.
- Apply cheese.
- Apply more cheese
- Look, I’m from Wisconsin, you’re not getting out of this until there’s enough cheese on that pizza, get me?
- For Each topping in [Set of Toppings] apply Topping to pizza.
- Preheat oven to 400 degrees Freedom (254 Commie)
- Once oven is at temperature insert pizza
- Bake for 20 minutes
- Remove pizza from oven.
Notice anything? The preheating instruction comes in at step 7. Odds are you were already thinking you should start the oven at step one so you don’t have to wait so long. The oven can be warming up while you’re mucking about with the cheese. That’s the thing people generally worry about when they’re talking about algorithms; which one is quicker. Both the original and revised PizzaMe algorithms will produce a Pizza, just one is quicker.
You could also apply a layer of abstraction to this:
EasyPizzaMe: Pass in Cash, returns one Pizza
- Call for delivery
The PizzaMe algorithm is still happening, it’s just happening at the pizza joint. You’ve abstracted past the point where you have to worry about those details. Neat, huh?
Okay, but back to computers.
What’s a Binary Search?
What’s a search? You’re looking through a thing to find another thing. Let’s say you’re looking for my house in Eau Claire Wisconsin. Here’s one way you could go about it.
- Find a house in Eau Claire. Knock on the door.
- If I answer the door you’re done.
- If I don’t then find another house and check that one.
Not terribly efficient, and that’s even assuming I’m sociable enough to answer random door-knockers. Eventually it’d get the job done though. You could make it a little more efficient (3. Ask that guy if he knows Hank) but it’s still slow. But hey, Eau Claire only has like 60,000 people, if you set a computer to do it it’ll be quick enough. It’s not you knocking on those doors after all.
Let’s modify the parameters. Supposing I lived in New York City. At ten million folks it’s much less likely that your computer will perform this search in a reasonable amount of time. (Reasonable defined as ‘I’m getting bored over here!’ It’s actually a pretty useful standard.) Now suppose you don’t actually need to get to my house, you just need my phone number. You could look in the phone book. (I don’t have a land line, but my NYC alter-ego does. That guy’s a dork.)
Simple phone book search: Pass in a name, get out a phone number
- Look at the first entry.
- If it’s Hank Rhody you’re done.
- If it isn’t, look at the next entry.
Still going to take a while, even for a computer. That half second while it’s thinking is enough for me to refresh my Ricochet alerts and get distracte. But hey, phone books are alphabetical by last name. Let’s try again, using that information:
- Open the book to the middle. Check any name on that page.
- If it’s Hank, you’re done (lucky you!)
- If it isn’t, check whether it’s alphabetically before or after it. Probably before; R is towards the end of the alphabet.
- Stick your thumb in the book at that page. Open the phone book halfway between your thumb and the correct end of the book.
- Repeat.
Each time you’re halving the amount of names you’d have to look through. Even if you’re doing it stupidly you’re going to get to my name after something like thirty checks. It’s a little more complicated than check each name in order but it’s much quicker.
That’s a binary search algorithm; “Binary” means you’re splitting the dictionary in two. It’s pretty quick; it’s possible to make quicker algorithms but they get more complex, and I’ve never needed them at the scale I work. I only got into binary searches because the “check each one” was taking too long. I had an Excel file with a big table (~250k lines, at that time) that I wanted to match times against. Here’s a function I wrote in VBA to do just that.
MatchTimeToTable: Stick in a time, returns the row of the table that contains that time.
“hi” is the highest number line you’re considering, “lo” is the lowest number. Naturally midPt is the middle-est.
Does it make sense? Probably not just from reading through it. I’ll work out an example for you. Let’s say I’m looking between rows 2 and 200,000 for a value. Eventually I’ll find it in the slot 31,337. Here’s a walk-through of what happens:
Calculate midPt (99,999).
Is it correct? No.
Is the guess too small? No.
Then the guess is too big; reset the top row to 99,998 (the next smallest row after the guess) and try again.
Calculate midPt (49,999). Too big again.
Reset and calculate midPt again. 24,999. Too small. Adjust the lower bound this time to 25,000, and calculate it from there.
Calculate midPt again (49,999 – 25,000)/2 + 25,000 = 37,498 (That’s a slightly unusual calculation for an average. The minus/plus bit is to avoid the number getting temporarily too big and breaking things.)
37,498 is too big again. Reset your upper bound and calculate it again. Now we’re checking between 25,000 and 37,497.
Repeating, we get approximately 31,250 (close!), 34,375 (further), 32,750, 32,000, 31,650, 31,450, 31,350, 31,300, 31,325, 31,337
Without cooking the example we found one value in 200,000 in only fourteen guesses. Lighting quick! Okay, I may have rounded for ease in the later calculations; I was doing this manually. You get the point though; having a clever algorithm makes doing your job immensely quicker. Quicker enough to make a difference? It helped quite a bit with my particular problem. But elsewhere?
Why’s an Algorithm?
Once upon a time I was studying thickness of a polyimide film on stainless steel. Had to do with process development. I had a measurement machine and I wasn’t sure I trusted the output of it’s program. Found a way to export a list of coordinates. Three hundred and sixty thousand lines of X, Y, and Z positions. Okay, I can make a visual map of that stuff in an Excel sheet. My first pass at an algorithm was stupid; with nested loops. It’d run through the whole list once for each item in the list. Worse than that; I was asking it to do calculations proportional to the cube of the lines in the table. At least 2,000,000,000,000,000 number crunches. That’s a number so large the national debt hasn’t even reached it yet. Even with Moore’s law at my back I wasn’t going to finish that calculation.
Second pass at the algorithm was less stupid. It only looped through the list once, which meant that I was only asking it to perform on the order of 360,000 calculations. That’s a number so small the federal government spends it without noticing. But I’m just a hedge programmer, playing in Excel while the real programmers are out writing code in hexadecimal. What does this kind of stuff look like in the real world?
Let’s say you’re looking for a unique phrase on every web page on the internet. You go to Google and plunk in the name Claymore J. Flapdoodle and see what it spits out. It tells me “About 16,100 results (0.55 seconds) “. Google has an algorithm that it uses to search the whole internet, categorize results, and show you the best ones, and do it all in half a second. That isn’t (just) rooms and rooms of computers. I don’t know how they do it, but it’s a heck of a lot more complex than a binary search. Google’s search algorithm is one of the most valuable bits of intellectual property in the world. Now you can understand why. The difference a good algorithm makes is the difference between half a second and half a century.
I hope you’ve enjoyed our little interlude into logic. I’ll get back to exposing next week (swearsies) once I’ve gathered some more pictures. Join us next week for “The Terrible Truth of the Autoexposer — Revealed!” or “Freaking Finally”.
This is part eleven of my ongoing series on How to Build a Computer, the “That’s not a Knife” way. You may find previous parts under the tag How to Build a Computer. This week’s post has been brought to you by Eggrolls Plus. The Plus is good too, but you’ll never know it because you’ll love our eggrolls so much. Eggrolls Plus!
You can put these all together and make them into a book
Gonna have to go deep-dish to fit enough cheese in there.
Hank really could! This is wonderfully written.
Oof. Did @samrhody help you write that one?
Alright, you’re forgiven.
One of these days, I need to write a post on the Texas Two-Step. My favorite ever algorithm.
I wish I could take credit for that.
Gas 6 in Brit. Why they use that particular scale is beyond me, but I have a couple of British cookbooks so I had to figure it out.
That cracked Me up.
This binary search algorithm sounds suspiciously like Newton’s Method for calculating square roots:
Which is so simple that I got a B on my first Calc II exam in college because my handwriting made it look like I’d written x*2 instead of x^2, and I was in such a hurry to finish the exam I failed to check my work, and didn’t notice that I’d calculated the square root of 65 to be roughly 11.
(In my defense, I learned the night before the final that the only reason the girl in my recitation I had a major crush on finished the exam questions was that she picked one of the five problems on each exam and skipped it! I wish I’d taken her advice on the final, but I was honestly still very excited that she’d come to my room the night before and asked me to tutor her in Econ. That she wrote me over Christmas Break to tell me she’d gotten all As for the semester, whereas I got Bs in both Calc II and Econ, actually made her more attractive, not less.)
I think I first heard it in the early 2000’s, on a cheap gag web site. It featured a dancing Al Gore. Nuff, as the kids say, said.
Do they also measure their food weights in stones?
That would be a lot of food to make it worthwhile.
Yeah, it’s similar. I once spent a long night at the plastics factory working out the square root of five by hand using Newton’s method. I got it wrong.
Wish I had as good an excuse as a girl.
Slide rules, guys.
Good definition of algorithm, by the way. Although, it’s kind of fun to hear people using the word when they obviously don’t know the meaning. Most people think it’s some kind of magical incantation.
Sufficiently advanced technology!
I wrote a paper in college on how you could replace the witches in Macbeth with computer programmers. When you get right down to it ‘magic incantation’ is a pretty good description.
Now this is my zone.
And suddenly I’m worried.
One of the hazards I took into account when I started writing this series, there are an awful lot of smart people on Ricochet. Sooner or later I’m going to get something wrong, and what’s worse, something that’s blatantly, awfully wrong in front of someone who happens to know everything there is to know about the subject.
On the subject of algorithms generally, some comments in my code:
What you’ve written up is perfectly fine. Nice bit with abstraction.
I’ve always found this visualization below to be interesting. Poor bubble sort.
I remember having to write all of those sorts in high school (in Pascal!) just to prove that quicksort was fastest (because we didn’t have YouTube in 1985).
By the time I was in college, they didn’t even bother with that exercise, merely telling new programmers, “Use Quicksort. It’s the fastest.”
I guess I’ll take that as a compliment. I always liked those witches.
Just wait until you get to deal with 1) recursion and 2) random number generators.
I had the “random” number table on my Atari 800XL memorized, and I could give a pretty good guess as to what number was going to come up based on how long it had been since I reset the computer.
Yes, I spent hours writing programs to POKE random values into every memory location to: a) see what interesting stuff I could get on the screen, and b) see how long it would take to hang the computer. Didn’t everyone?
Missed opportunity there. Could have been ” and 17) random number generators.”
I am looking forward to getting to random number generation. There’s quite a bit there that I don’t know or don’t understand yet, and I get to learn it before I can present it to y’all.
I had an 800XL too. Quite a bargain for its time.
Those are both fun!
You discovered the need for a sanity check. After 20 or so iterations you should have been asking: Do I have OCD? If you’re next question was “But do I have OCD?” and the question after that, and the question after that … then the answer is: Yes. Yes you have. Seek treatment. Although, in rare cases, you simply have a case of Hamlet’s syndrome, which is easily treated by one-time application of a poisoned sword.
You’re going to post that paper here, right?
Please?
Don’t believe I have it anymore. If I do it’s locked away on an old hard drive in a dusty box.
The assignment was to change the setting of the play and see what that does to the story. Probably the silliest was the Stoner Macbeth.
“Dude, I know what I saw, and those trees were moving.”
“Been smoking some of that Birnam Wood?”