---
# System prepended metadata

title: Untitled

---

## 4.6

Write a parallel variant of Kernighan and Ritchie's classic "hello, world"  program [61]. Each process should print a message of the form 
```
hello, world, from process <i> 
```
where \<i\>  is its rank. 

## 4.7
Write a parallel program that computes the sum 1 + 2 + ... + p in the 
following manner: Each process i assigns the value i + 1 to an integer, 
and then the processes perform a sum reduction of these values. Process 0 
should print the result of the reduction. As a way of double-checking the 
result, process 0 should also compute and print the value p(p + l)/2 . 

## 4.8

A prime number is a positive integer evenly divisible by exactly two  positive integers: itself and 1. The first five prime numbers are 2, 3, 5, 7,  and 11. Sometimes two consecutive odd numbers are both prime. For  example, the odd integers following 3, 5, and 11 are all prime numbers.  However, the odd integer following 7 is not a prime number. Write a  parallel program to determine, for all integers less than 1,000,000, the  number of times that two consecutive odd integers are both prime. 

### 4.9

The gap between consecutive prime numbers 2 and 3 is only 1, while the  gap between consecutive primes 7 and 11 is 4. Write a parallel program  to determine, for all integers less than 1,000,000, the largest gap between  a pair of consecutive prime numbers. 

## 4.12

Simpson's Rule is a better numerical integration algorithm than the  rectangle rule because it converges more quickly. Suppose we want to  compute $\int_a^bf(x)dx$. We divide the interval $[a. b]$ into $n$ subintervals,  where $n$ is even. Let $x$, denote the end of the $i$-th interval, for $1 \leq i \leq n$,  and let $x_0$ denote the beginning of the first interval. According to  Simpson's Rule: 
$$
\int_a^bf(x)dx\approx\frac{1}{3n}\left[f(x_0)-f(x_n)+\sum_{i=1}^{n/2}(4f(x_{2i-1})+2f(x_{2i}))\right]
$$
A C program that uses Simpson's Rule to compute $\pi$ appears in  Figure 4.9. 

* (a)

  Write a parallel program to compute the value of TT using Simpson's  Rule: /(.r) =4/( 1 +x-),a = 0,/; = l,and/; = 50.

* (b)

  Benchmark your program on various numbers of processors. 

**Figure 4.8** A C program to compute the value of $\pi$ using the  rectangle rule. 

```c
/* This program computes p i using the rectangle rule . */
#define INTERVALS 1000000
int main (int argc, char *argv[] ) {
    double area; /* Area under curve */
    double ysum; /* Sum of rectangl e height s */
    double xi ; /* Midpoint of interva l */
    int i ;
    ysum = 0.0 ;
    for(1=0 ; i < INTERVALS; i++) {
        x i = (1.0/INTERVALS)*(i+0.5);
        ysum += 4.0/(1.0+xi*xi) ;
        )
        area = ysum * (1.0 / INTERVALS);
        print f ("Area i s %13.11f\n", area) ;
        return 0;
    }
}
```

**Figure 4.9** A C program to compute the value of $\pi$ using Simpson's Rule.. 

```c
/* This program uses Simpson's Rule t o compute pi . */
#define n 50
double f (int i ) {
    double x;
    x = (double) i / (double) n;
    retur n 4.0 / (1.0 + x * x) ;
}
int main (int argc, char *argv[] ) {
    double area;
    int i ;
    area = f(0 ) - f(n) ;
    f o r ( i = 1; i <= n/2; i++)
    area += 4.0*f(2*i-l ) + 2*f(2*i) ;
    area /= (3.0 * n) ;
    print f ("Approximation of pi : %13.11f\n", area) ;
    return 0;
}
```

## 5.11

The simplest harmonic progression is
$$
\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \cdots
$$
Let $S_n=\sum_{i=1}^n 1/i$

* (a) Write a parallel program that computes these sums to arbitrary  precision after the decimal point. For example, $S_7$= 2.592857142857,  to 12 digits of precision after the decimal point. Process 0 should  query the user for the two parameters, n and d, and broadcast these  parameters to the other processes. Processes should work together to  compute $S_n$ to d digits of precision after the decimal point. After $S_n$,  has been computed, process 0 should print its value. 
* (b) Benchmark the program computing $S_{1,000,000}$  to $100$ digits of  precision, using various numbers of processors.

## 6.8

Assume that the time needed to send an n-byte message is $\lambda+n/\beta$.  Write a program implementing the "ping pong" test to determine $\lambda$  (latency) and $\beta$ (bandwidth) on your parallel computer. Design the  program to run on exactly two processes. Process 0 records the time and  then sends a message to process 1. After process 1 receives the message,  it immediately sends it back to process 0. Process 0 receives the message  and records the time. The elapsed time divided by 2 is the average  message-passing time. Try sending messages multiple times, and  experiment with messages of different lengths, to generate enough data  points that you can estimate $\lambda$ and $\beta$.

## 6.13

In 1970, Princeton mathematician John Conway invented the game of Life. Life is an example of a cellular automaton. It consists of a rectangular grid of cells. Each cell is in one of two states: alive or dead. The game consists of a number of iterations. During each iteration a dead cell with exactly three neighbors becomes a live cell. A live cell with two or three neighbors stays alive. A live cell with less than two
neighbors or more than three neighbors becomes a dead cell. All cells are updated simultaneously. Figure 6.12 illustrates three iterations of Life for a small grid of cells.



![](https://i.imgur.com/Tbcay3L.png)

**Figure 6.12 An initial state and three iterations of Conway's game of Life.**

Write a parallel program that reads from a hie an $m \times n$ matrix containing the initial state of the game. It should play the game of Life for $j$ iterations, printing the state of the game once every $k$ iterations, where $j$ and $k$ are command-line arguments.
