On the rapid computation of various polylogarithmic constants 论文

摘要

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">\pi</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">\pi</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">\pi ^{2}, \; \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}(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">\pi</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">\pi ^{2}</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>