On Dec 20, 2007 11:23 AM, Arthur W Cater <[EMAIL PROTECTED]> wrote:
> I think that would be worse. There are lots of sets of 8 numbers that sum
> the same,
> far more than there are sets of 8 with the same minimum element.
>
> Arthur
>
> ----- Original Message -----
> From: Álvaro Begué <[EMAIL PROTECTED]>
> Date: Thursday, December 20, 2007 4:08 pm
> Subject: Re: [computer-go] rotate board
> To: computer-go <[email protected]>
>
> > On Dec 20, 2007 10:19 AM, Jason House <[EMAIL PROTECTED]>
> > wrote:
> > >
> > >
> > > On Dec 20, 2007 10:15 AM, Arthur Cater <[EMAIL PROTECTED]> wrote:
> > >
> > > > With 8 hashes per position, the chance of two different boards
> > > > producing a different set of hashes but
> > > > the same canonical hash is greater than 1/2^64, because there
> > will be
> > > > a bias in the choice of canonical
> > > > hashes - toward numerically lower numbers, for instance.
> > > >
> > > > I think.
> > >
> > >
> > > More importantly, how does it differ from 8/2^64 = 1/2^61?
> > >
> >
> > If you are going to compute all 8 hash keys, you can just add them
> > up at the
> > end instead of picking the minimum. Wouldn't that be better?
>
That can't possibly be true... Think about it. Sums of random numbers are
uniformly distributed (remember we are working in the ring of integers
modulo 2^64), while the minimum is very biased towards small numbers.
These two Unix commands show the number of different sums and the number of
different minimums among 10,000 sets of 8 random integers. I did it with 16
bits instead of 64:
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x (1..10000){$s=0;for
$y (1..8){$s+=int(rand(65536));}print "".($s%65536)."\n";}' | sort -u | wc
-l
9294
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x
(1..10000){$s=9999999;for $y (1..8){$t=int(rand(65536)); $s=$t if
$t<$s;}print "$s\n";}' | sort -u | wc -l
7476
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
