Velocity Reviews > Parallel program to calculate PI

# Parallel program to calculate PI

Prime Mover
Guest
Posts: n/a

 05-13-2008
Hello all,

I have got the pseudo-code below that I would like to convert to c
language. The algorithm calculates Pi value. I am somewhat familiar
with C language, but I am just starting to learn parallel programming.
In this specific example, the idea seems to be simple: one must
subdivide the main loop into pieces that can be executed by

Then, each "worker task" executes a part of the loop a certain number
plays the role of "master task", which will collect and sum the

% descriptive algorithm:
1. Inscribe a circle inside a square
2. Generate random points inside the square
3. Determine the number of points that fell inside the circle
4. Let r be the number of points inside the circle divided by the
total number of points
5. Pi is approximately equal to 4*r
6. The more points are generated, the more is the precision in P value

% pseudo-code (parallel):
1. npoints = 10000
2. circle_count = 0
3. p = number of tasks
4. num = npoints/p
5. find out if I am MASTER or WORKER
6. do j = 1,num
7. generate 2 random numbers between 0 and 1
8. xcoordinate = random1
9. ycoordinate = random2
10. if (xcoordinate, ycoordinate) inside circle then
circle_count = circle_count + 1
11. end do
12. if I am MASTER
13. receive from WORKERS their circle_counts
14. compute PI (use MASTER and WORKER calculations)
15. else if I am WORKER
16. send to MASTER circle_count
17. endif

Any help would be much appreciated.

I thank you all in advance.

Prime Mover
Guest
Posts: n/a

 05-13-2008
Let me just be a bit more specific:

My (understading) problem starts in the line 5 of the pseudo-code:
5. find out if I am MASTER or WORKER

How would I specificy a "worker"? Would that be another computer?
If yes, how can I access this remote computer in the calculations, in
C language?
If yes, it means that I have to have a LAN or something to perform
tests?

I have found that there are some libraries such as OMP or MPI that
could be
used, but I'd like to know if there is a more "raw" way of doing this
first.

Again, thank you all.

Spiros Bousbouras
Guest
Posts: n/a

 05-13-2008
On 13 May, 15:20, Prime Mover <(E-Mail Removed)> wrote:
> Hello all,
>
> I have got the pseudo-code below that I would like to convert to c
> language. The algorithm calculates Pi value. I am somewhat familiar
> with C language, but I am just starting to learn parallel programming.
> In this specific example, the idea seems to be simple: one must
> subdivide the main loop into pieces that can be executed by
>
> Then, each "worker task" executes a part of the loop a certain number
> of times, independently of the other worker tasks. One specific task
> plays the role of "master task", which will collect and sum the
> results of the worker tasks:
>
> % descriptive algorithm:
> 1. Inscribe a circle inside a square
> 2. Generate random points inside the square
> 3. Determine the number of points that fell inside the circle
> 4. Let r be the number of points inside the circle divided by the
> total number of points
> 5. Pi is approximately equal to 4*r
> 6. The more points are generated, the more is the precision in P value
>
> % pseudo-code (parallel):
> 1. npoints = 10000
> 2. circle_count = 0
> 3. p = number of tasks
> 4. num = npoints/p
> 5. find out if I am MASTER or WORKER
> 6. do j = 1,num
> 7. generate 2 random numbers between 0 and 1
> 8. xcoordinate = random1
> 9. ycoordinate = random2
> 10. if (xcoordinate, ycoordinate) inside circle then
> circle_count = circle_count + 1
> 11. end do
> 12. if I am MASTER
> 13. receive from WORKERS their circle_counts
> 14. compute PI (use MASTER and WORKER calculations)
> 15. else if I am WORKER
> 16. send to MASTER circle_count
> 17. endif

On 13 May, 15:28, Prime Mover <(E-Mail Removed)> wrote:
> Let me just be a bit more specific:
>
> My (understading) problem starts in the line 5 of the pseudo-code:
> 5. find out if I am MASTER or WORKER
>
> How would I specificy a "worker"? Would that be another computer?
> If yes, how can I access this remote computer in the calculations, in
> C language?
> If yes, it means that I have to have a LAN or something to perform
> tests?
>
> I have found that there are some libraries such as OMP or MPI that
> could be
> used, but I'd like to know if there is a more "raw" way of doing this
> first.

Standard C has no built-in support for parallel processing so an
to the question "find out if I am MASTER or WORKER" falls outside
standard C which is what's topical here. I have no idea what kind of
hardware set-up and extensions to C can be used to tackle numerically
intensive parallel algorithms. Perhaps others here have the relevant
experience. Searching Google groups for *parallel* I found
comp.parallel.mpi and comp.parallel.pvm where I'm guessing you might
get more useful advice than here.

Out of curiosity for what value of npoints are you aiming for ? In
your example it's only 100000 and you can get that on a modern desktop
in a few seconds.

Spiros Bousbouras
Guest
Posts: n/a

 05-13-2008
> On 13 May, 15:28, Prime Mover <(E-Mail Removed)> wrote:
>
> > Let me just be a bit more specific:

>
> > My (understading) problem starts in the line 5 of the pseudo-code:
> > 5. find out if I am MASTER or WORKER

>
> > How would I specificy a "worker"? Would that be another computer?
> > If yes, how can I access this remote computer in the calculations, in
> > C language?
> > If yes, it means that I have to have a LAN or something to perform
> > tests?

>
> > I have found that there are some libraries such as OMP or MPI that
> > could be
> > used, but I'd like to know if there is a more "raw" way of doing this
> > first.

>
> Standard C has no built-in support for parallel processing so an
> to the question "find out if I am MASTER or WORKER" falls outside
> standard C which is what's topical here. I have no idea what kind of
> hardware set-up and extensions to C can be used to tackle numerically
> intensive parallel algorithms. Perhaps others here have the relevant
> experience. Searching Google groups for *parallel* I found
> comp.parallel.mpi and comp.parallel.pvm where I'm guessing you might
> get more useful advice than here.

There's also comp.parallel

Bart
Guest
Posts: n/a

 05-13-2008
On May 13, 3:55*pm, Spiros Bousbouras <(E-Mail Removed)> wrote:
> On 13 May, 15:20, Prime Mover <(E-Mail Removed)> wrote:

> > I have got the pseudo-code below that I would like to convert to c
> > language. The algorithm calculates Pi value. I am somewhat familiar

> Out of curiosity for what value of npoints are you aiming for ? In
> your example it's only 100000 and you can get that on a modern desktop
> in a few seconds.- Hide quoted text -

I got 3.1415 using a billion points. Looks like it will converge very
slowly.

Also the granularity of the x,y points may affect the maximum accuracy
(because it introduces errors near the circular edge). Tried a sphere
too but not any better.

--
Bartc

Spiros Bousbouras
Guest
Posts: n/a

 05-13-2008
On 13 May, 16:02, Pietro Cerutti <gahr@localhost> wrote:
> Prime Mover wrote:
> > % descriptive algorithm:
> > 1. Inscribe a circle inside a square
> > 2. Generate random points inside the square
> > 3. Determine the number of points that fell inside the circle

>
> How can you determine it without knowing PI a priori?

Imagine a circle with radius is 1 and its center has coordinates
(0 , 0).
A random point with coordinates (x,y) will be inside the square
if -1 <= x <= 1 and -1 <= y <= 1
if ( x*x + y*y < 1) /* inside the circle */

Spiros Bousbouras
Guest
Posts: n/a

 05-13-2008
On 13 May, 16:15, Bart <(E-Mail Removed)> wrote:
> On May 13, 3:55 pm, Spiros Bousbouras <(E-Mail Removed)> wrote:
>
> > On 13 May, 15:20, Prime Mover <(E-Mail Removed)> wrote:
> > > I have got the pseudo-code below that I would like to convert to c
> > > language. The algorithm calculates Pi value. I am somewhat familiar

> > Out of curiosity for what value of npoints are you aiming for ? In
> > your example it's only 100000 and you can get that on a modern desktop
> > in a few seconds.- Hide quoted text -

>
> I got 3.1415 using a billion points. Looks like it will converge very
> slowly.
>
> Also the granularity of the x,y points may affect the maximum accuracy
> (because it introduces errors near the circular edge). Tried a sphere
> too but not any better.

And of course you must know that your random numbers
will be uniformly distributed within the square.

Spiros Bousbouras
Guest
Posts: n/a

 05-13-2008
On 13 May, 17:00, Richard Heathfield <(E-Mail Removed)> wrote:
> Spiros Bousbouras said:
>
> <snip>
>
> > And of course you must know that your random numbers
> > will be uniformly distributed within the square.

>
> That's easy. Use the following random point generator:
>
> #include <assert.h>
>
> void rndpt(unsigned long int *x,
> unsigned long int *y,
> unsigned long int max) /* max = side of square */
> {
> static unsigned long int n = 0;
> assert(x != NULL && y != NULL);
> *x = n % max;
> *y = n++ / max;
> n %= max;
> return;
>
> }
>
> If you call this i * max times, where max is a constant and i is an
> integer, the distribution of the random points will be uniform.

Since *y will always get the value 0 I don't think
so.

dj3vande@csclub.uwaterloo.ca.invalid
Guest
Posts: n/a

 05-13-2008
In article <(E-Mail Removed)>,
Richard Heathfield <(E-Mail Removed)> wrote:
>Spiros Bousbouras said:
>
>> On 13 May, 17:00, Richard Heathfield <(E-Mail Removed)> wrote:
>>> Spiros Bousbouras said:
>>>
>>> <snip>
>>>
>>> > And of course you must know that your random numbers
>>> > will be uniformly distributed within the square.
>>>
>>> That's easy. Use the following random point generator:
>>>
>>> #include <assert.h>
>>>
>>> void rndpt(unsigned long int *x,
>>> unsigned long int *y,
>>> unsigned long int max) /* max = side of square */
>>> {
>>> static unsigned long int n = 0;
>>> assert(x != NULL && y != NULL);
>>> *x = n % max;
>>> *y = n++ / max;
>>> n %= max;
>>> return;
>>>
>>> }
>>>
>>> If you call this i * max times, where max is a constant and i is an
>>> integer, the distribution of the random points will be uniform.

>>
>> Since *y will always get the value 0 I don't think
>> so.

>
>Since it won't, I do.

It looks to me like it will, so I don't.

When n is max-1, the line that assigns *y sets *y to 0, and then bumps
n to max. The next line folds max back to 0, so on the next invocation
you'll go back to 0 for *x and *y will still be 0.
I think you meant to write "n %= (max*max)" for the line just before
the return.

dave

--
Dave Vandervies dj3vande at eskimo dot com
> I'd like to believe that somewhere there must be a BMW not driven by a
> fsckwit. --Garrett Wollman and Richard P. Grant in

Give me a BMW and I'll fulfill that wish. the scary devil monastery

Bart
Guest
Posts: n/a

 05-13-2008
On May 13, 5:00*pm, Richard Heathfield <(E-Mail Removed)> wrote:
> Spiros Bousbouras said:
>
> <snip>
>
> > And of course you must know that your random numbers
> > will be uniformly distributed within the square.

>
> That's easy. Use the following random point generator:
>
> #include <assert.h>
>
> void rndpt(unsigned long int *x,
> * * * * * *unsigned long int *y,
> * * * * * *unsigned long int max) /* max = side of square */
> {
> * static unsigned long int n = 0;
> * assert(x != NULL && y != NULL);
> * *x = n % max;
> * *y = n++ / max;
> * n %= max;
> * return;
>
> }
>
> If you call this i * max times, where max is a constant and i is an
> integer, the distribution of the random points will be uniform.

You mean max*max?

This looks to be simply filling in a square sequentially. You are then
effectively calculating the area of a circle in a square by counting
the all dots. That's not really in the spirit of the original method.
(I think it also converges more slowly compared with the same number
of points picked randomly.)

--
Bartc