Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Behold! The power of recursion.

by davido (Archbishop)
on Oct 18, 2004 at 01:52 UTC ( #400027=note: print w/ replies, xml ) Need Help??


in reply to Behold! The power of recursion.

I wanted to point out that your "guess the number" algorithm is O(log N) in its computational efficiency. What that means is that as the dataset (or in this case, the size of the range in which the secret number may be hidden) grows by "N", the amount of work needed to find the secret number grows by "log N".

This happens to be, roughly, the same algorithm used in a binary search, which is known to be O(log N) too (of course).

The recursion is mostly a convenience here. An iterative approach could be used to implement the same basic algorithm, but recursion is kinda cool. :)

By the way, Perl (with warnings turned on) warns you when your recursion level reaches 100 levels deep. You can turn this off, if I recall, with "no warnings qw/recursion/;".


Dave


Comment on Re: Behold! The power of recursion.
Download Code
Re^2: Behold! The power of recursion.
by pg (Canon) on Oct 18, 2004 at 02:06 UTC
    "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 ... ;-)

      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!

Re^2: Behold! The power of recursion.
by demerphq (Chancellor) on Oct 18, 2004 at 17:54 UTC

    Just to add something here, the log we use in computer science is log 2 not log 10. Hence log(10) is 2.30258509299405 not 1. Just in case anybody forgot this :-)


    ---
    demerphq

      First they ignore you, then they laugh at you, then they fight you, then you win.
      -- Gandhi

      Flux8


Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://400027]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (5)
As of 2014-09-16 02:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (155 votes), past polls