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

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

2023-11-10 19:08:22

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

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




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

See Also

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
decimal digit of assorted transcendental numbers
, November 1996.
2
David H. Bailey, Peter B. Borwein and
Simon Plouffe, On the Speedy Computation of Numerous Polylogarithmic
Constants
, April 1997 in Arithmetic of Computation.


Solar Jan 12 22:34:36 MET 1997
Fabrice Bellard (
http://bellard.org/
)

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top