Unbias a random generator: Difference between revisions
Content added Content deleted
(=={{header|Julia}}=={{works with|Julia|0.6}}<lang julia></lang>{{out}}<pre></pre>) |
(Added Julia language) |
||
Line 940: | Line 940: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|Julia}}== |
||
{{works with|Julia|0.6}} |
|||
<lang lb> |
|||
for N =3 to 6 ' bias as defined |
|||
tests =1E5 ' number of tests to do |
|||
<lang julia>randN(N) = () -> rand(1:N) == 1 ? 1 : 0 |
|||
print " Biased bit-string, '1' chosen on average once out of "; N; " times . . . " |
|||
function unbiased(biased::Function) |
|||
this, that = biased(), biased() |
|||
while this == that this, that = biased(), biased() end |
|||
return this |
|||
end |
|||
@printf "%2s | %10s | %5s | %5s | %8s" "N" "bias./unb." "1s" "0s" "pct ratio" |
|||
countZeros =0: countOnes =0 |
|||
const nrep = 10000 |
|||
for N in 3:6 |
|||
biased = randN(N) |
|||
v = collect(biased() for __ in 1:nrep) |
|||
for j =1 to tests |
|||
v1, v0 = count(v .== 1), count(v .== 0) |
|||
@printf("%2i | %10s | %5i | %5i | %5.2f%%\n", N, "biased", v1, v0, 100 * v1 / nrep) |
|||
if b =1 then countOnes =countOnes +1 else countZeros =countZeros +1 |
|||
next j |
|||
v = collect(unbiased(biased) for __ in 1:nrep) |
|||
print " "; countZeros; " zeros & "; countOnes; " ones. Ratio ="; countOnes /tests |
|||
v1, v0 = count(v .== 1), count(v .== 0) |
|||
@printf("%2i | %10s | %5i | %5i | %5.2f%%\n", N, "unbiased", v1, v0, 100 * v1 / nrep) |
|||
end</lang> |
|||
{{out}} |
|||
print " Unbiased bit-string . . . " |
|||
<pre> N | bias./unb. | 1s | 0s | pct ratio |
|||
3 | biased | 3286 | 6714 | 32.86% |
|||
3 | unbiased | 4986 | 5014 | 49.86% |
|||
4 | biased | 2473 | 7527 | 24.73% |
|||
4 | unbiased | 4986 | 5014 | 49.86% |
|||
5 | biased | 1992 | 8008 | 19.92% |
|||
5 | unbiased | 5121 | 4879 | 51.21% |
|||
6 | biased | 1663 | 8337 | 16.63% |
|||
6 | unbiased | 5040 | 4960 | 50.40%</pre> |
|||
=={{header|Kotlin}}== |
|||
countZeros =0: countOnes =0 |
|||
{{trans|Java}} |
|||
<lang scala>// version 1.1.2 |
|||
fun biased(n: Int) = Math.random() < 1.0 / n |
|||
for j =1 to tests |
|||
b =unBiased( N) |
|||
if b =1 then countOnes =countOnes +1 else countZeros =countZeros +1 |
|||
next j |
|||
fun unbiased(n: Int): Boolean { |
|||
print " "; countZeros; " zeros & "; countOnes; " ones. Ratio ="; countOnes /tests |
|||
var a: Boolean |
|||
var b: Boolean |
|||
next N |
|||
do { |
|||
a = biased(n) |
|||
b = biased(n) |
|||
} |
|||
while (a == b) |
|||
return a |
|||
} |
|||
fun main(args: Array<String>) { |
|||
print " DONE." |
|||
val m = 50_000 |
|||
val f = "%d: %2.2f%% %2.2f%%" |
|||
for (n in 3..6) { |
|||
var c1 = 0 |
|||
var c2 = 0 |
|||
for (i in 0 until m) { |
|||
if (biased(n)) c1++ |
|||
if (unbiased(n)) c2++ |
|||
} |
|||
println(f.format(n, 100.0 * c1 / m, 100.0 * c2 / m)) |
|||
} |
|||
}</lang> |
|||
Sample output: |
|||
end ' _____________________________________________________ |
|||
function randN( n) |
|||
if rnd( 1) <( 1 /n) then randN =1 else randN =0 |
|||
end function |
|||
function unBiased( n) |
|||
do |
|||
n1 =randN( n) |
|||
n2 =randN( n) |
|||
loop until n1 <>n2 |
|||
unBiased =n1 |
|||
end function |
|||
</lang> |
|||
Output: |
|||
<pre> |
<pre> |
||
3: 33.19% 50.19% |
|||
Biased bit-string, '1' chosen once out of 3 times . . . |
|||
4: 25.29% 49.85% |
|||
664236 zeros & 335764 ones. Ratio =0.335764 |
|||
5: 19.91% 50.07% |
|||
Unbiased bit-string . . . |
|||
6: 16.71% 50.14% |
|||
500349 zeros & 499651 ones. Ratio =0.499651 |
|||
Biased bit-string, '1' chosen once out of 4 times . . . |
|||
748122 zeros & 251878 ones. Ratio =0.251878 |
|||
Unbiased bit-string . . . |
|||
499728 zeros & 500272 ones. Ratio =0.500272 |
|||
Biased bit-string, '1' chosen once out of 5 times . . . |
|||
798517 zeros & 201483 ones. Ratio =0.201483 |
|||
Unbiased bit-string . . . |
|||
500044 zeros & 499956 ones. Ratio =0.499956 |
|||
Biased bit-string, '1' chosen once out of 6 times . . . |
|||
832096 zeros & 167904 ones. Ratio =0.167904 |
|||
Unbiased bit-string . . . |
|||
500407 zeros & 499593 ones. Ratio =0.499593 |
|||
</pre> |
</pre> |
||