Updates     Reduction process       Software     PI evaluation programs     Measures     Tweaking                         LOGOUT / REFERENCES 
Identity lists (Classification, Layout, & Links)                        Self-checking pairs of identities

COMPUTING PI: LISTS OF MACHIN-TYPE (INVERSE COTANGENT) IDENTITIES FOR PI/4

(and more than a half-million decimal digits of PI)

Edited by Michael Roby Wetherfield & Hwang Chien-lih (last updated 29 July 2010)
 We were saddened to read of the death on 21st June 2007 of Professor John Todd who, in his paper "A problem on arc tangent relations" (Amer. Math. Monthly 56 (1949), pp. 517-528), described his process for the reduction of inverse cotangents, gratefully acknowledged as the basis for much of the material in this website.
N.B.: THE NOTATION "[x]" IS USED TO REPRESENT "arccot(x)" (= arctan(1/x)) THROUGHOUT THIS SITE.

The Machination software we have used to generate our own contribution to these lists depends on John Todd's beautiful "reduction" process. Todd showed how the inverse cotangents of certain integers are "irreducible", all these "irreducibles" (apart from [1]) being associated in a 1-1 correspondence with the primes congruent to 1 (modulo 4) - for example, because n=9 is the smallest integer for which 41 divides (n² + 1), [9] is irreducible and is associated with the prime 41. Accordingly, [1] is associated with the prime 2; the irreducibles associated with the primes 5, 13, 17, 29 and 37 are respectively [2], [5], [4], [12] and [6], and so on (for further details, refer to "Reduction process"). Like "prime", the word "irreducible" may be used as a noun or an adjective, according to context.

Just as any composite integer can be expressed uniquely as a product of primes, Todd's process enables any inverse integral cotangent which is not itself irreducible to be expressed as a unique linear sum of irreducibles with positive or negative integer coefficients, i.e. "reduced" (in any such "reduction" the irreducible cotangent values are all numerically less than the reduced integer cotangent value). The process can also be used to obtain reductions of inverse rational cotangents, in particular of the inverse cotangents of half-integer values. By convention, the terms in any reduction are arranged in increasing sequence of irreducible cotangent values.

If the largest prime factor of (n² + 1) is less than 2n, [n] is not irreducible, so [3], [7], [8], [13], etc., are not irreducibles; their "reductions" are:

    [3] = [1] - [2]
    [7] = -[1] + 2[2] 
    [8] = [1] - [2] - [5]
    [13] = [1] - [2] - [4]
    etc.

Measuring arccotangents in radians, [1] = PI/4; eliminating [2] from the above reductions of [3] and [7], the equation ([1]=) PI/4 = 2[3] + [7] is obtained. This identity (the term used herein to refer to such arccotangent 'formulae' for PI/4) is nowadays credited to John Machin (1680-1751). The reduction of [239] is -[1]+4[5], giving ([1]=) PI/4 = 4[5] - [239], the exact equivalent of Machin's own celebrated identity of 1706.

Top of page

Our software operates on a database, continually being expanded, of reductions of both integer and "half-integer" arccotangents, an example of the latter being: [1011/2] = [1]-3[2]+[4]+[5]+[6]. Half-integer terms of the form "[N/2]" appear explicitly in our identities - in practice, they are no harder to evaluate than inverse integral cotangents; those who prefer to deal only with the latter may mentally substitute the expression {2[N] - [N(N²+3)/2]} for "[N/2]" (in this example: {2[1011] - [516683682]}). This database comprises a number of text files - the first of these contains the reductions of all inverse cotangents [N] and [N/2] for which the largest prime factor of (N² + 1), or (for half-integers) of (N² + 4), is at most 97; each of the remaining files corresponds to a single irreducible whose associated prime exceeds 97.

For example, since (49² + 1) = 2.1201 (i.e. the prime 1201 is associated with the irreducible [49]), the file corresponding to the irreducible [49] just contains reductions of inverse cotangents [X], where X = N (integer) or X = N/2 (half-integer), and 1201 is the largest prime factor of (N² + 1) or (N² + 4) respectively; every one of these reductions is certain to include a multiple of [49], but none of the reductions in the files corresponding to irreducibles whose associated prime is less than 1201 can include multiples of [49].

The software includes programs which can search this database for all reductions involving only a wholly- or partly-specified set of irreducibles, and (treating these reductions as simultaneous linear equations, as in the example above) can then attempt to eliminate all the irreducibles except [1] from the equations in increasing sequence (i.e. [2], [4], [5], [6],...). This process, if successful, leads to an arccotangent identity with [1], or a positive multiple of [1], on the LHS. The irreducibles eliminated are referred to as the "eliminated set" (sometimes some irreducibles cannot be eliminated, but feature in the resultant identity).

We have no plans to extend the database to include reductions of inverse fractional cotangents involving denominators greater than 2.

Many of the identities in our lists are present either for their historical interest, or as a record of the progress made by the editors in their search for new identities. Every identity has a "measure" which is the sum of the reciprocals of the logarithms, to base 10, of the cotangent values (integers and half-integers) it includes - the smaller the measure, the better. We also use an identity's measure, to 5 decimal places, to act as a distinguishing identifier for it.

Our current "best" identity has measure 1.26579.

Top of page

Any serious attempt to compute PI using arccotangent identities will usually rely on a pair of mutually-checking identities, the results only being acceptable if no significant discrepancies are detected. To minimise computation time, the pair should share as many cotangent values as possible, having coefficients which (after "normalisation" relative to the coefficient of [1]) must be different in the two identities. Examples are listed on the "Self-checking pairs" page; the "Compound measure" shown on the line preceding each pair, used to index the pair's efficacy, is the sum of the reciprocals of the logarithms of all distinct cotangent values (DCVs), in effect the sum of the measures of the two identities, but with the contributions of shared cotangent values counted only once. Pairs are grouped according to the number of DCVs they contain, making it easier for users with a particular number of PCs at their disposal to choose a suitable pair to use in a computation.

To determine whether a particular collection of irreducibles can provide us with a worthwhile self-checking pair, we search the database for all reductions involving only these irreducibles, and then attempt to find within those the "best" linearly-independent set of reductions from which all of these irreducibles, as well as [1], can be eliminated - i.e. we look for a linear sum of "reducible" inverse integer and half-integer cotangents equating to 0. If any single "reducible" is then omitted from this set of values, an identity should be obtainable from the values remaining, any two such identities constituting a "self-checking" pair. All such "pairs" will have the same "best" Compound measure - by convention, we choose the two identities obtained by omitting in turn the two lowest cotangent values in the set, so that the resulting pair of identities have the least measures obtainable.

Our current "best" mutually-checking pair of identities has Compound measure 1.81462.

To access the classified lists of identities, follow a link to "Identity lists". 
To access the list of self-checking pairs of identities, follow a link to "Self-checking pairs". 
To explore some of the byways, follow links in the top line of this page.
UPDATES
(29 Jul 10)
(3 Jul 10)
(20 Jun 10)
(19 May 10)
(22 March 10)
(18 March 10)
Top of page
(4 March 10)
(28 Feb 10)
Top of page
(9 Feb 10)
(4 Feb 10)
(20 Jan 10)
(18 Jan 10)
(17 Jan 10)
Top of page
(10 Jan 10)
(15 Dec 09)
(25 Nov 09)
(21 Nov 09)
(20 Nov 09)
Top of page
(16 Nov 09)
(13 Nov 09)
(11 Nov 09)
(10 Nov 09)
(17 Oct 09)
Top of page
(13 Oct 09)
(12 Oct 09)
(11 Oct 09)
(8 Oct 09)
(2 Oct 09)
(1 Oct 09)
(28 Sep 09)
Top of page
(27 Sep 09)
(26 Sep 09)
(25 Sep 09)
(24 Sep 09)
(1 Aug 09)
Top of page
(31 Jul 09)
(23 Jun 09)
(7 Jun 09)
(25 May 09)
(27 Feb 09)
(11 Jan 09)
(12 Mar 08)
Top of page