Author: Udo Wermuth Program: 1-3-2–21.mms (V1F1, p. 47)

Farey series

    t         IS        $255
              LOC       Data_Segment
    _x        GREG      @
              LOC       Data_Segment+4*10000
    _y        GREG      @
              LOC       #100

> Computation of Farey series

             > Calling sequence: SET $1,n; PUSHJ $0,:Farey

> Entry conditions: n in $1 is the order of the series, 1 < n < 182

> _x and _y are arrays, each for at least 10000 tetras

> Exit conditions: $0 is number of x/y pairs, i.e., entries generated in _x and _y

              PREFIX    :FAREY:

01 n IS $1 Parameter: order of the Farey series

02 kk        IS        $2                         kk ← 4 ∗ k
03 yk        IS        $3  y_{k}
04 yk1       IS        $4  y_{k+1}
05 xk        IS        $5  x_{k}
06 xk1       IS        $6  x_{k+1}
07 flr       IS        $7
08 yk2       IS        $8  y_{k+2}
09 xk2       IS        $9  x_{k+2}

10 :Farey SET n,$0 1 Get the parameter.

11  SET       xk,0  1 Init for k = 0.

12  STTU      xk,:_x,4*0  1
13  SET       yk,1  1
14  STTU      yk,:_y,4*0  1

15  SET       xk1,1  1 Init for k = 1.

16  STTU      xk1,:_x,4*1  1
17  SET       yk1,n  1
18  STTU      yk1,:_y,4*1  1
19  SET       kk,4  1 k ← 1.

20 nextval ADDU flr,yk,n A Calculate the next values xk2 and yk2.

21  DIVU      flr,flr,yk1  A flr ← ⌊(yk + n)/yk1⌋.
22  MULU      xk2,flr,xk1  A
23  SUBU      xk2,xk2,xk  A xk2 ← flr ∗ xk1 − xk.
24  MULU      yk2,flr,yk1  A
25  SUBU      yk2,yk2,yk  A yk2 ← flr ∗ yk1 − yk.

26  INCL      kk,4  A k ← k + 1.

27  STTU      xk2,:_x,kk  A
28  STTU      yk2,:_y,kk  A

29  SET       xk,xk1  A Shuffle the registers.

30  SET       xk1,xk2  A
31  SET       yk,yk1  A
32  SET       yk1,yk2  A

33  CMPU      flr,xk2,yk2  A The computation stops when
34  PBNZ      flr,nextval  A  1 = 1/1 is computed.

35  INCL      kk,4  1

36  SR        kk,kk,2  1 Remove factor for tetra.
37  SET       $0,kk  1 The number of elements
38  POP       1,0  1  is returned.

Analysis The subroutine :Farey costs (2A + 4)μ + (92A + 18)υ.

Let the length of a Farey series of order n be f_{n}. Then the following relation holds: A = f_{n} − 2. The value of f_{1} is 2 as there are just the two entries 0/1 and 1/1. The Farey series of order 2 has one more element as the only quotient to be added is 1/2. So f_{2} = 3. In general the step from f_{n−1} to f_{n} adds all quotients of the form x/n in which the x is relatively prim to n. So f_{n} = f_{n−1} + φ(n). Therefore A = 2 + φ(2) + φ(3) + ⋯ + φ(n) − 2.

For test runs with n = 7, 13, and 39 the answers are f_{7} = 19, f_{13} = 59, and f_{39} = 475. So in the subroutine the value of A has to be 17 + 57 + 473 = 547.

    The first call to Farey starts with 7 instructions, 1 mem, 11 oops; 0 good guesses, 0 bad and
ends with 276 instructions, 39 mems, 1593 oops; 16 good guesses, 1 bad. Therefore the subrou-

tine needs 38μ and 1582υ. The second and third calls have 118μ + 5262υ and 950μ + 43534υ. The measured data agree with the above stated cost function.