Re: Salamin-Brent algorithm

On Jun 21, 6:00 pm, Chip Eastham <hardm...@xxxxxxxxx> wrote:
On Jun 21, 6:42 pm, Gerry Myerson <g...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:

In article <1182447514.837296.169...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

dgoldsmith_89 <d.l.goldsm...@xxxxxxxxx> wrote:
if I can just download say like
the first 2^100 binary digits (or 16^25 hex....

Um, 2^100 digits - where would you put them all? Seriously.

Anyway, no one has computed more than a few billion digits
(or bits, or whatever), which is way less than what you want.

Well, I agree with the thought (no one would have
room for 2^100 bits), but actually the computation
of pi has been carried out to one trillion places
(10^12) in both decimal and hexidecimal arithmetic.

http://www.super-computing.org/pi_current.html

Thanks for the reference, that looks like it may be useful.

I note that it mentions they used a different algorithm - Divide &
Rationalize; I haven't had a chance to study that, but I have had a
chance to think about the problem of precision and I think I can
phrase my question a little more clearly.

Assume for the sake of argument that I want to use the S-B algorithm
as described at http://en.wikipedia.org/wiki/Gauss-Legendre_algorithm;
this requires addition, subtraction, multiplication, division and root
taking. Addition and subtraction aren't a big issue as far as
affecting the number of digits one needs to keep around: they never
change the maximum number by more than one, positive or negative.
Multiplication, division, and root-taking, however, are a different
story: division and root-taking (multiplication when we're talking
about the fraction-representing digits, which is of course almost all
the digits in our calculation) right-shift the digits of the numerator/
radicand, meaning that left-most digits which one might have thought
one could dispose of because they represent precision achieved a while
back in the calculation, may instead have to be kept around. But do
they? If so, does this problem only delay one's ability to dispose of
them, or must all digits always be used every step of the way
(necessitating that one's storage capacity increase exponentially,
since one's precision is so increasing with the S-B algorithm)? And
if one can eventually dispose of left-most digits, what's the disposal
criterion?

Does this make sense, or am I missing something which makes these
questions nonsense?

DG
as of Oct. 20, 2005.

regards, chip

.

Relevant Pages

  • Re: Salamin-Brent algorithm
    ... fraction-representing digits, which is of course ... might have thought one could dispose of because ... since one's precision is so increasing with the ... S-B algorithm)? ...
    (sci.math)
  • Re: float bug? perl 5.8, DBI and oracle 10.2.0
    ... precision numbers in oracle, you've got 38 decimal digits to play ... and with minimal coaxing perl will handle them as ... digits from a 32 bit floating point number - I'll go out on a limb ... and hazard that one can expect 12 or so digits from a 64 bit floating ...
    (perl.dbi.users)
  • RE: float bug? perl 5.8, DBI and oracle 10.2.0
    ... I would not characterise 32-bit signed integers as giving 10 digits ... truncate and tell people you get 9 digits of precision. ... perl 5.8, DBI and oracle 10.2.0 ... Floating point values are typically stored in 64 bits or sometimes 96 ...
    (perl.dbi.users)
  • Re: float bug? perl 5.8, DBI and oracle 10.2.0
    ... I would not characterise 32-bit signed integers as giving 10 digits ... truncate and tell people you get 9 digits of precision. ... perl 5.8, DBI and oracle 10.2.0 ... Floating point values are typically stored in 64 bits or sometimes 96 ...
    (perl.dbi.users)
  • Re: 15 Significant Digits Limitation a Mistake for Spatial Informa
    ... DP does not restrict to 15 decimal digits. ... Input and output precision are more tightly linked in Excel ... Decimal data type or roll your own extended precision data types. ...
    (microsoft.public.excel)