On Tue, May 13, 2008 at 8:10 PM, Weston Markham <[EMAIL PROTECTED]> wrote: > On Tue, May 13, 2008 at 7:08 PM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: > > And I agree, don't even think of doing this with floating point > > numbers. > > This is a bit tangential to computer go. But you have piqued my > curiosity.... > > Offhand, that sounds rather extreme to me. Perhaps I haven't really > thought this through completely, but it seems as if there is a simple > modification to the stated algorithm, that would ensure that it works > fine with floating point numbers. Or at least well enough for any > conceivable purpose: > > Make sure that you select each random number from a slightly larger > range than prescribed by the exact totals. (For example, always round > up while calculating the totals. If you do not have control over the > rounding mode, just add on some small fraction of the largest weight.) > Then, in the event that subtracting the weights of the > points/rows/buckets never reduced the selected number to a > non-positive value, just select a new random number and start over. > > Would this work fine, or is there some flaw in my thinking that Álvaro > and Gunnar have already considered?
John Tromp and I spent quite a bit of time patching the floating-point implementation and hunting down the subsequent bugs. I am not saying that making it robust is impossible, but I ended up so frustrated that I don't think I will ever try again. Integers are much better behaved and are sufficient for everything we wanted to do. As to the optimal branching factor for the tree (assuming there are many many leaves), I believe it's n=3, if all you care about is picking random points fast. Outline of the proof: On a particular level of the tree you will make about n/2 comparisons before you pick your branch and descend. The number of leaves is l = pow(n,k), so the number of levels is k = log(l)/log(n). The total number of comparisons will be something like (log(l)/2)*(n/log(n)). The first part is fixed, so we need to minimize n/log(n). That function reaches its minimum at n=e, but unfortunately n has to be an integer value. Among the integers, n=3 is the best, with n=2 and n=4 tied at as close seconds. Of course, in practice you will also need to do updates to the weights (actually more often than picking random points), so the number of levels in the tree becomes more relevant, which favors larger values of n. My original implementation had n=2 and the tree was beautifully implemented as an array, in the same style as the usual implementation of a heap. However, Rémi pointer out that cheaper updates were important. I think the two-level solution using rows is easy to implement and probably close to optimal. Álvaro. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
