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.1415926535897 9.)

_______________ _______________ _______________ _______________ _______________

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?

[Eric Sosman]

Re: Random Number Generators....

RadiationX wrote:[color=blue]
> [...]
>
> 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?[/color]

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.

--
Eric Sosman
esosman@acm-dot-org.invalid

[Ulrich Eckhardt]

Re: Random Number Generators....

RadiationX wrote:[color=blue]
> 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?[/color]

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

Uli

[Walter Roberson]

Re: Random Number Generators....

In article <1140958727.705 581.52580@u72g2 000cwu.googlegr oups.com>,
RadiationX <heavyreader@gm ail.com> wrote:[color=blue]
> 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.[/color]

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

--
All is vanity. -- Ecclesiastes

[Charles Krug]

Re: Random Number Generators....

On 2006-02-26, RadiationX <heavyreader@gm ail.com> wrote:[color=blue]
>
> _______________ _______________ _______________ _______________ _______________
>
> 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?
>[/color]

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]

Re: Random Number Generators....

In article <-rSdnX_7W984d5zZ RVn-vg@comcast.com> ,
Charles Krug <cdkrug@aol.com > wrote:[color=blue]
>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.[/color]
[color=blue]
>When it DOES matter, it becomes a hardware problem involving things like
>mason or gamma ray detectors.[/color]

Or Lava Lamps.

--
All is vanity. -- Ecclesiastes

[Guillaume]

Re: Random Number Generators....

Charles Krug wrote:[color=blue]
> Know that there is no software method that can produce "random numbers",
> only a subset of an arbitrary, albeit ABSOLUTELY predictable sequence of
> numbers.[/color]

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]

Re: Random Number Generators....

roberson@ibd.nr c-cnrc.gc.ca (Walter Roberson) writes:[color=blue]
> In article <1140958727.705 581.52580@u72g2 000cwu.googlegr oups.com>,
> RadiationX <heavyreader@gm ail.com> wrote:[color=green]
>> 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.[/color]
>
> 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.j...at/MT/emt.html[/color]

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 (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

Re: Random Number Generators....

"RadiationX " <heavyreader@gm ail.com> writes:[color=blue]
> 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:[/color]
[snip][color=blue]
> 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.1415926535897 9.)[/color]

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.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[RadiationX]

Re: Random Number Generators....

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

[RadiationX]

Re: Random Number Generators....

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]

Re: Random Number Generators....

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@aol.com]

Re: Random Number Generators....


RadiationX wrote:[color=blue]
> 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?[/color]

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]

Re: Random Number Generators....

could you give me an example of some sample code ?

[Keith Thompson]

Re: Random Number Generators....

"RadiationX " <heavyreader@gm ail.com> writes:[color=blue]
> 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?[/color]

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

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.