Sylvester’s Algorithm

From: Howard A. Peelle, July 1996

mathematics and statistics programming techniques

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

In [1] Norman Thomson resurrects Sylvester’s algorithm for converting a "vulgar fraction" (decimal between 0 and 1) into a list of "unit fractions" (or integer reciprocals). Here, Sylvester’s algorithm is recast again in J for perspicuity.

First, compute the largest unit fraction less than the input:

   unit =. >. &. %

For example:

   unit Fraction =. 0.67296
0.5

Use this to decompose the input into the largest unit fraction and the "error" term:

   decompose =. unit , (- unit)

For example:

   decompose Fraction
0.5 0.17296

Use this to extend any such list by decomposing the last term:

   extend =. }: , decompose@{:

For example:

   extend 0.5 0.17296
0.5 0.1666667 0.006293333

And, finally, repeat it:

   extend^:3 Fraction
0.5 0.1666667 0.006289308 4.02516e_6

The integer reciprocals are obtained easily. For example:

   % extend^:3 Fraction
2 6 159 248437

Also, note the identity:

   Fraction = +/ extend^:3 Fraction
1

Further, this applies to a vulgar mixed fraction as well:

   extend^:6 Mixed =. 3.67296
1 1 1 0.5 0.1666667 0.006289308 4.02516e_6

And to negative vulgar fractions (between _1 and 0):

   extend^:3 -Fraction
_1 0.25 0.07692308 0.0001169231

And to real, non-empty arrays:

   extend^:3"0 Fraction,-Fraction
0.5 0.1666667 0.006289308    4.02516e_6
 _1      0.25  0.07692308 0.0001169231

All this may be embodied in a program to return the leading integers (without the error term) whose unit fractions approximate the vulgar fraction input:

   sylvester =. [: }:"1 [: % extend@]^:["0

For example:

   3 sylvester (+,-) Fraction
 2 6 159
_1 4  13

Also in [1] Norman Thomson codes a similar algorithm to represent a fraction (decimal) in a given number base. Here it is expressed simply:

   f =. * 1&|

For example:

   <. 5 f^:(i.6) Fraction
0 3 1 4 0 3                     NB. +/0 3 1 4 0 3 * 5 ^ -i.6

Reference¶

[1] Thomson, N. J-ottings 9, Vector, Vol. 12, No. 4, April 1996 pp. 28-29