Yes, the problem is fixed totally on tip. The tip is using the normal mod operation "fastrand() % n".
On Friday, October 27, 2017 at 5:17:53 PM UTC-4, Axel Wagner wrote: > > It turns out that, apparently, at least on tip (what I linked to) the > fastrand implementation itself is actually pretty good. You might want to > re-run the test on tip. fastrandn will still be somewhat biased. > > On Fri, Oct 27, 2017 at 11:05 PM, Axel Wagner <axel.wa...@googlemail.com > <javascript:>> wrote: > >> Neither. fastrand is not a perfect PRNG, as that doesn't exist (much less >> in…fast) and the reduction is biased (necessarily, unless you are going to >> resort to rejection sampling, which is slow). >> >> On Fri, Oct 27, 2017 at 11:00 PM, T L <tapi...@gmail.com <javascript:>> >> wrote: >> >>> >>> >>> On Friday, October 27, 2017 at 4:57:46 PM UTC-4, T L wrote: >>>> >>>> >>>> >>>> On Friday, October 27, 2017 at 4:51:15 PM UTC-4, Axel Wagner wrote: >>>>> >>>>> Yes. The random number generator employed (right above from what I >>>>> linked to; the fastrand function), apparently, is unsurprisingly >>>>> imperfect. >>>>> >>>> >>>> Why not to maintain a global start index for each goroutine? >>>> The value of the start index is the number of executed select blocks in >>>> a goroutine. >>>> So that we can change the fastrandn implementation to >>>> "return uint32(uint64(fastrand() + current_g.numExecutedSelects) * >>>> uint64(n) >> 32)" >>>> >>> >>> Aha, which function is unfair, fastrand or fastrandn? >>> If fastrandn is unfair, then the above trick doesn't work. >>> >>>> >>>> >>>>> >>>>> On Fri, Oct 27, 2017 at 10:47 PM, T L <tapi...@gmail.com> wrote: >>>>> >>>>>> It is also not uniform for powers of two. >>>>>> If there a 8 cases, the sixth one will only get a 80% chance of the >>>>>> first one. >>>>>> >>>>>> On Friday, October 27, 2017 at 4:33:47 PM UTC-4, Axel Wagner wrote: >>>>>>> >>>>>>> The code suggests, that select is indeed not fair: >>>>>>> >>>>>>> https://github.com/golang/go/blob/a4d03a9bf7604b727abd0a1ebfb118ff6366ee50/src/runtime/stubs.go#L109 >>>>>>> Which seems fine to me. A fair, uniform PRNG for ranges that are not >>>>>>> powers of two gets a fair bit of overhead and no program should depend >>>>>>> on >>>>>>> uniformity of select for correctness anyway. >>>>>>> >>>>>>> On Fri, Oct 27, 2017 at 10:28 PM, T L <tapi...@gmail.com> wrote: >>>>>>> >>>>>>>> It looks the distribution of the RNG results depends on the number >>>>>>>> of cases. >>>>>>>> The third case only gets the lowest possibility of there are 6 >>>>>>>> cases, >>>>>>>> >>>>>>>> >>>>>>>> On Friday, October 27, 2017 at 4:21:12 PM UTC-4, T L wrote: >>>>>>>>> >>>>>>>>> A better example to show the inhomogeneity of the selected >>>>>>>>> possibilities of each case. >>>>>>>>> >>>>>>>>> package main >>>>>>>>> >>>>>>>>> import "fmt" >>>>>>>>> >>>>>>>>> func main() { >>>>>>>>> foo := make(chan struct{}) >>>>>>>>> close(foo) >>>>>>>>> var a, b, c, d, e, f, g float64 >>>>>>>>> fa := func(){a++} >>>>>>>>> fb := func(){b++} >>>>>>>>> fc := func(){c++} >>>>>>>>> fd := func(){d++} >>>>>>>>> fe := func(){e++} >>>>>>>>> ff := func(){f++} >>>>>>>>> fg := func(){g++} >>>>>>>>> for i := 0; i < 1000000; i++ { >>>>>>>>> select { >>>>>>>>> case <-foo: fa() >>>>>>>>> case <-foo: fb() >>>>>>>>> case <-foo: fc() >>>>>>>>> case <-foo: fd() >>>>>>>>> case <-foo: fe() >>>>>>>>> case <-foo: ff() >>>>>>>>> case <-foo: fg() >>>>>>>>> } >>>>>>>>> } >>>>>>>>> fmt.Println(a/a) >>>>>>>>> fmt.Println(b/a) >>>>>>>>> fmt.Println(c/a) >>>>>>>>> fmt.Println(d/a) >>>>>>>>> fmt.Println(e/a) >>>>>>>>> fmt.Println(f/a) >>>>>>>>> fmt.Println(g/a) >>>>>>>>> } >>>>>>>>> >>>>>>>>> result: >>>>>>>>> >>>>>>>>> 1 >>>>>>>>> 0.9999052991869258 >>>>>>>>> 0.9015652691532394 >>>>>>>>> 0.9691884140319548 >>>>>>>>> 0.966320332264567 >>>>>>>>> 0.9669020658305938 >>>>>>>>> 0.9604624105415533 >>>>>>>>> >>>>>>>>> On Friday, October 27, 2017 at 4:08:39 PM UTC-4, T L wrote: >>>>>>>>>> >>>>>>>>>> The following program constantly prints a value larger than 1.02 >>>>>>>>>> >>>>>>>>>> package main >>>>>>>>>> >>>>>>>>>> import "fmt" >>>>>>>>>> >>>>>>>>>> func main() { >>>>>>>>>> foo, bar := make(chan struct{}), make(chan struct{}) >>>>>>>>>> close(foo) >>>>>>>>>> close(bar) >>>>>>>>>> x, y := 0.0, 0.0 >>>>>>>>>> f := func(){x++} >>>>>>>>>> g := func(){y++} >>>>>>>>>> for i := 0; i < 1000000; i++ { >>>>>>>>>> select { >>>>>>>>>> case <-bar: g() >>>>>>>>>> case <-foo: f() >>>>>>>>>> case <-bar: g() >>>>>>>>>> case <-foo: f() >>>>>>>>>> case <-bar: g() >>>>>>>>>> case <-foo: f() >>>>>>>>>> } >>>>>>>>>> } >>>>>>>>>> fmt.Println(x/y) >>>>>>>>>> } >>>>>>>>>> >>>>>>>>>> if the last two cases are removed, then it becomes quit fair. >>>>>>>>>> >>>>>>>>> -- >>>>>>>> You received this message because you are subscribed to the Google >>>>>>>> Groups "golang-nuts" group. >>>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>>> send an email to golang-nuts...@googlegroups.com. >>>>>>>> For more options, visit https://groups.google.com/d/optout. >>>>>>>> >>>>>>> >>>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "golang-nuts" group. >>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>> send an email to golang-nuts...@googlegroups.com. >>>>>> For more options, visit https://groups.google.com/d/optout. >>>>>> >>>>> >>>>> -- >>> You received this message because you are subscribed to the Google >>> Groups "golang-nuts" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to golang-nuts...@googlegroups.com <javascript:>. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
