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.wagner...@googlemail.com > 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 <tapir....@gmail.com> 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/a4d03a9bf7604b727abd0a1ebf >>>>>> b118ff6366ee50/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+unsubscr...@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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
