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.
