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.
Advertisements
[…] 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):
#include <stdio.h> #include <stdlib.h> main() { int trials = 1000000 ; int ttrials = 0; int i, j ; double sum ; for (i=0; i<trials; i++) for (sum=0., ttrials++; (sum += drand48()) < 1.; ttrials++) ; printf("%f trials on average.\n", (double) ttrials / trials) ; }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:
(defn to-one [] (loop [times 0 sum 0] (cond (> sum 1) times :else (recur (inc times) (+ sum (rand)))))) (defn to-one-avg [n] (/ (reduce + (repeatedly n to-one)) n 1.0)) user=> (to-one-avg 10000000) 2.7184935PLT “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.
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
count_sum = 0 iterations = 1000 (1..iterations).each do sum = 0 count = 0 while sum < 1.0 do sum += rand count += 1 end count_sum += count end puts "#{count_sum.to_f / iterations }"Here’s a Java solution:
package progpraxis; import java.util.ArrayList; import java.util.List; import java.util.Random; public class E { public static void main(String[] args) { Random generator = new Random(); List<Integer> totalAttempts = new ArrayList<Integer>(); for (int i = 1; i <= 100000; i++) { double total = generator.nextDouble(); int attempts = 1; while (total <= 1.0) { total += generator.nextDouble(); attempts++; } totalAttempts.add(attempts); } double average = 0d; for (Integer number : totalAttempts) { average += number; } average = average / totalAttempts.size(); System.out.println("Average before surpassing 1: " + average); } }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.
\ multiply with carry RNG \ quickie MWC-0 (no lag, 2^63 period is good enough) create seed counter , create carry 48313 , : random ( -- r ) seed @ 4164903690 um* carry @ 0 d+ carry ! dup seed ! ; : trial ( -- n ) 0 0. ( stack: count rng ) BEGIN random 0 D+ rot 1+ -rot dup 0> UNTIL 2drop ; : trials ( n -- ) locals| n | 0 n 0 DO trial + LOOP 10000 n */ s>d <# # # # # [char] . hold #s #> type space ;And here is session with SwiftForth :-