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

### 16 Responses to “E”

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

2. Remco Niemeijer said

```import Control.Monad
import System.Random

f :: Float -> IO Int
f s = if s > 1 then return 0 else fmap succ . f . (s +) =<< randomRIO (0, 1)

test :: Int -> IO Float
test n = fmap ((/ toEnum n) . toEnum . sum) \$ replicateM n (f 0)

main :: IO ()
main = print =<< test 100000
```
3. ```#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) ;
}
```
4. 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.

5. 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.7184935
```
6. Eric Hanchrow said

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

7. Eric Hanchrow said

 #! /bin/sh #| Hey Emacs, this is -*-scheme-*- code! #\$Id\$ exec mzscheme -l errortrace –require "\$0" –main — \${1+"\$@"} |# #lang scheme (define (trial) (let loop ([number-of-numbers 0] [sum 0]) (if (<= 1 sum) number-of-numbers (loop (add1 number-of-numbers) (+ (random) sum))))) (define (main) (let ([outcomes (for/list ([t (in-range 0 1000000)]) (trial))]) (exact->inexact (/ (apply + outcomes) (length outcomes))))) (provide main)

view raw
gistfile1
hosted with ❤ by GitHub

8. Aidan said

Here’s a Python implementation:
``` import random import sys```

``` random.seed() numIterations = int(sys.argv) 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 ```

9. slabounty said

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 }"
```
10. 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.

11. Axio said

(* 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”);;

12. Axio said

(* 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”);;

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

14. Jonathan Barton said

//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);
}
}

15. Rodrigo Menezes said

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);

16. David said

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

```1000 trials 2.7150  ok
10000 trials 2.7191  ok
100000 trials 2.7163  ok
713742 trials 2.7175  ok
```