Random Number Generators....

[RadiationX]

I have a problem that I really don't understand at all. In my previous
post I could get started on my projects I just had a few problems with
syntax errors. This problem is something that I don't conceptually
understand very well. Here it is:



Π – the ratio of the circumference of a circle to its diameter
– is one of the most common and important constants in mathematics.
It is an irrational number (a real number that cannot be expressed as
the ratio of two integers), but its value has been calculated to more
than a million decimal places using different formulas. (See, for
example, Petr Beckmann's A History of Π, St. Martin's Press: New York,
1971) In this assignment you will estimate the value of Π by
simulating randomly throwing darts at a target.

The figure at the left is a quarter circle of radius 1.0 inscribed in
a square of side 1.0 on the Cartesian plane. It can be show that area
of the dark blue quarter circle is Π/4. If we were to randomly throw d
darts at the square, and c of them landed in the circle, we could
estimate the value of Π/4 as c / d, so an approximation of Π is 4 * (
c / d ).

Your program should "throw" darts at the target by generating a
random coordinate pair (x, y) where x and y are floating point values
in the range [0.0, 1.0], which will represent the point the dart hit
the target. (You can generate numbers in this range with the expression
(double)rand()/RAND_MAX) .) This point will be inside the quarter
circle if:

sqrt( x2 + y2) <= 1.0

By maintaining counters for the number of darts landing in the
quarter circle and the the total number of darts thrown, the value of
Π can be approximated. The larger the number of darts thrown, the
better the approximation will be.

Your program should use a function that, each time it is called,
generates a new random coordinate pair, determines if this pair
represents a point inside the quarter circle, and returns a 1 if it is,
and a 0 if it is not. Your program should run a simulation for a
user-specified number of dart throws, and then display the estimated
value of Π and the percentage difference (percent error) between your
estimated value and the true value of Π; if your estimated value is p,
then the percent error is (( p - Π) / Π ) * 100. (The actual value of
Π to 15 significant figures is 3.14159265358979.)

___________________________________________________________________________

I do have some ideas about the variables that I need but I'm not sure
how to really implement the rand()/ RAND_MAX function... could someone
give a start in the right direction?

 

[Ulrich Eckhardt]

I do have some ideas about the variables that I need but I'm not sure
how to really implement the rand()/ RAND_MAX function... could someone
give a start in the right direction?

Both rand() and the associated constant RAND_MAX are part of the builtin C
API.

Uli

 

[Eric Sosman]

[...]

Your program should "throw" darts at the target by generating a
random coordinate pair (x, y) where x and y are floating point values
in the range [0.0, 1.0], which will represent the point the dart hit
the target. (You can generate numbers in this range with the expression
(double)rand()/RAND_MAX) [...]

I do have some ideas about the variables that I need but I'm not sure
how to really implement the rand()/ RAND_MAX function... could someone
give a start in the right direction?

You do not need to implement the rand() function nor
define RAND_MAX; they are part of the Standard C library.
Just #include <stdlib.h> and start using them.

 

[Walter Roberson]

Your program should use a function that, each time it is called,
generates a new random coordinate pair, determines if this pair
represents a point inside the quarter circle, and returns a 1 if it is,
and a 0 if it is not.

Be careful with that. A -lot- of implementations use
linear congruential random number generators for rand(), and
there is a well known problem with those that if you use
consequative samples from the stream as (x,y) pairs and graph
the results, instead of filling a square evenly, you will get
a number of noticably seperated diagnonal lines.

There are various corrections that one can use to reduce this
problem, but the best correction is to use a much better random number
generator. One that is said to be fast and very good is the
Mersenne Twister,
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

 

[Charles Krug]

___________________________________________________________________________

I do have some ideas about the variables that I need but I'm not sure
how to really implement the rand()/ RAND_MAX function... could someone
give a start in the right direction?

rand() and RAND_MAX return integers. so rand()/RAND_MAX either 0 or 1.
Think for a moment about why that must be true.

So there must be a techinque you can do to ensure that you get a
floating point answer from that calculation.

I suppose I could tell you it's a FAQ.....

You might want to print the value of RAND_MAX. Random number generators
start to show predictability when the number of numbers generated gets
"close to" the period of the pRNG. RAND_MAX isn't the period, but it
will give you a general idea how long the period is.

If RAND_MAX is 65535, you probably don't want to use more than 6000 or
so values from it in any simulation.

There are MANY things to learn about RNGs. Googling the topic will give
you more links than you might care to know.

Know that there is no software method that can produce "random numbers",
only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence of
numbers. For MOST applications, the difference doesn't matter all that
much.

When it DOES matter, it becomes a hardware problem involving things like
mason or gamma ray detectors.

 

[Walter Roberson]

Know that there is no software method that can produce "random numbers",
only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence of
numbers. For MOST applications, the difference doesn't matter all that
much.

When it DOES matter, it becomes a hardware problem involving things like
mason or gamma ray detectors.

Or Lava Lamps.

 

[Guillaume]

Know that there is no software method that can produce "random numbers",
only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence of
numbers.

That is true, but some generators (by the way, that should be called
pseudo-random generators, because, indeed, we have no means of
expressing true randomness algorithmically, or that would be a giant
step forward!) are pretty good.

One of the best I have used came from one of the D. Knuth books. Simple
enough, yet incredibly efficient.

You can also try this: http://www.random.org/
It can help either generating random sequences for direct use, or for
comparing your own generator with good random sequences, using a
statistical tool such as: http://www.fourmilab.ch/random/

At any rate, I strongly suggest implementing the one Knuth suggests.
IIRC, it memorizes 55 past numbers to generate a new one (so that
should help you find the algorithm in question in "The Art of Computer
Programming".

 

[Keith Thompson]

Be careful with that. A -lot- of implementations use
linear congruential random number generators for rand(), and
there is a well known problem with those that if you use
consequative samples from the stream as (x,y) pairs and graph
the results, instead of filling a square evenly, you will get
a number of noticably seperated diagnonal lines.

There are various corrections that one can use to reduce this
problem, but the best correction is to use a much better random number
generator. One that is said to be fast and very good is the
Mersenne Twister,
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

This is good advice for anyone doing real work with random numbers,
but I don't think it's something the OP should be worrying about. He
has a homework assignment to write a fairly elementary program that
uses random sampling to estimate the value of pi. For his purposes,
it's reasonable to assume that rand(), when used properly, yields
sufficiently random numbers. I suspect that any problems with
whatever random number generator he's using aren't going to show up in
the number of iterations he's going to be able to use (the method
converges very slowly).

The OP's major problem is how to write the program, not how to use a
random number generator, much less how to implement a high-quality
one.

 

[Keith Thompson]

I have a problem that I really don't understand at all. In my previous
post I could get started on my projects I just had a few problems with
syntax errors. This problem is something that I don't conceptually
understand very well. Here it is: [snip]
Your program should use a function that, each time it is called,
generates a new random coordinate pair, determines if this pair
represents a point inside the quarter circle, and returns a 1 if it is,
and a 0 if it is not. Your program should run a simulation for a
user-specified number of dart throws, and then display the estimated
value of Ð and the percentage difference (percent error) between your
estimated value and the true value of Ð; if your estimated value is p,
then the percent error is (( p - Ð) / Ð ) * 100. (The actual value of
Ð to 15 significant figures is 3.14159265358979.)

Break the problem down into smaller parts. You're going to need
floating-point random numbers in the range 0.0 to 1.0. Write a
program that generates and displays one such number. Then add a loop
so it generates and displays a sequence of such numbers (say, 10 of
them). Then add the other requirements. At each stage, add printf
statements to display the values you're generating; visually examine
the output to be sure it makes sense (e.g., the number look more or
less random, they're in the proper range, etc.). As you get each part
of the program working, you can delete or comment out the printf
statements so the output isn't too cluttered.

Section 13 of the comp.lang.C FAQ, <http://www.c-faq.com/>, has some
good information on generating random numbers. Don't worry too much
about the quality of your system's random number generator; rand()
almost certainly isn't good enough for cryptography, but it's fine for
your purposes.

 

[RadiationX]

Thanks for all the help from everyone. I'm working on the solution now

 

[RadiationX]

I have not written any code yet, I'm still trying to get my head around
this problem.
Here are my ideas so far:

My only input from the user will be how many darts they choose to
throw. This will be an int.

Once I get this value I need to generate coordinate pairs from their
value of darts. Say they choose 500 darts.

What I need then is two variables to hold the coordinate pairs. Say x
and y. So, x will get 500 and y will get 500.

So I will loop 500 times.

Now I need to count the number of 'hits' in the range of sqrt(x^2 +
y^2)<= 1.00

I can use a simple IF statement for this counter.

I think this is the right track

 

[RadiationX]

Ok, I have a question. How do I generate a specific number of random
numbers?

For instance if I needed 500 random numbers how do I 'put' these 500
numbers into the Random Number Generator?

 

[mensanator]

Ok, I have a question. How do I generate a specific number of random
numbers?

For instance if I needed 500 random numbers how do I 'put' these 500
numbers into the Random Number Generator?

Uh, you don't put numbers INTO the generator, you take them out.

Call the rand() function 1000 times (for each of the 500 x & y
values you need) and save the returned values. Each time
you call it, you'll get back a new random number.

 

[RadiationX]

could you give me an example of some sample code ?

 

[Keith Thompson]

Ok, I have a question. How do I generate a specific number of random
numbers?

For instance if I needed 500 random numbers how do I 'put' these 500
numbers into the Random Number Generator?

Please read <http://cfaj.freeshell.org/google/>. (This doesn't answer
your question, but it will greatly help you get answers to any future
questions.)

 

[mensanator]

could you give me an example of some sample code ?

/*
randtest.c
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
float r[500][2];
int i;

srand((unsigned int)time((time_t *)NULL));

for (i=0; i<500; ++i) {
r[0] = rand() / (RAND_MAX + 1.);
r[1] = rand() / (RAND_MAX + 1.);
}
printf("\n\n");
for (i=0; i<500; ++i) {
printf("%f %f\n", r[0],r[1]);
}
return 0;
}

 

[Keith Thompson]

could you give me an example of some sample code ?

/*
randtest.c
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
float r[500][2];
int i;

srand((unsigned int)time((time_t *)NULL));

[snip]

Both casts are unnecessary. As long as the prototypes for srand() and
time() are visible (which they are since you have the proper #include
directives), the conversions will be done implicitly. Just use:

srand(time(NULL));

(You do sometimes need an explicit cast when you're calling a function
with a variable number of parameters, such as printf.)

 

[Richard Bos]

Or Lava Lamps.

Or tea. Or even ATS; it is the only known purpose for which that
substance is useful.

Richard

 

[Pedro Graca]

I have not written any code yet, I'm still trying to get my head around
this problem.
Here are my ideas so far:

My only input from the user will be how many darts they choose to
throw. This will be an int.

Make this a function.

Once I get this value I need to generate coordinate pairs from their
value of darts. Say they choose 500 darts.

What I need then is two variables to hold the coordinate pairs. Say x
and y. So, x will get 500 and y will get 500.

Hmmm? You already have the 500 from the previous function. No need to
save it again (twice) in x or y.

So I will loop 500 times.

Now I need to count the number of 'hits' in the range of sqrt(x^2 +
y^2)<= 1.00

I can use a simple IF statement for this counter.

I think this is the right track

Define the functions used in main() below and, hopefully, you'll have a
working program.
Don't forget to #include other necessary headers; maybe test if the user
requested 0 (zero) throws.

#include <stdio.h>

int main(void) {
int i, inside = 0;
int throws = get_user_number();

for (i = 0; i < throws; ++i) {
double x = get_random_double(0, 1);
double y = get_random_double(0, 1);
if (distance_to_origin(x, y) <= 1) {
++inside;
}
}
printf("Out of %d throws, %d were inside the quarter circle.\n",
throws, inside);
return 0;
}

 

[mensanator]

could you give me an example of some sample code ?

/*
randtest.c
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
float r[500][2];
int i;

srand((unsigned int)time((time_t *)NULL));

[snip]

Both casts are unnecessary. As long as the prototypes for srand() and
time() are visible (which they are since you have the proper #include
directives), the conversions will be done implicitly. Just use:

srand(time(NULL));

(You do sometimes need an explicit cast when you're calling a function
with a variable number of parameters, such as printf.)

Ok, thanks for pointing that out.

BTW, I copied it from the FAQ (some of us _do_ actually look
at the FAQ first).