Binary Search

Previous: What Causes the Mandela Effect?

[ source ]

The Basic and Advanced Strategies which we have been discussing for "Guess The Number" are so powerful in other contexts that we all use them in our daily lives without even thinking about it.

To find a word in a dictionary, you don't start at the beginning and read the whole book. You choose a page near the middle, check what it says, and narrow your search to the front or the rear as appropriate. And you repeat this process as many times as necessary until you find what you're looking for.

We use the same technique when searching a phone book, an encyclopedia, or an index. Any sorted list lends itself to this technique, which is sometimes called "Binary Search."

This is not the same as the "False Binary" which we sometimes see in politics, for instance, where people are told they must be "Democrat or Republican," or "Liberal or Conservative," or "with us or against us," and where no other options are ever acknowledged, even though they do exist.

This approach might be called "True Binary," because no matter where you look, if you don't find the item you're seeking, then it must be either before or after the place where you're looking. It can't be both, and there is never any third option.

When we use Binary Search to find a phone number, for instance, we don't try to look at the middle of the range every time. Looking anywhere near the middle of the range is good enough.

This is because we are not trying to find the number in the fewest possible steps. We are trying to find it as quickly as possible. And we can't pinpoint the middle of the range easily, as we can in "Guess The Number." So we don't bother. We just make one reasonable guess after another because that's faster.

Computer programs use Binary Search in many different ways, some of them far from obvious. And software can find the middle of a sorted list quite easily, so that's what computer programs do. We might even say that computers always use Basic Strategy whereas humans always use Advanced Strategy.

Whether we do it ourselves or program our computers to do it; whether we use Basic or Advanced Strategy, we like Binary Search for its efficiency, especially when we are working with a long list.

In "Guess The Number," Basic Strategy can find any number between 0 and 32 in at most 5 guesses.

And it's called Binary Search because it cuts the range in half each time, so we can find a number between 0 and 64 in 6 guesses, between 0 and 128 in 7 guesses, and so on.

If a list has a thousand items, a binary search takes 10 steps. If it has a million items, the search takes 20 steps. If the list has a billion items, the search takes 30 steps. And so on.

Unless a list is very short, it always makes more sense to use Binary Search than to read the whole thing. And the longer the list, the more sense it makes, as long as the list is sorted.

People say, "finding a needle in a haystack" when they mean, "solving a very difficult problem."

With Binary Search, you can find a needle quickly and easily, provided you can sort the haystack.

Next: Triple Bogus When Lit
Previous: What Causes the Mandela Effect?
Home: Contents
~~~
Your comments are invited.

Me And My Shadow

Previous: "Saddam's Confessions"

This diagram, from "Solar Geometry
On The Flat Earth," shows key points
in black and distances in red.

One evening, when the sky was clear, I went outside shortly after dinner and found a flat spot. Then I drove a stake into the ground, using a level to make sure it was vertical.

I measured the distance (H) from the top of the stake (T) to the ground (B), and recorded it in my notebook.

Then, at irregular intervals, I marked the end of the stake's shadow (P) and measured the length of the shadow (L). After each measurement, I recorded the time and the new value of L.

As the evening went on, the shadow grew longer and L grew larger. But I didn't pay much attention to the actual numbers. I just wrote them in my book.

After a while, the shadow got so long that I couldn't measure it properly, so I started using a shorter stake. I measured the new value of H and recorded it along with the time. Then I went back to measuring and recording L.

I stopped when the sun was so low in the sky that I couldn't see the shadow clearly. In this way I made about a dozen observations over a two-hour period.

~~~

Later, I typed my notes into a spreadsheet and ran a bit of math. Mostly I wanted to see how the ratio L/H changed over time. L/H is very interesting under the flat earth model, where the sun (S) is always 3000 miles (K) above the earth (M). It's interesting because if we multiply L/H by 3000, we get Q, the distance between M and P in miles.

When L/H = 1, Q is 3000. When L/H = 2, Q is 6000, and so on. So this is an easy way to figure out the distance to the place directly below the sun, and to the sun itself, under the flat earth model.

When I started measuring, L/H was slightly more than 3. So Q was more than 9000, and M, the spot on the earth directly below the sun, was more than 9000 miles away from me.

When I stopped, L/H was more than 14. According to the flat earth model, Q was more than 42000, which means that M was more than 42000 miles away from me.

This result poses a bit of a problem for the flat earth model, because I did my experiment in the summer, and I live the North of the equator.

~~~

Why is this a bit of a problem? The radius of the equator, the distance from the North Pole to the equator, is about 6250 miles. Therefore the diameter of the equator is about 12500 miles.

When it's spring or summer in the North, the sun is circling inside the equator, according to the flat earth model. That is to say, the sun is traveling in a circle whose diameter is less than 12500 miles.

As the sun circles in the sky, M traces a circle on the surface of the earth, and the diameter of that circle is also less than 12500 miles.

Remember what we mean by diameter: Given any point on a circle, if we drew a line through the center of the circle and extended it until it met the circle again, the length of that line would be a diameter.

The two points where the diameter intersected the circle would be as far apart as any two points could be, if they were both on the circle.

So the distance from any point on the circle to any point inside the circle must be less than the diameter.

And therefore Q must be less than 12500 -- all day, every day of spring or summer, for every observer North of the equator.

Since I am North of the equator, Q must be less than 12500 for me, too. Therefore, M, the spot on the earth's surface directly under the sun, must be less than 12500 miles away from me, according to the flat earth model.

But I used the same model to interpret the data I had collected, and it told me that when I stopped measuring, M was more than 42000 miles away. How can this be?

~~~

Well, I lied. This is not actually "a bit of a problem." M cannot possibly be less than 12500 miles away and more than 42000 miles away at the same time, so this -- for me -- is conclusive proof that the flat earth model is incorrect.

I can say with confidence that the flat earth model does not explain the evidence that I observed. I can even say the evidence undermines the model.

I have a handle on epistemology. I am on the path of evidence. I have seen strong evidence, evidence that I collected myself, and I trust its accuracy.

Therefore, I believe I am justified in rejecting the flat earth model. But this does not mean that you would be justified in doing the same.

I have described an easy way for you to do an experiment of your own. You can collect your own evidence. You can make up your own mind. If you can replicate my results, you too can reject the flat earth model with confidence.

If you live South of the equator, the numbers are different. The sun moves in larger circles during your summer. And you are farther away from the center of the solar circles. But no matter how far South you live, M could never be 42000 miles away from you, either. So if you can replicate my measurements, you too can confidently reject the flat earth model.

Next: What Causes the Mandela Effect?
Previous: "Saddam's Confessions"
Home: Contents
~~~
Your comments are invited.

Advanced Strategy For "Guess The Number"

Previous: Solar Geometry On The Flat Earth

[ source: grammar dot about dot com ]

Our Basic Strategy for "Guess The Number" is the best you can do against a Selector who chooses his Answers randomly. But if you play it consistently, a smart Selector will adjust his tactics and gain an advantage.

After several Rounds, he will begin to see that your first Guess is always 16, your second Guess is always 8 or 24, your third Guess is always 4, 12, 20, or 28, and your fourth Guess is always an even number as well.

Once he notices this, he will start choosing only odd numbers, reasoning that with your strategy, you can't find an odd Answer until your fifth Guess, so he will score 4 points per Round.

Can you alter your strategy to counter his adjustment? Of course you can!

Clearly, if you think the Answer is odd, there's no point in continually guessing even numbers until the only number left in your range is odd.

Actually, if you think the Answer is odd, there's no point in guessing any even numbers at all! But this is what the Basic Strategy leads you to do.

So let's go one step further and say: If you think the Answer is odd, you should guess odd numbers.

Against a random Selector, this would be slightly sub-optimal because the first Guess breaks the range into two unequal parts, and subsequent Guesses may do so as well. But you can do very well with it, provided that you always pick a number which is close to the middle of the range. So rather than 16 for your first Guess, you would choose 15 or 17, and so on.

We can use standard statistical methods to analyze these two strategies against various strategies of the Selector. The arithmetic is simple, but there's an awful lot of it, so I won't go into detail about the calculations here (although I will say more in the comments if anyone is interested).

Cutting to the chase, then, and using round numbers:

Using a random approach against Basic Strategy, the Selector will score an average of 3 points per Round. And this is what we would expect at the beginning of a game.

Against Basic Strategy, as we have seen, the Selector can score 4 points per Round by choosing only odd numbers, and he will do this until the Guesser adopts our Advanced Strategy.

Against Advanced Strategy, the Selector will average only 2 points per Round by choosing odd numbers, so a smart Selector will switch back to even numbers, which will score an average of 4 points per Round, until the Guesser reverts to Basic Strategy, when the Selector will average 2 points per Round, until the Selector starts choosing odd numbers again, and so on.

In this way, "Guess The Number" can gradually become a game of psychology, rather than arithmetic, as both players move toward mixed strategies, in order to avoid being predictable, which loses.

When both players adopt mixed strategies, the play once again takes on a more-or-less random character, and the average score settles back in at 3 points per Round.

Aren't you glad you know all this? We'll talk about it more, later.

Next: "Saddam's Confessions"
Previous: Solar Geometry On The Flat Earth
Home: Contents
~~~
Your comments are invited.

Basic Strategy For "Guess The Number"

Previous: New Wine In Old Bottles

[source: your dictionary dot com]

For the Guesser in "Guess The Number," the best possible strategy is the one which leads him to the Answer in the fewest steps, no matter which number the Selector has chosen. How do we find this strategy?

At the beginning of each Round, the Guesser knows only that the Answer is between 0 and 32. In other words, it's in the range 1-31, so there are 31 possibilities.

The Guesser would have no reason to assume that any number in the range is more probable than any of the others, so he cannot maximize the probability of choosing the right Answer.

That is to say, unless he has secret powers, the Guesser cannot avoid making incorrect Guesses. But he can maximize the amount of information he obtains from each incorrect Guess. How can he do this?

Let's look at what will happen if the Guesser guesses a number from one end of the range or the other.

If he incorrectly guesses 1, the Selector will say "Too Low" and the Guesser will eliminate 1 from his range, leaving 30 possibilities(2-31).

If he incorrectly guesses 31, the Selector will say "Too High" and the Guesser will eliminate 31 from his range, leaving 30 possibilities(1-30).

In either case, the Guesser will eliminate only the Guess. And if he keeps chipping away at either end of the range, he will eventually find the Answer, but it might take him a long time to do so.

However, if he incorrectly guesses a number closer to the middle of the range, the Selector will say either "Too High" or "Too Low," which will give the Guesser additional information, allowing him to elminate more than one number from his range.

For instance, if he incorrectly guesses 16...

... either the Selector will say "Too High," in which case he will eliminate 16-31 from his range, leaving 15 possibilities (1-15)...

... or the Selector will say "Too Low," in which case he will eliminate 1-16 from his range, leaving 15 possibilities (17-31)...

... and in either case, he will have cur his range in half.

These are the most extreme cases, but the general point is: the Guesser will find the Answer faster if he chooses numbers from the middle of the range, rather than numbers from either end.

And the closer his Guesses are to the middle of his range, the faster he will find the Answer.

~~~

If the Guesser always chooses the number that is exactly in the middle of the range, he can find the Answer in at most 5 guesses.

To see how this works, let's say the Answer is 23. Here is how the Guesser would find it:

First he would calculate 1+31=32 and 32/2=16, so his first guess would be 16, which would be "Too Low." This would eliminate 1-16, leaving 15 possibilities (17-31).

Then he would calculate 17+31=48 and 48/2=24, so his second guess would be 24, which would be "Too High." This would eliminate 24-31, leaving 7 possibilities (17-23).

Then he would calculate 17+23=40 and 40/2=20, so his third guess would be 20, which would be "Too Low". This would eliminate 17-20, leaving 3 possibilities (21-23).

Next he would calculate 21+23=44 and 44/2=22, so his fourth guess would be 22, which would again be "Too Low". This would eliminate 21 and 22, leaving only one possibility (23).

His fifth guess would be 23, which is the Answer. And the Selector would score 4 points.

If this is not clear to you, please ask questions in the comments, and I will try to do a better job explaining it.

We will return to this topic fairly soon.

Next: Double Bogus When Lit
Previous: New Wine In Old Bottles
Home: Contents
~~~
Your comments are invited.

Elliptical Thinking

Previous: "Guess The Number"

source: infactcollaborative.com

According to the flat earth model, the sun travels in circles, 3000 miles above the earth. And the circles vary in size over the course of a year, which accounts for the seasons. But it always takes exactly 24 hours for the sun to complete a circle, which accounts for day and night. And the center of the circle is always directly above the center of the earth, which we call the North Pole.

Since the earth is a plane and the sun is always the same distance above the earth, we can deduce that the sun moves in another plane, that the plane of the sun is parallel to the plane of the earth, and that the distance between these two planes is 3000 miles. Otherwise the sun would come closer to the earth, and/or move farther away, as it circled around.

As we know from experience, a circle observed from above or below doesn't appear perfectly round unless the observer is directly above or below the center of the circle.

From any other vantage point, the circle appears to be an ellipse. We can prove this is so, and see why, using projective geometry.

Projective geometry is the mathematics behind perspective graphics, which allows artists and computers to create realistic-looking 2-dimensional images of 3-dimensional objects.

Photographs look realistic if the lens preserves this geometry. Paintings and sketches look realistic if the artist can capture this geometry. And computers can generate realistic-looking moving graphics in real time because the arithmetic required by this geometry is very simple.

And that means: we can use this geometry to test the flat earth model.

We don't just know that the path of the sun will appear elliptical. We can determine precisely what that path will look like.

In other words, we can easily calculate the apparent position of the sun, as seen on any day of the year, at any time of the day, from anywhere on earth.

And this suggests a simple experiment. We could calculate where the sun would appear at a certain time, to an observer in a certain place.

Then we could put an observer in that place at that time, and have him measure and record where he sees the sun.

Or we could just go to that place at that time, look at the sky, and see for ourselves.

Either way, the experiment would involve the comparison of a prediction against an observation.

Of course, an experiment involving a single prediction and a single observation would not amount to a fair test. We would need a series of predictions, and a series of observations.

~~~

All these thoughts ran through my head, and I thought: Why not? What's the harm?

So I decided to build a mathematical model of the flat earth theory, generate some predictions, and test them.

This was my first hint that I was becoming delusional.

Next: Forgive Us Our Debts
Previous: "Guess The Number"
Home: Contents
~~~
Your comments are invited.

"Guess The Number"

Previous: Who Moved South America?

source: I don't smoke dot net

Here's a simple game you can play with a friend, if you have a friend who plays simple games.

The game is played in turns called Rounds, and the rules define two roles: the Selector and the Guesser.

Start by tossing a coin. The winner is the Selector in the first Round, and the loser is the Guesser. After each Round, the roles are reversed.

To play a Round, the Selector chooses an Answer (a number between 0 and 32). The Selector writes the Answer on a piece of paper, and puts it face-down on the table.

Then the Guesser finds the Answer by repeating as many times as necessary:

Step 1:
The Guesser makes a Guess by announcing a number between 0 and 32.

Step 2:
If the Guess matches the Answer, the Selector says "Correct." The Selector turns over the paper to reveal the Answer, and the Round is over.

Otherwise, the Selector announces whether the Guess is "Too High" or "Too Low." The Selector scores a point and the game reverts to Step 1.

After each Round, the roles are reversed. The Selector becomes the Guesser, the Guesser becomes the Selector, and the game continues.

The first player to score 32 points is the winner.

~~~

If any of this is unclear, please ask questions.

Otherwise, I have a question for you.

What is the best strategy for the Guesser?

See if you can figure it out.

Next: Elliptical Thinking
Previous: Who Moved South America?
Home: Contents
~~~
Your comments are invited.