Birthday problem: Difference between revisions

Content added Content deleted
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: Line 467:
5 collision: 313 people, P = 0.501105 +/- 0.000221016</pre>
5 collision: 313 people, P = 0.501105 +/- 0.000221016</pre>
=={{header|Go}}==
=={{header|Go}}==
{{trans|C}}
Based on the C version but multithreaded using Go channels
<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
<lang go>package main


import (
import (
"math/rand"
"fmt"
"fmt"
"time"
"math"
"math"
"math/rand"
"runtime"
"runtime"
"time"
)
)


type ProbeRes struct {
type ProbeRes struct {
np int
np int
p, d float64
p, d float64
}
}

type Frac struct {
type Frac struct {
n int
n int
d int
d int
}
}

var DaysInYear int = 365
var DaysInYear int = 365


func main(){
func main() {
sigma := 5.0
sigma := 5.0
for i := 2; i <= 5;i++{
for i := 2; i <= 5; i++ {
res, dur := GetNP(i,sigma,0.5)
res := GetNP(i, sigma, 0.5)
fmt.Printf("%d collision: %d people, P = %f +/- %f, took %s\n",i,res.np,res.p,res.d,dur)
fmt.Printf("%d collision: %d people, P = %.4f ± %.4f\n",
i, res.np, res.p, res.d)
}
}
}
}


func GetNP(n int, n_sigmas, p_thresh float64) (res ProbeRes, dur time.Duration){
func GetNP(n int, n_sigmas, p_thresh float64) (res ProbeRes) {
res.np = DaysInYear * (n - 1)
start := time.Now()
res.np = DaysInYear*(n-1)
for i := 0; i < DaysInYear*(n-1); i++ {
tmp := probe(i, n, n_sigmas, p_thresh)
for i := 0; i < DaysInYear * (n-1);i++ {
tmp := probe(i,n,n_sigmas,p_thresh)
if tmp.p > p_thresh && tmp.np < res.np {
if tmp.p > p_thresh && tmp.np < res.np{
res = tmp
res = tmp
}
}
}
}
dur = time.Since(start)
return
return
}
}

func probe(np,n int, n_sigmas, p_thresh float64) ProbeRes{
var numCPU = runtime.NumCPU()
var p,d float64

func probe(np, n int, n_sigmas, p_thresh float64) ProbeRes {
var p, d float64
var runs, yes int
var runs, yes int
cRes := make(chan Frac,runtime.NumCPU())
cRes := make(chan Frac, numCPU)
for i:=0; i < runtime.NumCPU();i++{
for i := 0; i < numCPU; i++ {
go SimN(np,n,25,cRes)
go SimN(np, n, 25, cRes)
}
}
for math.Abs(p - p_thresh) < n_sigmas * d || runs < 100{
for math.Abs(p-p_thresh) < n_sigmas*d || runs < 100 {
f := <-cRes
f := <-cRes
yes += f.n
yes += f.n
Line 521: Line 643:
p = float64(yes) / float64(runs)
p = float64(yes) / float64(runs)
d = math.Sqrt(p * (1 - p) / float64(runs))
d = math.Sqrt(p * (1 - p) / float64(runs))
go SimN(np,n,runs/3,cRes)
go SimN(np, n, runs/3, cRes)


}
}
return ProbeRes{np,p,d}
return ProbeRes{np, p, d}
}
}
func SimN(np,n, ssize int, c chan Frac){
func SimN(np, n, ssize int, c chan Frac) {
r := rand.New(rand.NewSource(time.Now().UnixNano() + rand.Int63()))
yes := 0
yes := 0
for i := 0;i < ssize;i++ {
for i := 0; i < ssize; i++ {
if Sim(np,n) {
if Sim(np, n, r) {
yes++
yes++
}
}


}
}
c <- Frac{yes,ssize}
c <- Frac{yes, ssize}
}
}
func Sim(p,n int) ( res bool){
func Sim(p, n int, r *rand.Rand) (res bool) {
Cal := make([]int,DaysInYear)
Cal := make([]int, DaysInYear)
for i := 0;i < p ;i++{
for i := 0; i < p; i++ {
Cal[rand.Intn(DaysInYear)]++
Cal[r.Intn(DaysInYear)]++
}
}
for _,v := range Cal{
for _, v := range Cal {
if v >= n {
if v >= n {
res = true
res = true
Line 549: Line 672:
}</lang>
}</lang>
{{Out}}
{{Out}}
<pre>
<pre>2 collision: 23 people, P = 0.506375 +/- 0.001197, took 1.5777555s
3 collision: 88 people, P = 0.516045 +/- 0.002945, took 2m17.5473911s
2 collision: 23 people, P = 0.5068 ± 0.0013
4 collision: 187 people, P = 0.502643 +/- 0.000507, took 1m11.1573736s
3 collision: 88 people, P = 0.5148 ± 0.0028
5 collision: 313 people, P = 0.501907 +/- 0.000367, took 1m49.7901966s</pre>
4 collision: 187 people, P = 0.5020 ± 0.0004
5 collision: 313 people, P = 0.5011 ± 0.0002
</pre>


=={{header|Hy}}==
=={{header|Hy}}==
Retrieved from "https://rosettacode.org/wiki/Birthday_problem"