Re: Other Efforts

Daniel Berlin (bmdberlin@worldnet.att.net)
Wed, 11 Jun 1997 17:22:44 -0400


Quick Question:
Are you assuming that the code can search random and sequential in the same amount of time?
It takes more processing time to generate a random number and throw it in a variable than to simply increment a counter.
Not much, but when you are running the routine 72 quadrillion times, it might amount to something.

----
From: Justin Dolske <dolske@cis.ohio-state.edu>
To: saurvok@exo.com <saurvok@exo.com>
Cc: deschall@gatekeeper.megasoft.com <deschall@gatekeeper.megasoft.com>
Date: Wednesday, June 11, 1997 2:52 PM
Subject: Re: Other Efforts

>On Wed, 11 Jun 1997 saurvok@exo.com wrote:
>
>> I have no idea what you are saying there.
>
>You're making this much more difficult than it is! Here's something
>resembling an inductive proof, maybe this will help.
>
>Situation: 100 keys, key is hidden somewhere, but we don't know where. We
>both start searching (me linearly, you randomly), but don't share any
>information about what we've already tested.
>
>I pick key #1 to test. You pick key #57. Which of these keys is more
>likely to be The Key? Neither. Both keys have a 1 in 100 chance of being
>the correct key, because we don't know where The Key is among all the
>keys.
>
>I now pick key #2. You pick key #29. Which of these keys is more likely to
>be The Key? Neither. Both keys have a 1 in 99 chance of being the correct
>key, because we don't know where The Key is, among all the remaining keys.
>
>I now pick key #3. You pick key #72. Which of these keys is more likely to
>be The Key? Neither. Both keys have a 1 in 98 chance of being the correct
>key, because we don't know where The Key is, among all the remaining keys.
>
>I now pick key #4. You pick key #34. Which of these keys is more likely to
>be The Key? Neither. Both keys have a 1 in 97 chance of being the correct
>key, because we don't know where The Key is, among all the remaining keys.
>
>Repeat until the key is found.
>
>Can you see that at each step, any key that is choosen has an equal
>probability of being the key? If not, you should just sit down and think
>about this for a few hours.
>
>> A sequential search from the start would require searching 75% of the
>> key space.
>> Randomly searching(no dupes) would statistically require how many keys to
>> be checked before find the right one?
>
>It completely depends on the particular "random" order you search in. You
>might look at key #75 first, and find it immediately. Or, you might look
>at 50 keys before looking at key #75. or, you might look at every key
>except for #75 first.
>
>> We aren't doing lots of contests..we have just this one. We dont know where
>> the key is. If we use sequential and start at the beginning....and the key
>> for this 1 contest is at the end....we would have to search alot more.
>> So we could gamble and hope the this one time the key is closer to the
>> front than the back and save time, or use the random method at get the 50%.
>
>You're trying to second-guess the contest. Didn't you read what I already
>posted about this?
>
>Justin Dolske <URL:http://www.cis.ohio-state.edu/~dolske/>
>(dolske@cis.ohio-state.edu)
>Graduate Fellow / Research Associate at The Ohio State University, CIS Dept.
>-=-=-=-=-=-=-=-=-=-=-=-=-=- Random Sig-o-Matic (tm) -=-=-=-=-=-=-=-=-=-=-=-=-
>Did you hear about the new corduroy pillow?
> ...It's making headlines all over town.
>