On the rapid computation of various polylogarithmic constants

1997/01/01 by David H. Bailey, Peter Borwein, Simon Plouffe · 3 citations
Mathematics · Computer Science · #Advanced Mathematical Identities #Analytic Number Theory Research #Polynomial and algebraic computation #Algorithm #Computer science #Annotation #Artificial intelligence #Mathematics

paper · pdf · doi:10.1090/s0025-5718-97-00856-9

openalex publication_date 1997/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/18

Abstract

We give algorithms for the computation of the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -th digit of certain transcendental numbers in various bases. These algorithms can be easily implemented (multiple precision arithmetic is not needed), require virtually no memory, and feature run times that scale nearly linearly with the order of the digit desired. They make it feasible to compute, for example, the billionth binary digit of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log left-parenthesis 2 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">log (2)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> or <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi"> <mml:semantics> <mml:mi> π </mml:mi> <mml:annotation encoding="application/x-tex">π</mml:annotation> </mml:semantics> </mml:math> </inline-formula> on a modest work station in a few hours run time. We demonstrate this technique by computing the ten billionth hexadecimal digit of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi"> <mml:semantics> <mml:mi> π </mml:mi> <mml:annotation encoding="application/x-tex">π</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , the billionth hexadecimal digits of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi squared comma log left-parenthesis 2 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi> π </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>,</mml:mo> <mml:mspace width="thickmathspace"/> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">π ², log (2)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log squared left-parenthesis 2 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>log</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo> ⁡ </mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">log ²(2)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and the ten billionth decimal digit of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log left-parenthesis 9 slash 10 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>9</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>10</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">log (9/10)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . These calculations rest on the observation that very special types of identities exist for certain numbers like <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi"> <mml:semantics> <mml:mi> π </mml:mi> <mml:annotation encoding="application/x-tex">π</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi squared"> <mml:semantics> <mml:msup> <mml:mi> π </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:annotation encoding="application/x-tex">π ²</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log left-parenthesis 2 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">log (2)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="log squared left-parenthesis 2 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>log</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo> ⁡ </mml:mo>

Citations

• A taxonomy of problems with fast parallel algorithms
• A search for Wieferich and Wilson primes

Cited by

• On the Random Character of Fundamental Constant Expansions
• Approximations of pi [wikipedia]
• Polylogarithm [wikipedia]