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 half a million decimal digits of PI)

Edited by Michael Roby Wetherfield & Hwang Chien-lih (last updated 21st September 2013)
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 the beautiful "reduction" process devised by Professor John Todd (1911-2007). In his 1949 paper "A problem on arc tangent relations", 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. The discovery of 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 extended, 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]}). However, we have no plans to extend the database to include reductions of inverse fractional cotangents involving denominators greater than 2.

The 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. Techniques for populating files in this database are described in the software page - in general (as is to be expected), the higher the associated prime, the larger the file.

The database file corresponding to the irreducible [49] may be taken as an example. Since (49² + 1) = 2.1201, 1201 is the associated prime. This file contains (only) 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 (of which there are currently over 18,000) is certain to include a multiple of [49]. Reductions held in database files corresponding to irreducibles whose associated prime is less than 1201 cannot include multiples of [49].

Top of page

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).

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 - this never seems to lead to confusion.

Our current "best" identity has measure 1.26579.

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.

Top of page

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 (selected) and corrections

Note: References to "N-digit" identities below imply that, in any such identity, the smallest cotangent value (or its numerator, in the case of a half-integer cotangent) has N decimal digits.

(21 Sep 13)
(14 Sep 13)
(5 Aug 13. We are deeply indebted to Akira Wada (who has tested all 755 identities in our website) for pointing out the need for the following corrections - the changes of 18 Jul 13, below, were also at his behest. In some cases the fault lies in the actual representation of a few half-integer cotangent values, but usually it is coefficient values and/or signs which are incorrect)
(18 Jul 13)
(24 Jun 13)
(31 Aug 12)
(23 Jul 12)
(9 Jul 12)
(15 Mar 12)
Top of page
(10 Mar 12)
(21 Aug 11)
(19 Aug 11)
(18 Aug 11)
Top of page
(23 Jul 11)
(9 Jun 11)
(1 Aug 10)
(18 March 10)
Top of page
(28 Feb 10)
(28 Sep 09)
(24 Sep 09)
(1 Aug 09)
(31 Jul 09)
Top of page
(7 Jun 09)
(25 May 09)
(27 Feb 09)
(11 Jan 09)
(12 Mar 08)