Next: List Tutorial Exercise 13, Previous: List Tutorial Exercise 11, Up: Answers to Exercises [Contents][Index]

This problem can be made a lot easier by taking advantage of some
symmetries. First of all, after some thought it’s clear that the
‘`y`’ axis can be ignored altogether. Just pick a random ‘`x`’
component for one end of the match, pick a random direction
‘`theta`’,
and see if ‘`x`’ and
‘`x + cos(theta)`’
(which is the ‘`x`’ coordinate of the other endpoint) cross a line.
The lines are at integer coordinates, so this happens when the two
numbers surround an integer.

Since the two endpoints are equivalent, we may as well choose the leftmost
of the two endpoints as ‘`x`’. Then ‘`theta`’ is an angle pointing
to the right, in the range -90 to 90 degrees. (We could use radians, but
it would feel like cheating to refer to ‘`pi/2`’ radians while trying
to estimate ‘`pi`’!)

In fact, since the field of lines is infinite we can choose the
coordinates 0 and 1 for the lines on either side of the leftmost
endpoint. The rightmost endpoint will be between 0 and 1 if the
match does not cross a line, or between 1 and 2 if it does. So:
Pick random ‘`x`’ and
‘`theta`’,
compute
‘`x + cos(theta)`’,
and count how many of the results are greater than one. Simple!

We can make this go a bit faster by using the `v .` and `t .`
commands.

1: [0.52, 0.71, ..., 0.72] 2: [0.52, 0.71, ..., 0.72] . 1: [78.4, 64.5, ..., -42.9] . v . t . 1. v b 100 RET V M k r 180. v b 100 RET V M k r 90 -

(The next step may be slow, depending on the speed of your computer.)

2: [0.52, 0.71, ..., 0.72] 1: [0.72, 1.14, ..., 1.45] 1: [0.20, 0.43, ..., 0.73] . . m d V M C +

```
1: [0, 1, ..., 1] 1: 0.64 1: 3.125
. . .
1 V M a > V R + 100 / 2 TAB /
```

Let’s try the third method, too. We’ll use random integers up to
one million. The `k r` command with an integer argument picks
a random integer.

2: [1000000, 1000000, ..., 1000000] 2: [78489, 527587, ..., 814975] 1: [1000000, 1000000, ..., 1000000] 1: [324014, 358783, ..., 955450] . . 1000000 v b 100 RET RET V M k r TAB V M k r

1: [1, 1, ..., 25] 1: [1, 1, ..., 0] 1: 0.56 . . . V M k g 1 V M a = V R + 100 /

```
1: 10.714 1: 3.273
. .
6 TAB / Q
```

For a proof of this property of the GCD function, see section 4.5.2,
exercise 10, of Knuth’s *Art of Computer Programming*, volume II.

If you typed `v .` and `t .` before, type them again to
return to full-sized display of vectors.