Problems for APL Buffs (I)
Vector 6:3, page 109
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 109
Author’s Note¶
Last night, it occurred to me that some of the problems I coped with during my professional career might be of interest to the APL community. This morning I put together a few notes on one of these subjects, and am sending them to you under the title "Problems for APL Buffs"
The concept of a random number is closely associated with a population frequency distribution. When a random sample is taken, a histogram of this sample should look like the frequency function of the population from which the sample was taken. The larger the sample, the closer should the histogram approach in shape that frequency curve.
In APL, a source of random numbers is available with the roll:
In the above example (I am using 1 as the index origin) the digits 1 2 and 3 should appear with roughly equal frequency. Therefore the underlying frequency distribution is a discrete function, and is defined as one third at the points 1 2 and 3. With the roll, and with some simple transformations, it is possible to generate random samples from arbitrary frequency distributions. A frequency function where each value has an equal chance of occurrence is called a uniform distribution.
Consider now a two-dimensional frequency function:
Each row is now a sample of two values. The associated frequency function is not a curve (or more accurately, points on a line for the discrete case), but a surface. There are two dimensions for the random variables, and one dimension for the probabilities. The extension to higher dimensions is straightforward.
Rotations¶
Another type of random sample is one dealing with rotations. Consider points in the x/y plane:
If we desire to rotate these points ‘randomly’, what does that mean? (From here on, whenever I use the word random I will mean ‘random in a uniform sense’.) The analogue of a uniform distribution for a rotation is one where each angle from 0 to 360 is equally likely. But given the angle, one still has to come up with a transformation that would change X,Y values to a new set of rotated ones X′,Y′. We can readily define such a function:
Suppose that we desire to rotate the rows in P in such a way that the first point (row-1 of P) moves to the place of the second point. (The angle is that for which the tangent is 3÷4 or 36.8698976…)
To rotate these points back, there are two ways of doing it:
or …
The reason is that the two-by-two array is a special one, belonging to a class of matrices called unitary. Its transpose is equal to its inverse; the matrix multiplied by its transpose produces the unit matrix with ones on the diagonal and zeros elsewhere.
Moving on the Sphere¶
The next question that one might ask is: what about three dimensions? Suppose we have points in space and we want to rotate these in a random way: how could we define random?
Things get a little more complicated here. To ‘simplify’ matters, consider a landmass on the globe (we will assume here that the Earth is a perfect sphere). If we desire to move England to, say Australia, we could do that in two steps. First we move the centre of gravity of England to the desired point. Then we rotate England around this centre of gravity as in the two dimensional case. Intuitively, a random motion on the unit sphere would be defined by picking any point on the sphere with equal likelihood, followed by a random rotation.
How would one define an APL function that randomly selects a point on a sphere? THAT might be a useful function. But is the motion that we have just defined truly random? Consider the following: it is well known that any motion on a sphere is equivalent to a simple rotation. The pole of that rotation has a special name: it is called the Euler pole. Given an Euler pole, and an angle of rotation, one can generate any motion of a two-dimensional object on the surface of a sphere.
This provides us with a second possible definition of random motion on a sphere: first select a random location on the sphere as before; then call this point an Euler pole, and select a random rotation in the plane. Are these two definitions of random motion equivalent? (I do not know the answer!)
So we have several interesting APL problems here. First consider writing an APL function that would generate a random unitary matrix for rotation in three dimensions. Next, given such a matrix, find the associated Euler pole and rotation. Another problem: given two points on the surface of a sphere (say London and Edinburgh) and a new location for the first point and a geographic direction for the second one (i.e. a desired rotation) find the appropriate unitary matrix. Finally: given an Euler pole, and a rotation, find the associated unitary matrix.
If these problems are too trivial, try this one. Define random rotation in more than three dimensions, and write an algorithm to generate the associated unitary matrix. Make sure that the matrix involves only rotations, and does not include inversions, which is a totally different subject.
If these problems are too abstract, here is one that is more practical: you have a map on the scale of 1:25000 from very high latitudes (the grid of parallels and meridians is not cartesian). You can digitize points on that map to about 4 significant digits of accuracy. Write an APL function to convert the digitized cartesian co-ordinates to latitudes and longitudes. If you use some of the functions discussed above, your function should be less than six lines of code.