2.7.30 List Tutorial Exercise 12

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.