Help System (web edition)

Algorithms used in multiprecision calculations

Calculations are done with floating point numbers in base 1000.
The number of significant (decimal) digits may be over one million
and the range of exponents is about (-2000000000,2000000000).
Thus very huge and tiny numbers can be represented:
................................................................................
ACCURACY=1000,20
2^(2^1000)=0.3058075504150725262e1964555237
2^(-2^1000)=0.3270030444450113159e-1964555236
2^(2^1000)*2^(-2^1000)=0.9999999999999999999
................................................................................
The multiplications with long numbers (over 400 digits) are performed
by using FFT (Fast Fourier Transformation) instead of the standard
'Schoolboy' scheme. The latter has computational complexity proportional
to n^2 while FFT multiplication is proportional to n*log(n)*log(log(n))
only.
Divisions and square roots are calculated by Newton-Raphson iteration.
Various transcendental functions are computed either from their Taylor's
series expansions (after suitable transformations to speed up
convergence) or by the AGM (arithmetic-geometric mean) technique.

................................................................................
Example: Natural logarithms
The logarithm of 10 is with ACCURACY=50
log(10)=0.23025850929940456840179914546843642076011014886287e1
It is actually computed by the formula
L(x,m):=#PI/(2*m*agm(1,4/x^m))
giving
L(10,26)=0.23025850929940456840179914546843642076011014886287e1
................................................................................
Above #PI is the universal constant =3.14159265... computed and saved
permanently in file <Survo>\U\SYS\#PI.NBR with at least 100000 digits
by the command
ARIT PI,#PI / ACCURACY=100000 .
Parameter m should exceed ACCURACY/2.
agm(x,y) is the arithmetic-geometric mean of numbers x and y, i.e.
obtained as a limit of the following iteration:

Let x(0)=x, y(0)=y.
Iteration step from n to n+1:
x(n+1)=[x(n)+y(n)]/2       arithmetic mean
y(n+1)=sqrt[x(n)*y(n)]     geometric mean

References:

David H. Bailey: A Portable High Performance Multiprecision Package.
RNR Technical Report RNR-90-022 (1993)

Richard P. Brent: Fast Multiple-Precision Evaluation of Elementary Functions.
Journal of the ACM, Vol.23, No.2, April 1976, pp.242-251.

Donald E. Knuth: The Art of Computer Programming, Vol.2.
Addison Wesley, 1981.


   P = More on multiprecision computations