the bias of %n would not be detectable in this situation...but if you wanted it right...the perfect thing is not hard.
On Fri, Oct 27, 2017 at 3:44 PM, T L <tapir....@gmail.com> wrote: > 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> >> 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> 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...@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. > -- Michael T. Jones michael.jo...@gmail.com -- 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.
