Think about Loose Coupling PerlMonks

### Re^2: Behold! The power of recursion.

by pg (Canon)
 on Oct 18, 2004 at 02:06 UTC ( #400029=note: print w/replies, xml ) Need Help??

in reply to Re: Behold! The power of recursion.
in thread Behold! The power of recursion.

"This happens to be, roughly, the same algorithm used in a binary search,"

Indeed this is binary search itself. This used to be a trick I played when I was a kid. I first ask other kids to have a number between 1 and 1024, don't tell me, just keep it to themselves. Then ask them whether they believe that I can guess their number by asking no more than 10 questions. Nobody believed me at the beginning, but ... ;-)

Replies are listed 'Best First'.
Re^3: Behold! The power of recursion.
by davido (Archbishop) on Oct 18, 2004 at 02:39 UTC

This is pretty easy to solve for "worst case" and "average case" mathematically. But DigitalKitty's script makes it pretty easy to also empirically test. This isn't intended to be a replacement for mathematical proof, but rather, just a quick real-world example of how efficient the binary-search algorithm is. For each of the items in the table below, a modified DigitalKitty script was run. The modification causes the script to search for random numbers ten times in each range, and then print the average number of guesses for those ten searches. In each case, the range is assumed to be "0 .. N".

So here are a few trial runs:

```Range          Average Guesses
10             2.5
100            6
1000           9
10000          13
100000         16.5
1000000        19.5            (That's a range of 1 million)
1000000000     29.5            (That range is 1 billion)
1000000000000  39              (The range is 1 trillion)

So this unscientific example shows that you can find one number hidden among a range of one trillion numbers, on average, after 39 guesses, using a binary search. Also, it should be noted that the larger the range, the smaller the standard deviation in number of guesses needed, as a percent of total guesses. A binary search is fairly stable; not very sensitive to the dataset.

If you were to bet someone you could guess their number between zero and 100 in less than ten guesses, you will most likely walk home with the money. But you'll really surprise someone if you can guess a one out of a trillion number in well under 50 guesses.

Dave

"If you were to bet someone you could guess their number between zero and 100 in less than ten guesses"

For numbers in this range, I will bet for 7 times, not 10 times!

Create A New User
Node Status?
node history
Node Type: note [id://400029]
help
Chatterbox?
 [1nickt]: But the bands are even louder! I saw Spearhead (Michael Franti) at an outdoor show and had to walk a mile away to not feel pain in my chest! Babies were crying ... I asked the sound engineer why it was necessary to have the bass so loud and he laughed... [Discipulus]: but the best i attended live was Mano Negra Patchanka at Forte Prenestino .. in 1990 [Corion]: Hmmm - Mano Negra or at least Manu Chao seem to put on a good live show. At least the one live CD I have from Manu Chao sounds good ;) Discipulus feels the same jealousity of the johngg's daughter [1nickt]: choroba I agree [choroba]: Playing in a punk rock band for 20 years... my hearing is quite bad [Corion]: I still have hopes to turn my godson and his two siblings into a punk band ;) [Corion]: Their older sister just started piano but has been interested in drumming, which she should be able to start with 8 years or so) [Discipulus]: ah was Kink of Bongo 1992..

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (9)
As of 2017-03-24 12:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should Pluto Get Its Planethood Back?

Results (301 votes). Check out past polls.