# Computation of the n’th digit of in any base in O(n^2)

*by*Phil Tadros

!Transformed with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, College of Leeds >

**Fabrice Bellard**

** This text is an alpha model. Please ship any feedback to Fabrice.Bellard@enst.fr **

Simon Plouffe defined in [1] a brand new algorithm to compute the

n’th digit of and another mathematical constants in any base with

little or no reminiscence. Its working time is . We

current right here an enchancment of this algorithm whose working time is

whereas its reminiscence necessities keep , which makes it

sensible to compute the millionth digit of for instance.

We need to compute the **n**‘th digit in base **B** of **s**, the place

Let , and

. We now have

with the Chinese language the rest theorem. Therefore

The ‘th digits of **s**, the place , are the digits in base **B** of

With the final method now we have

As proven in [1], this equality is fascinating as a result of every time period

could be computed separatly, with a complete reminiscence of if we already

know **b** and .

We wish now to compute the **n**‘th digit in base **B** of , the place

with

With the primary consequence now we have

the place

with

and

The important thing statement is that we are able to use for all the identical

modulo, therefore

This may be rewritten

To have the digits after the n’th one, in base B, we compute

The working time is and the reminiscence necessities keep

if we suppose that:

Given

we are able to use the results of part 2 as a result of if **p** is a

prime quantity, we discover that

the place is the multiplicity of

**p** in **n**. It comes from the relation

Therefore, if we would like the n’th digit of in base B, we might use the

following algorithm:

The working time is as a result of there are

prime numbers between **2** and **2n** . The reminiscence necessities are, as

anticipated, in .

We now have introduced an algorithm to compute the n’th digit in any base B of

whose working time is . It has the identical working time as different

classical strategies for computing (e.g. arctangent formulation), but it surely

makes use of little reminiscence, it is rather easy and doesn’t want excessive precision

computations. It’s nonetheless slower than the BBP algorithm [2], but it surely

works in any base. As described in [1], the identical algorithm might

be used to compute different numbers resembling , , ,

and .

## References

**1**- Simon Plouffe,
*On the computation of the n’th*, November 1996.

decimal digit of assorted transcendental numbers **2**- David H. Bailey, Peter B. Borwein and

Simon Plouffe,*On the Speedy Computation of Numerous Polylogarithmic*, April 1997 in Arithmetic of Computation.

Constants

Solar Jan 12 22:34:36 MET 1997

Fabrice Bellard (

http://bellard.org/ )