Cross-clocks in J
Vector 8:3, page 124
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 124
This article was prepared using J version 3.4a running on an Archimedes 540.
Here is an interesting problem whose solution was required to be implemented in C as part of Midland Montagu’s Windowed Technical Trading Environment (WiTTE). In the absence of a good theoretical understanding of modulo arithmetic and diophantine equations, I chose to explore the problem using J.
A ‘clock’ ticks with period p, a whole number of seconds, and first ticks a seconds after some agreed original time t0, where a is called the alignment. The problem is this: given two clocks, cx=(px,ax) and cy=(py,ay), is there a cross-clock cz=(pz,az), which ticks when and only when both cx and cy tick, and if so what are pz and az?
Before we begin, let’s define two verbs and two adverbs, all very useful in tacit definitions:
Now let’s describe the data structure for a clock. It is simply a two-element vector of the period and the alignment. In J, we can describe structures by defining functions which extract the members of those structures:
In much of the work that follows, we are going to want to extract the period and alignment of a clock in a dyadic function, so let’s define some dyadic functions which extract these values.
The exploration begins: here is a function which shows the times of the first x ticks of a clock:
expand =. ay + py * i. X:
] E1 =. 10 expand C1
3 8 13 18 23 28 33 38 43 48
] E2 =. 10 expand C2
1 5 9 13 17 21 25 29 33 37
Let’s proceed empirically for now. Given the expansion of two clocks, what is the expansion of the cross-clock? It is the intersection of the expansion vectors.
From this, we can see that the cross-clock’s alignment is 13, and its period is 33 - 13 = 20. Let’s write a function which extracts these values, i.e. which does the opposite of expand:
Putting all this together, we can build an empirical solution with an adverb. Its argument is the number of ticks of each clock to be used:
Cross =. 'contract@(x.&expand X: cap x.&expand Y:)' : 1
I: =. [.]
Cross =. (&expand) (I: (X: ('cap'I:) Y:)) \ (contract@)
5 3 (10 Cross) 4 1
20 13
Now let’s look at some other examples, to see if there’s a pattern:
cross =. 100 Cross
9 0 cross 7 0
63 0
2 0 cross 2 0
2 0
4 2 cross 1 0
4 2
6 5 cross 9 2
18 11
10 expand 6 5
5 11 17 23 29 35 41 47 53 59
10 expand 9 2
2 11 20 29 38 47 56 65 74 83
10 expand 18 11
11 29 47 65 83 101 119 137 155 173
6 5 cross 9 3
index error
The following conclusions can be drawn:
if
axandayare both 0, the cross-clock alignment is also 0;the cross-clock of two identical clocks is also identical to them;
1 0 is an identity clock;
the cross-clock period is the lowest common multiple of
pxandpy;some pairs of clocks do not have a cross-clock (the index error above).
My mathematics is sadly no longer good enough to be able to provide proofs of all of the above without quite a struggle, but this is after all an informal exploration: you and I will both have to put some faith in the remnants of mathematical intuition left to me after years of C programming.
Now provided we choose a large enough expansion size, we have a solution to the problem. But it is impractical, since the size of the expansions is going to increase roughly with the size of the periods, and my application required a fast solution for arbitrarily large periods.
One part of the problem is already solved: the cross-clock period is the LCM of px and py. So let’s at least rewrite our solution to take advantage of this knowledge:
lcm =. *.
Crossalign =. 'first@(x.&expand X: cap x.&expand Y:)' : 1
Crossalign =. (&expand) (I: (X: ('cap'I:) Y:)) \ (first@)
pz =. px lcm py
az =. 100 Crossalign
cross =. pz , az
6 5 cross 9 2
18 11
We can simplify the problem by temporarily moving the time origin to one of the alignments, say ay, and then shifting it back once we’ve calculated the cross-clock:
0 2 + (6 5 - 0 2) cross (9 2 - 0 2)
18 11
translate =. (-&0 2) :. (+&0 2)
6 5 cross&.translate 9 2
18 11
So now we only have to address the problem where ay is 0. Another simplification is to change the granularity of time to be the greatest common divisor of px and py:
0 2 + 3 * ((6 5 - 0 2) % 3) cross ((9 2 - 0 2) % 3)
18 11
scale =. %&3
6 5 cross&.scale&.translate 9 2
18 11
This suggests that the cross-clock exists if and only if the difference between the alignments is divisible by the greatest common divisor of the periods. I am confident that this is true, but I am not equipped to attempt a proof.
Let’s generalise these last two improvements:
gcd =. +.
f =. px gcd py
cross =. pz , ay+f * ((px , ax-ay) % f) az ((py , 0:) % f)
6 5 cross 9 2
18 11
We can’t use &. here because there is no way in J to use tacit definition to express its right argument as a function of the derived function’s arguments. This is a more complicated formula, but now two things can be guaranteed about the arguments to az: ay is zero, and px and py are coprime (i.e. their GCD is 1).
Let’s have a look at how az changes with ax for a couple of period pairs obeying these rules:
5 0 az 3 0
0
5 1 az 3 0
6
5 2 az 3 0
12
5 ,"0 i. 5
5 0
5 1
5 2
5 3
5 4
clocksofperiod =. ,"0 i.
clocksofperiod 5
5 0
5 1
5 2
5 3
5 4
(clocksofperiod 5) az"1/ 3 0
0 6 12 3 9
try =. clocksofperiod X: az"1/ y. , 0:
5 try 3
0 6 12 3 9
15 | 6 * i.5
0 6 12 3 9
7 try 9
0 36 9 45 18 54 27
63 | 36 * i. 7
0 36 9 45 18 54 27
7 4 az 9 0
18
63 | 36 * 4
18
az seems to vary proportionally to ax, modulo pz. So we are nearly there: all we have to do is calculate the constant of proportionality, k, for a pair of periods, which is also (by definition) az where ax = 1 and ay = 0.
Once again, let’s first write down an empirical solution for k so that we can experiment:
The cross-clock for a pair of clocks ticks when and only when both those clocks tick. So at time k, all three clocks must tick. So k is determined as follows:
So k is a multiple of py, say k = py * r, which when divided by px leaves a remainder of 1:
r is therefore the reciprocal of py, modulo px, which we shall write as px mr py. This always exists provided px and py are coprime, which we have already guaranteed. x mr y is defined such that 1 = x | y * x mr y. We can write an empirical definition of mr as follows:
AsScalar =. {.@
mr =. ((1: = x. | y. * i. X:) # i. X:) AsScalar
7 mr 9
4
7 | 9 * 7 mr 9
1
testmr =. x. | y. * x. mr y.
2 3 4 5 6 (testmr"0) 5 7 9 11 13
1 1 1 1 1
So now we have a solution for k in terms of mr:
Finally, the definition of mr is still unsuitable for implementation in C. A variant of Euclid’s algorithm can be employed to implement mr recursively, as follows:
mr =. (x. | (1: - x. * y. mr y.|x.) % y.) ` 1: @. (x.=0:)
2 3 4 5 6 (testmr"0) 5 7 9 11 13
1 1 1 1 1
It is at this point that I state, with some inevitability, that the proof is left as an exercise for the reader.
Since GCD is also omitted from most C libraries, we have Euclid’s algorithm for that, too:
Or rather more efficiently:
OrderArgs =. 'x.~ ` x. @. y.' : 2
OrderArgs =. (~ `) @. ].
gcd0 =. (y. gcd0 y. | x.) ` x. @. (y. = 0:)
gcd =. gcd0 OrderArgs > "0
And we can write LCM in terms of GCD:
Checking against the J primitives:
Finally, let’s build up our general solution, putting back the scaling and translation:
pz =. px lcm py
f =. px gcd py
k =. (py % f) * (px % f) mr (py % f)
az =. ay + f * pz | k * (ax - ay) % f
az =. pz | ay + k * ax - ay
cross =. (pz , az) "1
10 expand 10 3
3 13 23 33 43 53 63 73 83 93
10 expand 25 18
18 43 68 93 118 143 168 193 218 243
10 3 cross 25 18
50 43
10 expand 50 43
43 93 143 193 243 293 343 393 443 493
Here are two more exercises for the reader: how is it that this still works when ax < ay, and why does cross return a result even when f doesn’t divide ax - ay (and what does the result mean)?