Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2007
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Pi upto a Billion Digits

  • To: mathgroup at smc.vnet.net
  • Subject: [mg75725] Re: [mg75672] Re: Pi upto a Billion Digits
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Wed, 9 May 2007 04:33:37 -0400 (EDT)
  • References: <f1msfm$rnf$1@smc.vnet.net> <200705080954.FAA18685@smc.vnet.net>

Szabolcs wrote:
> Raj wrote:
> 
>>hi!
>>
>>Could somebody tell me if they ever tried finding Pi upto a billion
>>digits using the N function:
>>N[Pi,10^9] and how long did it take?
>>
>>Thanks,
>>
>>Raj
> 
> 
> I haven't tried it, but you can estimate how long it takes, like this:
> 
> d = Table[Update[]; First@Timing[N[Pi, 2^k 10^5]], {k, 1, 6}]/Second
> 
> {1.437, 3.579, 9.14, 23.375, 58.453, 143.391}
> 
> (Results are from Mathematica 5.2, 1.7 GHz processor.)
> 
> ListPlot[Log@d]
> 
> Now we can extrapolate. Find the slope of Log@d
> 
> slope = Mean@ListConvolve[{1, -1}, Log@d]
> 
> 0.920604
> 
> 10^9 is approximately 2^12 * 10^5, so you can expect
> 
> Exp[11*slope + d[[1]] ]
> 
> 105202.
> 
> This is approximately 30 hours. Of course this result may be an order of 
> magnitude off, but I suspect that the precise result is less than 30 
> hours, not more. With a little patience you can get a much better estimate.
> 
> Or you can leave the calculation running for a day and hope that you 
> don't run out of memory (memory usage may be a bigger problem than CPU 
> time). If you do run the calculation, please let us know your findings.
> 
> But note that the time to export the result to a file may be comparable 
> to the time of the calculation (or even much longer -- Mathematica I/O 
> is pretty slow).
> 
> Szabolcs

I'll comment on that last part. First we rerun the computation. I'm 
using version 6 on a Linux machine, around 3 GHz.

In[8]:= d = Table[ClearSystemCache[];
   First[Timing[v[k]=N[Pi,2^k*10^5]]], {k,1,7}]
Out[8]= {0.47603, 1.08807, 2.56416, 6.09238, 14.2249, 31.874, 73.5246}

What we see is "soft" linear time, roughly that associated with the 
(bit) complexity of multiplication.

Now we convert to strings of digits.

In[12]:= f = Table[First[Timing[s10[k]=RealDigits[v[k]]]], {k,7}]
Out[12]= {0.176011, 0.47603, 1.12407, 2.77217, 6.65242, 15.861, 37.3623}

We see similar complexity. Not surprising, because the conversion from 
binary to decimal involves division, which has the same complexity as 
multiplication.

If we avoid the b2d conversion it becomes a byte faster.

In[13]:= g = Table[First[Timing[s16[k]=RealDigits[v[k],16]]], {k,7}]
Out[13]= {0.004, 0.008002, 0.012, 0.020002, 0.036002, 0.076004, 0.15201}

Outputting the results e.g. to a file will show similar behavior to 
RealDigits; slow if in decimal and relatively fast if in hex. Upshot: 
This has little to do with I/O, and more to do with conversion of large 
numbers from binary to decimal form.

Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: Re: Pi upto a Billion Digits
  • Next by Date: Re: Re: Pi upto a Billion Digits
  • Previous by thread: Re: Pi upto a Billion Digits
  • Next by thread: Re: Pi upto a Billion Digits