Problems for APL Buffs (III)

by Zdenek V Jizba

mathematics and statistics programming techniques competitions and puzzles

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 136

The newsletter of our Southern California SIGAPL organisation is a one page sheet announcing the place and time of the next meeting. Since there is usually some space left, we try to include some APL puzzle or problem for our members to solve.

For the October 1990 meeting, I found an interesting reference [1, p.97] to a method that the ancient Greeks used to find an approximation to the square root of 2. They generated a table, or ladder as they called it.

The rule given for finding each new row is as follows. For the first column, add the numbers from the previous row. For the second column, add the number from the first column to the previous number from the first column.

The ratio of the second column to the first column converges to the square root of two. This follows from the relation:

      (1 3 7 17 41*2)-2×1 2 5 12 29*2
¯1 1 ¯1 1 ¯1

which can be easily proven as shown in the APPENDIX.

An APL function was defined to generate this ladder. The function uses the recursion rule stated above to generate the N×2 array. Our SIGAPL members were asked to find another APL function that would produce the same result more efficiently. It was suggested to look for an APL function that would not be recursive.

In the debate that ensued, some including myself, thought that a non-recursive algorithm might be difficult to find. Others including Roy Sykes felt that there must be a "closed" form. As an argument he pointed out that Jim Brown (et al) in his textbook on APL2 [2, p.321] shows a simple formula for the Nth term of the Fibonacci progression. This might have been the end of the discussion, since no one had any other comment.

About ten days before the November meeting, Roy who is our president, called me to ask if I could take his place since he was not going to be able to make it. My assigned task was to find a speaker, or to come up with a subject for discussion. He thought that perhaps I could come up with new information about the Greek ladder.

Not being able to find a substitute speaker on such a short notice, I decided to tackle the ladder problem. Right away, with some algebraic manipulation (see the APPENDIX), it can be shown that each of the two columns can be evaluated separately. Indeed, the formula is the same. If we call the array LADDER, we have:

LADDER[N+1;]←LADDER[N-1;]+2×LADDER[N;]

Armed with this information, one can easily define a general APL function called PROGRESSION:

    ∇U←V PROGRESSION W;I
[1]  ⍝ Calculate ladder with factor V[1], V[2] columns
[2]  ⍝ and seed vector W
[3]   I←1
[4]   U←1,[0.5],W
[5]  L0:→(V[2]≤I←I+1)/0
[6]   U←U,[1]U[I-1;]+V[1]×U[I;]
[7]   →L0
    ∇

The express 2 5 PROGRESSION 2 3 reproduces the Greek ladder. When the arguments to this function are 1,N and 1, the result is the Fibonacci progression of N terms:

      ,1 10 PROGRESSION
1 1 1 2 3 5 8 13 21 34 55

The reference given by Roy also can be used to produce function FIB:

    ∇U←FIB N;A;B;C
[1]  ⍝ Generate N terms of the Fibonacci series
[2]   C←1-A←0.5×1+5*0.5
[3]   B←5*¯0.5
[4]   U←B×(×\N⍴A)-×\N⍴C
    ∇

Even though the values of A, B and C are irrational, function FIB generates a vector of integers:

      FIB 10
1 1 2 3 5 8 13 21 34 55

Where can we go from here? We can look at the ratio of two consecutive terms. That ratio converges, and for the Fibonacci series we have:

      ¯1↑2÷/,1 50 PROGRESSION 1
0.6180339887

This number can be written as (¯1+5*0.5)÷2. Why stop just here? We can also evaluate:

      ¯1↑÷/,2 50 PROGRESSION 2
0.4142135624

And this number can be written as ¯1+2*0.5. With this as a clue it does not take much effort to find a closed solution to the Greek ladder problem:

    ∇U←LADDER N;A;B;C
[1]  ⍝ Generate N rows of the Greek ladder
[2]   C←2-A←0.5×2+8*0.5
[3]   B←8*¯0.5
[4]   U←B×(×\N⍴A)-×\N⍴C
[5]   U←U,[1.1]1,2+/U
    ∇

We do not have to stop here. Before we can proceed, however, we should note the following: the constants A and C in LADDER are the roots of a quadratic polynomial. (This was pointed out by Harry Bertucelli at the November meeting.)

Also note that the difference between a column of (N R) PROGRESSION W and (N R) PROGRESSION N is (0,¯1↓,(N R) PROGRESSION N)∘.×(W-N).

This can be seen best with:

(2 5 PROGRESSION 2 2 2)-2 5 PROGRESSION ⍳3

We can therefore write a general ladder function:

    ∇U←N GLADDER W;A;B;C;D
[1]  ⍝ Generate N[2] rows of ladder with multiplier N[1]
[2]  ⍝ and seed W
[3]   D←4+N[1]*2
[4]   C←N[1]-A←0.5×N[1]+D*0.5
[5]   B←D*¯0.5
[6]   U←B×(×\N[2]⍴A)-×\N[2]⍴C
[7]   U←(⍉(⌽N[2],⍴W)⍴U)+(¯1↓0,U)∘.×W-N[1]
    ∇

The property of the Greek ladder that can be used to estimate the square root of 1 can be written as the following APL expression:

      ((2 10 GLADDER 3)*2)-2×(2 10 GLADDER 2)*2
¯1 1 ¯1 1 ¯1 1 ¯1 1 ¯1 1

This is not generally true for arbitrary pairs of seeds. With some experimentation we found the following expressions:

      ((1 10 GLADDER 3)*2)-5×(1 10 GLADDER 1)*2
¯4 4 ¯4 4 ¯4 4 ¯4 4 ¯4 4

      ((3 10 GLADDER 8)*2)-13×(3 10 GLADDER 2)*2
¯12 12 ¯12 12 ¯12 12 ¯12 12 ¯12 12

One can also generalise the Fibonacci progression as an array that can be generated with function GENFIB:

    ∇U←ROWS GENFIB COLS;I;S
[1]  ⍝ Generalised Fibonacci array
[2]   I←1
[3]   U←1,[0.5]S←⍳COLS
[4]  L0:→(ROWS≤I←I+1)/0
[5]   U←U,[1]U[I-1;]+S×U[I;]
[6]   →L0
    ∇

There is more but that is for you, the APL buffs to discover.

Consider the following problems:

The expression

¯1↑,((1 50 GLADDER 3)*2)÷(1 50 GLADDER 1)*2

generates the factor 5. Write and APL function that will generate the vector of integers (F N M K) such that

((F P GLADDER N)*2)-K×(F P GLADDER M)*2)

produces S×¯1*⍳P. What would be the argument(s) to such a function?

The expression ,R P GLADDER R generates a progression of real numbers when R is not an integer (R>0).

Can you define a non-recursive function that will accept real R (R>0)?

Will the resulting progression contain complex numbers?

In general, the expression

X←¯1↑(((F,50) GLADDER N)*2)÷((F,50) GLADDER M)*2

does not produce an integer, and the vector

((F P GLADDER N)*2)-X×(F P GLADDER M)*2

does not produce a vector of the form Y×¯1*P. Is X irrational?

References¶

[1] The world of Mathematics. James R Newman Editor; Simon and Schuster, New York 1956

[2] APL2 At a Glance. James A Brown, Sandra Pakin and Raymond P. Polivka; Prentice Hall, New Jersey 1988

Appendix¶

The original rule for building the Greek ladder can be expressed by the following relations:

[1] f(N) ← f(N-1) + g(N-1)
[2] g(N) ← f(N) + f(N-1)

where f(N) is the value in the Nth row first column, and g(N) is the value in the Nth row second column. Replacing g(N-1) in [1] with [2] we get:

    f(N) ← f(N-1) + {f(N-1) + f(N-2)}
[3] f(N) ← f(N-2) + 2f(N-1)

To evaluate g(N) in terms of g(N-i), we first substitute [1] in both terms of [2]

g(N) ← {f(N-1) + g(N-1)} + f(N-1)
     ← f(N-1) + g(N-1) + {f(N-2) + g(N-2)}

but since f(N-1) + f(N-2) = g(N-1), we get

[4] g(N) ← g(N-2) + 2g(N-1)

The property that makes the ladder useful in estimating square root of two also follows from [1] and [2]. Replacing f(N) in [2]

[5] g(N) ← g(N-1) + 2f(N-1)

Replacing [2] and [5] in g²(N+1) - 2f²(N+1)

{g(N) + 2f(N)}² - 2{g(N) - f(N)}²

and after simplification we get the recursion

g²(N+1) - 2f²(N+1) = -{g²(N) - 2f²(N)}

And since

g²(1) - 2f²(1) = 1 - 2×1 = -1

we can see that

g²(N) - 2f²(N) = (¯1)ⁿ