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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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