Re: Computing decimals of pi

On May 24, 8:51 pm, "James H. Newman" <NewJa...@xxxxxxxxxxx> wrote:
On Sat, 24 May 2008 17:57:29 -0700, Mensanator wrote:
On May 24, 1:02 pm, "James H. Newman" <NewJa...@xxxxxxxxxxx> wrote:
On Sat, 24 May 2008 10:07:12 -0700, Mensanator wrote:
On May 24, 11:20�am, "James H. Newman" <NewJa...@xxxxxxxxxxx> wrote:
On Sat, 24 May 2008 10:42:11 -0400, Joshua Cranmer wrote:
James H. Newman wrote:
Not quite - I am afraid I did not explain myself correctly.

My understanding is that when using those methods to produce millions
upon millions of decimals of pi, when attempting to compute (say) N
decimals one has to carry out all the intermediate computations to a
precision of N decimals

Not necessarily. Pi can be computed to arbitrary precision using an
infinite series of arbitrary precision rationals. They start out small
and the terms needn't be kept in memory, only the sum does.

The decimal places aren't calculated until the end when the rational
sum is converted to floating point.

Could you please provide specific examples?

Ok, here's the formula I use:

pi/2 = 1 + 1/3 + (1*2)/(3*5) + (1*2*3)/(3*5*7) + ...

Note that this is for pi/2, so I have to multiply by two to get the
actual digits of pi. But also note how each term differs from the
previous:

numerator:   multiply by 1 more
1       then
1*2     then
1*2*3   then
1*2*3*4 etc.
denominator: multiply by 2 more
3       then
3*5     then
3*5*7   then
3*5*7*9 etc.

For a single term, the rational becomes 2.0, not a very good
approximation of pi. So we add a second term 1/3 (times two remember)
making the sum 2.666..., still not very good. But if we keep at it long
enough

current sum: 2.0 next term: 1/3
current sum: 2.66666666666666666663 next term: 2/15 current sum:
2.93333333333333333328 next term: 2/35 current sum:
3.04761904761904761901 next term: 8/315 current sum:
3.09841269841269841261 next term: 8/693 current sum:
3.12150072150072150062 next term: 16/3003 current sum:
3.13215673215673215673 next term: 16/6435 current sum:
3.13712953712953712953 next term: 128/109395 current sum:
3.13946968064615123436 next term: 128/230945 current sum:
3.14057816968033686291 next term: 256/969969 current sum:
3.14110602160137763843 next term: 256/2028117 current sum:
3.1413584725201362703 next term: 1024/16900975 current sum:
3.14147964896114041352 next term: 1024/35102025 current sum:
3.14153799317347574177 next term: 2048/145422675 current sum:
3.14156615934494796917 next term: 2048/300540195 current sum:
3.14157978813759582116 next term: 32768/9917826435 current sum:
3.14158639603706144636 next term: 32768/20419054425 current sum:
3.14158960558823046434 next term: 65536/83945001525 current sum:
3.14159116699150187839 next term: 65536/172308161025 current sum:
3.14159192767514692634 next term: 262144/1412926920405 current sum:
3.1415922987403396326 next term: 262144/2893136075115 current sum:
3.14159247995822444265 next term: 524288/11835556670925 current sum:
3.14159256855363479429 next term: 524288/24185702762325 current sum:
3.1415926119088356046 next term: 4194304/395033145117975

we eventually have pi accurate to 8 digits. We don't need millions of
digits at this point. And all these early terms get discarded, only the
rational sum remains. Eventually, we'll need some number with millions
of digits (bits actually) but a single such number is better that
millions of such numbers.

To get a 1000 digits of pi takes this program 3317 terms.


Is it not the case that in order to obtain 8 decimals you need to
compute each of those fractions to a precision of at least 8
decimals?

No. I don't NEED to convert any of the fractions
until the end. Now that I know it takes about
three times as many terms as decimal places,
I could wait until I've done 3000 terms before
starting to check the 1000th decimal place for
convergence.

By doing the calculation entirely with rationals,
there are no decimal places involved at all and
thus, no rounding errors. Of course, many decimal
places of the final rational are discarded, we only
keep them to point where they've converged.

And even though no decimal places are involed, the
integers that make up the numerator and denominator
get quite large with up to twice as many digits as
we're trying to find decimal places. But we are
constantly updating this sum, not creating new ones.
That's why the memory use isn't so bad.

In
general, if we wanted to compute N decimals of pi we would need to
compute each of those fractions to N decimals,
and then perform additions to N decimals, right?

No, we don't convert the fractions to decimal,
they are left as fractions and the math does
the calculations as fractions. If you did as
you say, you would still have rounding problems
even with your millions of decimal places.


My question was whether one could obtain N decimals of pi by
performing a (possibly humongous) number of operations,
each of them to a precision of n decimals, where n < N
(possibly << N)

Sure, it COULD be done that way. The problem with
using floating point with a humungous number of
operations is the potential for loss of precision
(And having millions of decimal places won't prevent
that). The big advantage of rationals is there is
NEVER loss of precision no matter how many operations
you do (assuming, of course, that the rationals are
composed of arbitrary precision integers).

When my program converts the rational to decimal,
it only checks the desired place for convergence
and then discards the floating point number. And
all the rounding baggage is discarded along with it,
so the errors don't accumulate like they would if we
were adding the n decimal places.

.

Relevant Pages

  • RE: Currency rounding problem
    ... Marsh I agree with you both sets of numbers may be correct but the sum is ... Regardless of the tax calculation I ... individual amounts (rounded to show two decimals) appear "right" also. ... digits yet individual results are based on one number, and totals based on ...
    (microsoft.public.access.reports)
  • Re: Computing decimals of pi
    ... upon millions of decimals of pi, when attempting to compute N ... infinite series of arbitrary precision rationals. ... and the terms needn't be kept in memory, only the sum does. ... we eventually have pi accurate to 8 digits. ...
    (sci.math)
  • Re: A rational proposal
    ... They don't handle decimals or rationals. ... and a float or complex will be returned. ... Decimals also have limited precision. ...
    (comp.lang.python)
  • RE: Overtime Calculations
    ... "Luke M" wrote: ... This formula has weekly salary in A2, and your SUM in G17. ... have to convert to decimals and input that into formula. ... The spreadsheet totals the hours and deducts the time taken ...
    (microsoft.public.excel.misc)
  • Re: Query - Error: Expression caused an overflow
    ... What is the data type of your Unit column? ... It seems that the Sum of all selected Units rows exceed the maximum value ... SELECT Sumas sumUnits, tWorkReport.CreatedDate, ... the format as decimal looses its decimals when converting to integer. ...
    (microsoft.public.sqlserver.ce)