## 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.

Pages: 1 2

[...] 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

;; http://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

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 :-