"Christoph Rippel" <crippel / primenet.com> wrote:
>
> > -----Original Message-----
> > From: Ben Tilly [mailto:ben_tilly / hotmail.com]
> > Sent: Tuesday, January 02, 2001 01:50 PM
> > To: ruby-talk ML
> > Subject: [ruby-talk:8543] Re: speedup of anagram finder
>...
> > In theory, yes.  In practice if you round reasonably, it will
> > work.  Of course the more you round, the sooner you get to a
> > false positive.
> > I said the idea was sick?  Sick but likely to work in a
> > practical situation.   (That said, *I* would not want to rely
> > on such code in production...)
>Yes, but instead of rounding afterwards you might as well sum up ``good 
>integer
>keys''  1 <= asc2int[char] <= upper_bound like Barry's	``asc2log[char]''. 
>In
>practice simply pick random numbers with an upper_bound around 2**29 and 
>pray, or
>pick  random numbers with an upper_bound around 2**58 if you are not the 
>sloppy
>type.

Ah yes.  The old, "Figuring out an explicit answer is hard, but
do something random and it probably works" trick. :-)

There are a lot of fun problems where finding good solutions
analytically is hard.  But take a random answer and you can
easily show it *probably* works.  And it is often not that
hard to check that it *does*.

Paul Erdos managed to start a branch of mathematics that
devotes itself to these algorithms.  And there are a number
of problems in combinatorics for which the best bounds known
come from probabilistic solutions.

IIRC an example of a practical CS problem where this comes
up is swapping large amounts of data across a cluster.  If
you try to organize how it works you seem to always get
bottlenecks.  But take each unit of data and slap on a
double-envelope.  The first is a random intermediate
location, the second is the final address.  Then just start
trying to chuck stuff where it is supposed to go.  And with
very high probability it will all figure out where it is
going in good time.

Or so I remember hearing a few years ago.  This example
could be seriously outdated by now.

Cheers,
Ben
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com