Birthday problem: Difference between revisions
→{{header|Go}}: remove timings, add random source per goroutine, which improves speed, add solution closer to C solution, which is also faster.
m (→version 1: added/changed comments and whitespace, used a template for the output section. optimized parts of the code.) |
(→{{header|Go}}: remove timings, add random source per goroutine, which improves speed, add solution closer to C solution, which is also faster.) |
||
Line 467:
5 collision: 313 people, P = 0.501105 +/- 0.000221016</pre>
=={{header|Go}}==
{{trans|C}}
<lang go>package main
import (
"fmt"
"math"
"math/rand"
"time"
)
const (
DEBUG = 0
DAYS = 365
n_sigmas = 5.
WORKERS = 16 // concurrent worker processes
RUNS = 1000 // runs per flight
)
func simulate1(p, n int, r *rand.Rand) int {
var days [DAYS]int
for i := 0; i < p; i++ {
days[r.Intn(DAYS)]++
}
for _, d := range days {
if d >= n {
return 1
}
}
return 0
}
// send yes's per fixed number of simulate1 runs until canceled
func work(p, n int, ych chan int, cancel chan bool) {
r := rand.New(rand.NewSource(time.Now().Unix() + rand.Int63()))
for {
select {
case <-cancel:
return
default:
}
y := 0
for i := 0; i < RUNS; i++ {
y += simulate1(p, n, r)
}
ych <- y
}
}
func prob(np, n int) (p, d float64) {
ych := make(chan int, WORKERS)
cancel := make(chan bool)
for i := 0; i < WORKERS; i++ {
go work(np, n, ych, cancel)
}
var runs, yes int
for {
yes += <-ych
runs += RUNS
fr := float64(runs)
p = float64(yes) / fr
d = math.Sqrt(p * (1 - p) / fr)
if DEBUG > 1 {
fmt.Println("\t\t", np, yes, runs, p, d)
}
// .5 here is the "even chance" threshold
if !(math.Abs(p-.5) < n_sigmas*d) {
close(cancel)
break
}
}
if DEBUG > 1 {
fmt.Println()
}
return
}
func find_half_chance(n int) (mid int, p, dev float64) {
reset:
lo := 0
hi := DAYS*(n-1) + 1
for {
mid = (hi + lo) / 2
p, dev = prob(mid, n)
if DEBUG > 0 {
fmt.Println("\t", lo, mid, hi, p, dev)
}
if p < .5 {
lo = mid + 1
} else {
hi = mid
}
if hi < lo {
if DEBUG > 0 {
fmt.Println("\tMade a mess, will redo.")
}
goto reset
}
if !(lo < mid || p < .5) {
break
}
}
return
}
func main() {
for n := 2; n <= 5; n++ {
np, p, d := find_half_chance(n)
fmt.Printf("%d collision: %d people, P = %.4f ± %.4f\n",
n, np, p, d)
}
}</lang>
<pre>
2 collision: 23 people, P = 0.5081 ± 0.0016
3 collision: 88 people, P = 0.5155 ± 0.0029
4 collision: 187 people, P = 0.5041 ± 0.0008
5 collision: 313 people, P = 0.5015 ± 0.0003
</pre>
'''Also based on the C version:'''
<lang go>package main
import (
"fmt"
"math"
"math/rand"
"runtime"
"time"
)
type ProbeRes struct {
np int
p, d float64
}
type Frac struct {
n int
d int
}
var DaysInYear int = 365
func main() {
sigma := 5.0
for i := 2; i <= 5; i++ {
res
fmt.Printf("%d collision: %d people, P = %
i, res.np, res.p, res.d)
}
}
func GetNP(n int, n_sigmas, p_thresh float64) (res ProbeRes
res.np = DaysInYear * (n - 1)
tmp := probe(i, n, n_sigmas, p_thresh)
if tmp.p
res = tmp
}
}
return
}
var numCPU = runtime.NumCPU()
func probe(np, n int, n_sigmas, p_thresh float64) ProbeRes {
var p, d float64
var runs, yes int
cRes := make(chan Frac,
for i := 0; i <
go SimN(np, n, 25, cRes)
}
for math.Abs(p
f := <-cRes
yes += f.n
Line 521 ⟶ 643:
p = float64(yes) / float64(runs)
d = math.Sqrt(p * (1 - p) / float64(runs))
go SimN(np, n, runs/3, cRes)
}
return ProbeRes{np, p, d}
}
func SimN(np, n, ssize int, c chan Frac) {
r := rand.New(rand.NewSource(time.Now().UnixNano() + rand.Int63()))
yes := 0
for i := 0; i < ssize; i++
if Sim(np, n, r) {
yes++
}
}
c <- Frac{yes, ssize}
}
func Sim(p, n int, r *rand.Rand) (
Cal := make([]int, DaysInYear)
for i := 0; i < p
Cal[
}
for _, v := range Cal {
if v >= n {
res = true
Line 549 ⟶ 672:
}</lang>
{{Out}}
<pre>
5 collision: 313 people, P = 0.5011 ± 0.0002
</pre>
=={{header|Hy}}==
| |||