Unbias a random generator: Difference between revisions

 

 

This task is an implementation of [http://en.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor Von Neumann debiasing], first described in a 1951 paper.

<br><br>

 

=={{header|Ada}}==

 

procedure Bias_Unbias is

Ada.Text_IO.New_Line;

end loop;

Output:<pre> I Biased% UnBiased%

3 32.87 49.80

=={{header|Aime}}==

{{trans|C}}

biased(integer bias)

{

 

0;

Output:<pre>bias 3: 33.51% vs 50.27%

bias 4: 24.97% vs 49.99%

=={{header|AutoHotkey}}==

{{output?}}

Random, q, 0, 4

return q=4

MsgBox % "Unbiased probability of a 1 occurring: " Errorlevel/1000

StringReplace, junk, t, 1, , UseErrorLevel

 

=={{header|BBC BASIC}}==

biased% = 0

unbiased% = 0

= A%

Output:

<pre>

 

=={{header|C}}==

#include <stdlib.h>

 

return 0;

output

<pre>bias 3: 33.090% vs 49.710%

bias 5: 19.760% vs 49.650%

bias 6: 16.740% vs 50.030%</pre>

 

=={{header|C sharp}}==

 

 

namespace Unbias

}

}

 

'''Sample Output'''

 

=={{header|Clojure}}==

(if (< (rand 2) (/ n)) 0 1))

 

[4 0.87684 0.5023]

[5 0.90122 0.49728]

 

=={{header|CoffeeScript}}==

biased_rand_function = (n) ->

# return a function that returns 0/1 with

stats "biased", f_biased

stats "unbiased", f_unbiased

output

<pre>

 

=={{header|Common Lisp}}==

 

(defun unbiased (n)

(let ((u (loop repeat 10000 collect (unbiased n)))

(b (loop repeat 10000 collect (biased n))))

output

<pre>3: unbiased 4992 biased 3361

 

=={{header|D}}==

 

enum biased = (in int n) /*nothrow*/ => uniform01 < (1.0 / n);

M.iota.map!(_=> n.biased).sum * 100.0 / M,

M.iota.map!(_=> n.unbiased).sum * 100.0 / M);

{{out}}

<pre>3: 33.441% 49.964%

5: 19.958% 49.987%

6: 16.660% 49.890%</pre>

 

=={{header|Elena}}==

{{trans|C#}}

extension op : IntNumber

public program()

{

{

int biasedZero := 0;

int unbiasedOne := 0;

{

if(n.randN()) { biasedOne += 1 } else { biasedZero += 1 };

unbiasedZero, unbiasedOne, unbiasedZero / 1000, unbiasedOne / 1000)

}

{{out}}

<pre>

 

=={{header|Elixir}}==

def randN(n) do

if :rand.uniform(n) == 1, do: 1, else: 0

ys = for _ <- 1..m, do: Random.unbiased(n)

IO.puts "#{n} #{Enum.sum(xs) / m} #{Enum.sum(ys) / m}"

 

{{out}}

 

=={{header|ERRE}}==

 

FUNCTION RANDN(N)

END FOR

END PROGRAM

{{out}}

<pre>N = 3 : biased = 32.66 , unbiased = 49.14

 

=={{header|Euphoria}}==

return rand(N) = 1

end function

end for

printf(1, "%d: %5.2f%% %5.2f%%\n", {b, 100 * cb / n, 100 * cu / n})

 

Output:

 

=={{header|F_Sharp|F#}}==

 

let random = Random()

printfn "%d: %5.2f%% %5.2f%%"

b (100. * float !cb / float n) (100. * float !cu / float n)

{{out}}

<pre>3: 33.26% 49.97%

 

=={{header|Factor}}==

IN: rosetta-code.unbias

 

] each ;

 

{{out}}

<pre>

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

 

end function

 

Output:

<pre>3: 33.337% 49.971%

5: 19.971% 49.987%

6: 16.688% 50.097%</pre>

 

=={{header|GAP}}==

local v, rand;

v := [1 .. n - 1]*0;

# [ 4, 249851, 500663 ],

# [ 5, 200532, 500448 ],

 

=={{header|Go}}==

 

import (

u[1], u[0], float64(u[1])*100/samples)

}

Output:

<pre>

=={{header|Haskell}}==

The first task:

import Control.Monad

import Text.Printf

 

randN :: MonadRandom m => Int -> m Int

 

Examples of use:

 

The second task. Returns the unbiased generator for any given random generator.

unbiased g = do x <- g

y <- g

 

Examples of use:

 

The third task:

where

showCounts b = do

printf "n = %d biased: %d%% unbiased: %d%%\n" b r1 r2

 

Output:

This solution works in both languages. Both <tt>randN</tt> and

<tt>unbiased</tt> are generators in the Icon/Unicon sense.

iters := \A[1] | 10000

write("ratios of 0 to 1 from ",iters," trials:")

procedure randN(n)

repeat suspend if 1 = ?n then 1 else 0

and a sample run:

<pre>->ubrn 100000

 

=={{header|J}}==

 

Example use:

 

1 0 0 0 1 0 0 0 0 0

unbiased 10#6

 

Some example counts (these are counts of the number of 1s which appear in a test involving 100 random numbers):

 

30

+/randN 100#4

49

+/unbiased 100#6

 

 

=={{header|Java}}==

public static boolean biased(int n) {

return Math.random() < 1.0 / n;

}

}

Output:

<pre>3: 33,11% 50,23%

6: 17.00% 49.88%</pre>

 

 

 

 

 

<pre>

</pre>

 

=={{header|Julia}}==

 

randN(N) = () -> rand(1:N) == 1 ? 1 : 0

v1, v0 = count(v .== 1), count(v .== 0)

@printf("%2i | %10s | %5i | %5i | %5.2f%%\n", N, "unbiased", v1, v0, 100 * v1 / nrep)

 

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

 

fun biased(n: Int) = Math.random() < 1.0 / n

println(f.format(n, 100.0 * c1 / m, 100.0 * c2 / m))

}

 

Sample output:

 

=={{header|Lua}}==

local function randN(n)

return function()

 

demonstrate(100000)

 

Output:

</pre>

 

TableForm[

Table[{n, Total[rand[n, count]]/count // N,

Total[#]/Length[#] &@unbiased[n, count] // N}, {n, 3, 6}],

3 0.33312 0.500074

4 0.24932 0.499883

5 0.1998 0.498421

 

=={{header|NetRexx}}==

{{trans|Java}}

options replace format comments java crossref symbols binary

 

end n

return

'''Output:'''

<pre>

=={{header|Nim}}==

{{trans|Python}}

 

 

 

result = biased()

var that = biased()

var cnt0, cnt1 = 0

for x in v:

 

v = newSeqWith(1_000_000, unbiased(biased))

cnt1 = 0

for x in v:

 

=={{header|OCaml}}==

 

if Random.int n = 0 then 1 else 0

 

Printf.printf "%d: %5.2f%% %5.2f%%\n"

b (100.0 *. float !cb /. float n) (100.0 *. float !cu /. float n)

 

Output:

=={{header|PARI/GP}}==

GP's random number generation is high-quality, using Brent's [http://maths.anu.edu.au/~brent/random.html XORGEN]. Thus this program is slow: the required 400,000 unbiased numbers generated through this bias/unbias scheme take nearly a second. This requires about two million calls to <code>random</code>, which in turn generate a total of about three million calls to the underlying random number generator through the rejection strategy. The overall efficiency of the scheme is 0.8% for 32-bit and 0.4% for 64-bit...

unbiased(N)={

my(a,b);

)

};

 

Output:

 

=={{header|Perl}}==

my $n = shift;

return int(rand($n) / ($n - 1));

100 * sqrt($fixed[0] * $fixed[1]) / ($fixed[0] + $fixed[1])**1.5);

 

Output:

<pre>Bias 3: 6684 3316, 66.84+-0.471% fixed: 2188 2228, 49.5471+-0.752%

 

=={{header|Phix}}==

{{out}}

<pre>

</pre>

 

=={{header|PicoLisp}}==

(if (= 1 (rand 1 N)) 1 0) )

 

(setq A (randN N))

(setq B (randN N)) ) )

Test:

(tab (2 1 7 2 7 2)

N ":"

(let S 0 (do 10000 (inc 'S (unbiased N))))

2 )

Output:

<pre> 3: 33.21 % 50.48 %

 

=={{header|PL/I}}==

test: procedure options (main); /* 20 Nov. 2012 */

 

 

end test;

Results:

<pre>

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

function randN ( [int]$N )

{

return $X

}

Note: The [pscustomobject] type accelerator, used to simplify making the test output look pretty, requires version 3.0 or higher.

$Tests = 1000

ForEach ( $N in 3..6 )

"Unbiased Ones out of $Test" = $Unbiased }

}

{{out}}

<pre>

 

=={{header|PureBasic}}==

If Random(n) <> 1

ProcedureReturn 0

output + #tab$ + " ratio=" + StrF(u_count(1) / #count * 100, 2) + "%" + #LF$

Next

Sample output:

<pre>---------------------------

 

=={{header|Python}}==

import random

 

v = [unbiased(biased) for x in range(1000000)]

v1, v0 = v.count(1), v.count(0)

 

'''Sample output'''

Biased(6) = Stats(count1=167561, count0=832439, percent=16.7561)

Unbiased = Stats(count1=499963, count0=500037, percent=49.996299999999998)</pre>

 

=={{header|R}}==

 

 

unbiased = function(f)

N = N,

biased = mean(replicate(samples, randN(N))),

 

Sample output:

 

=={{header|Racket}}==

#lang racket

;; Using boolean #t/#f instead of 1/0

(printf "Count: ~a => Biased: ~a%; Unbiased: ~a%.\n"

n (try% biased) (try% (unbiased biased))))

{{out}}

<pre>

(formerly Perl 6)

{{trans|Perl}}

return ( $n.rand / ($n - 1) ).Int;

}

}

printf "N=%d randN: %s, %4.1f%% unbiased: %s, %4.1f%%\n",

 

Output:<pre>N=3 randN: [676, 324], 32.4% unbiased: [517, 483], 48.3%

 

=={{header|REXX}}==

parse arg # R seed . /*obtain optional arguments from the CL*/

if #=='' | #=="," then #=1000 /*#: the number of SAMPLES to be used.*/

pct: return ctr( format(arg(1) / # * 100, , 2)'%' ) /*2 decimal digits.*/

randN: parse arg z; return random(1, z)==z /*ret 1 if rand==Z.*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

for n = 3 to 6

biased = 0

m = (random(m) = 1)

return m

Output:

<pre>

N = 5 : biased = 16.65%, unbiased = 48.86%

N = 6 : biased = 13.31%, unbiased = 49.96%

</pre>

 

=={{header|Ruby}}==

rand(bias) == 0 ? 1 : 0

end

counter[:bias] = bias

puts counter.values_at(*keys).join("\t")

{{output}}

<pre>

 

=={{header|Rust}}==

 

extern crate rand;

);

}

{{output}}

<pre>

 

=={{header|Scala}}==

 

def unbiased( n:Int ) = { def loop : Boolean = { val a = biased(n); if( a != biased(n) ) a else loop }; loop }

"%d: %2.2f%% %2.2f%%".format(i, 100.0*c1/m, 100.0*c2/m)

{{output}}

<pre>3: 33.09% 49.79%

 

=={{header|Seed7}}==

include "float.s7i";

 

" " <& flt(100 * sumUnbiased) / flt(tests) digits 3 lpad 6);

end for;

 

Output:

=={{header|Sidef}}==

{{trans|Raku}}

n.rand / (n-1) -> int

}

printf("N=%d randN: %s, %4.1f%% unbiased: %s, %4.1f%%\n",

n, [raw, fixed].map {|a| (a.dump, a[1] * 100 / iterations) }...)

{{out}}

<pre>

 

=={{header|Tcl}}==

proc randN n {expr {rand()*$n < 1}}

 

puts [format "unbiased %d => #0=%d #1=%d ratio=%.2f%%" $n $c(0) $c(1) \

[expr {100.*$c(1)/$i}]]

Sample output:

<pre>

biased 6 => #0=833623 #1=166377 ratio=16.64%

unbiased 6 => #0=500518 #1=499482 ratio=49.95%

</pre>

 

=={{header|zkl}}==

foreach N in ([3..6]){

"%d: biased: %3.2f%%, unbiased: %3.2f%%".fmt(N,

(0).reduce(Z,'wrap(s,_){ s+unbiased(randN.fp(N)) },0.0)/Z*100)

.println();

{{out}}

<pre>