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)
- New 3-DCV self-checking
pair with Compound measure 4.62989.
(14 Sep 13)
- In 6-digit identity
with measure 1.61816, associated Compound measure corrected to
1.85000.
(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)
- In 2-digit identity
with measure 1.74096, coefficients of both last 2 terms changed
from '-4' to '+4'.
- In 2-digit identity
with measure 1.78220, coefficient of [110443] changed from '+6'
to '+12'.
- In 8-digit identity
with measure 1.71753, missing ']' appended to 14th term.
- In 10-digit
identity with measure 1.82151, representation of [36523075989/2]
corrected.
- In 12-digit
identity with measure 1.92755, '2]' appended to 3rd term.
- In 12-digit
identity with measure 1.93336, '4' appended to coefficient of
4th term (becomes '+4765038574').
- In 13-digit
identity with measure 2.01249, representation of [43777069138111/2]
corrected.
- In 13-digit
identity with measure 2.01560, representation of [17857722814749/2]
corrected (spurious '{2' removed).
- In 'Self-checking
pairs', identity with measure 1.65426, coefficient of 6th term
should be '-67595' (minus sign was missing).
- In 'Self-checking
pairs', identity with measure 1.69382, change sign of coefficient
of last term (becomes '+13261').
- In 'Self-checking
pairs', identity with measure 1.70951, change sign of coefficient
of last term (becomes '+26522').
(18 Jul 13)
- In 2-digit identity
with measure 1.65181, sign preceding term [18677233307] changed
from '-' to '+' .
- In 9-digit identity
with measure 1.73500, coefficient of [1432278547] changed from
'+54876' to '+5487606'.
(24 Jun 13)
- 4th cotangent
value in "best" 2-digit identity corrected to [9916207]
(measure unchanged).
(31 Aug 12)
- New 6-digit
identity (1.65027) and two new 5-digit identities (1.53702 (new
"best"), 1.58108).
(23 Jul 12)
- Dates associated
with Euler's two 3-term identities revised following research
by Amrik Singh Nimbran in the "Euler Archive" <http://www.math.dartmouth.edu/~euler>.
(9 Jul 12)
- New 9-digit
identity (1.74866), member of new "best" 18 DCV self-checking
pair (Compound measure 1.88600).
- New 8-digit
identity with measure 1.73223.
(15 Mar 12)
- Further minor
revisions to text on this page (above) relating to database of
reductions.
Top of page
(10 Mar 12)
- Revisions to
text on this page (above) relating to database of reductions.
- Minor changes
to Software page - including enhancement of process to generate
new "outsize" half-integer reducibles with associated
primes up to 1201; these can also (more frequently than one might
expect) be obtained by "differencing" integer reducibles
whose associated primes exceed 1201.
(21 Aug 11)
- New 12-digit
identity with measure 1.92909.
(19 Aug 11)
- New 14-digit
identities with measures 2.08477, 2.08500, 2.09165, 2.09335,
2.09414, 2.09485, and 2.09539.
- New 31-DCV self-checking
pairs with Compound measures 2.16051 and 2.16117.
(18 Aug 11)
- The "Software"
page has been revised, and now includes an outline description
of a recently-completed program which enables new "outsize"
reducible half-integer cotangent values to be generated. This
program has been applied with some success; when all the results
have been gathered in, improvements to several reductions displayed
on the "Identity List" pages for (probably) 12-, 13-
and 14-digit identities (and in some cases the "Self-checking
pairs" page) will be incorporated.
- A reference
has been added on the LOGOUT page to Amrik Singh Nimbran's article,
entitled "On the derivation of Machin-like Arctangent Identities
for computing Pi", recently published in the Indian journal
"The Mathematics Student".
Top of page
(23 Jul 11)
- Five new 6-digit
identies discovered by Amrik Singh Nimbran (29May11) with measures
1.61816, 1.65318, 1.65587, 1.65629, and 1.66027 (a sixth, with
measure 1.66333, also incorporated in a new 13-DCV self-checking
pair, below).
- Three concurrently-discovered
new 13-DCV self-checking pairs, incorporating some of the above,
with Compound measures 1.85000, 1.85894 and 1.86616.
- Four new 12-digit
identities discovered with measures 1.90181 (ASN, 16Jun11), 1.93217
(ASN,21Jun), 1.90536 and 1.91506.
- Two new 5-digit
identities (25Jun11) with measures 1.62115 and 1.63062.
- Two new 14-digit
identities with measures 2.09537 (17Jun11) and 2.09750 (25Jun11).
- New 31-DCV self-checking
pair with Compound measure 2.17215.
(9 Jun 11)
- "Software"
page updated to record the fact that all files in our database
of reductions for irreducibles up to [49] (i.e. associated with
primes up to 1201) have been completed for LHS integer cotangent
values up to [9999 99999 99999] and half-integer values up to
[19999 99999 99999/2].
(1 Aug 10)
- 3-digit identity
list tidied considerably. It will be observed that, in certain
cases, multiple identities derived by "tweaking" from
a single original have been listed, for the sake of interest
; now, for each "original", only the measure of the
best such "derivative" is included in the "top
20 measures" list for the category.
(18 March 10)
- Website title,
and wording of above introduction, revised to remove emphasis
on inverse integral cotangent terms in identities.
Top of page
(28 Feb 10)
- Revised wording
on "Identity Lists" page to clarify categorisation
of identities with more than four terms.
(28 Sep 09)
- New "natural"
half-integer convention applied to all identity lists.
(24 Sep 09)
- The "Tweaking"
page has been more drastically edited, to reflect changes to
the associated software, and also to announce some resulting
successes.
- Many of the
resulting changes involve a half-integer term [3375905320682366575989
/ 2]. Since the cube of the numerator of this fraction takes
up an inordinate amount of space, it has been decided to abandon
the rather artificial practice of representing half-integer terms
as pairs of integers (this change is on-going).
(1 Aug 09)
- Layout of identities
(on "Identity lists" page) updated to introduce notion
of "back-formed" identities, identified by discovery
date shown as "(***)". 2-digit, 3-digit and 4-digit
identity pages updated to conform.
(31 Jul 09)
- A note has been
inserted on the "Identity Lists" page to clarify the
significance of asterisked references to other identities.
Top of page
(7 Jun 09)
- A selection
of Amrik Singh Nimbran's identities, discovered during 2007-8
and recently sent to us, appear in the 3- and 4-digit lists.
We are grateful for these - more of them are likely to be included
after checking; they have stimulated us to generate new identities
ourselves.
(25 May 09)
- "Computing
PI" added to title.
(27 Feb 09)
- Page added describing
programs used to perform evaluation of PI featured on this website.
(11 Jan 09)
- Preparation
for revival of website (lapsed since end July 2008) with URL
changed to <http://www.machination.eclipse.co.uk>.
(12 Mar 08)
- Our attention
has recently been drawn to Ian Tweddle's 1991 paper "John
Machin and Robert Simson on Inverse-tangent series for PI"
(v. detailed reference on LOGOUT page). This paper, and its references,
show convincingly that Machin submitted a paper to the Royal
Society in 1705 or 1706 which described not only the four 2-term
identities listed herein (including his "famous" one),
but also a 3-term identity hitherto attributed to Loney (1893);
moreover Simson (1687-1768) can now be credited with describing,
in 1723, the 3-term identity documented by Klingenstierna in
1730. These attributions have accordingly all been revised.