E
August 13, 2010
This puzzle made the rounds of the programmer mathematician blogs a while ago:
Given a random number generator that returns a real number between zero and one, how many random numbers must be selected, on average, to make their accumulated total greater than one?
Your task is to write a program that answers the question above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
[…] Praxis – E By Remco Niemeijer In today’s Programming Praxis exercise our task is to determine how many random numbers between 0 and 1 we […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/08/13/programming-praxis-e/ for a version with comments):
A couple of improvements could be made. I left the j variable in accidently, it is unused. In C++, the scope of the sum value could be confined to the for loop in which it appears. A do { } while loop would mean that I didnt have two different increments of the ttrial variable.
Here’s my solution in Clojure:
PLT “racket”:
#! /bin/sh
#| Hey Emacs, this is -*-scheme-*- code!
#$Id$
exec mzscheme -l errortrace –require “$0″ –main — ${1+”$@”}
|#
#lang scheme
;; https://programmingpraxis.com/2010/08/13/e/
(define (trial)
(let loop ([number-of-numbers 0]
[sum 0])
(if (inexact
(/ (apply + outcomes)
(length outcomes)))))
(provide main)
/me tips his hat to Mark VandeWettering, Oregon ’86 or thereabouts
Gaah. Stupid wordpad.
gistfile1
hosted with ❤ by GitHub
Here’s a Python implementation:
import random
import sys
random.seed()
numIterations = int(sys.argv[1])
count = 0.0
sum = 0.0
for i in range(numIterations):
sum += random.random()
if sum > 1.0:
count += 1.0
sum = 0.0
print numIterations/count
A naive ruby implementation
Here’s a Java solution:
The output, as expected, is 2.72197.
(* OCaml *)
let test () =
let acc = ref 0. and cpt = ref 0 in
while !acc < 1. do
incr cpt;
acc := !acc +. (Random.float 1.);
done;
!cpt;;
let mean n =
let rec aux n =
if n = 0
then 0
else test () + aux (n-1)
in
(float_of_int (aux n)) /. (float_of_int n);;
print_string ((string_of_float (mean 10000))^”\n”);;
(* Purely functional looks even better (well, as in “no references”…) *)
let rec test acc cpt =
if acc < 1.
then test (acc +. (Random.float 1.)) (cpt + 1)
else cpt
let mean n =
let rec aux n =
if n = 0
then 0
else test 0. 0 + aux (n-1)
in (float_of_int (aux n)) /. (float_of_int n);;
print_string ((string_of_float (mean 10000))^”\n”);;
[…] about computing Euler’s Number, e, using Clojure. It wasn’t until I saw the idea on Programming Praxis, though, that I decided to just do […]
//quick and dirty javascript
var getRandomCount = function(ctr,buf){
while(buf < 1){
var nbr = Math.random();
ctr = ctr + 1;
buf = buf + nbr;
}
return ctr;
}
var getAverageNumberOfTimes = function(iter){
var total = 0;
for(i=0;i<iter;i++){
total = total + getRandomCount(0,0);
}
return total;
}
alert(getAverageNumberOfTimes(1000)/1000);
C#
Random randNum = new Random();
int trials = 1000000;
long totalTrials = 0;
double i = 0;
for (int runs = 0; runs < trials; i = 0, runs++)
for (totalTrials++ ; (i += randNum.NextDouble()) < 1.0; totalTrials++) ;
Console.WriteLine((float)totalTrials / trials);
Console.ReadLine();
Here is a FORTH version, without floating point.
A random 32 bit number is treated as binary random between 0-1. When overflow occurs (requires 33 bits), it is interpreted as exceeding 1.0.
And here is session with SwiftForth :-