This is a package to calculate PI in huge digits. I programmed it for a benchmark of a FFT based multiple-precision routine.

Distribution

pi_fftc6_src.tgz (52KB) , source file only, for UNIX / ver. LG1.1.2-MP1.5.2af updated: 011105 pi_fftc6.zip (358KB) , source file with WIN32 binary / ver. LG1.1.2-MP1.5.2af updated: 011105 pi_fftc5_src.tgz (74KB) , source file only, for UNIX / ver. LG1.1.2-MP1.5.2a updated: 991103 (old) pi_fftc5.zip (334KB) , source file with WIN32 binary / ver. LG1.1.2-MP1.5.2a updated: 991103 (old)

Files in the Package (pi_fftc6)

Makefile : make file - for 32bit CPU: digits <= 6,000,000,000 Makefile_64bit : make file - for 64bit CPU Makefile_quad : make file - for 128bit FPU config.h : machine depending macros fftsgx.c : FFT Package in C - split-radix - use work areas fftsg_hx.c : FFT Package in C - split-radix - use no work areas pi_fftca.c : PI Calc. Program - standard version - use fft*gx.c" pi_fftcs.c : PI Calc. Program - mem save version - use "fft*g_hx.c" pi_fftcw.c : PI Calc. Program - mem swap version - use "fft*g_hx.c" dgt_div.c : data converter - from pi.dat to Super_PI format README.TXT : readme file win32bin/ : DIR win32bin/Makefile : make file - for intel C++ compiler win32bin/pi_cs.exe : Win32 exec. - mem save version win32bin/pi_cs_thread.exe : Win32 exec. - use FFT level threads win32bin/pi_cw.exe : Win32 exec. - mem swap version win32bin/pi_cw_thread.exe : Win32 exec. - use FFT level threads win32bin/dgt_div.exe : data converter - pi.dat => pi.txt a printout format Check macros in "config.h" and modify if necessary. FFT_ERROR_MARGIN is very impotant parameter. If FFT_ERROR_MARGIN is very small then efficiency will be bad. If FFT_ERROR_MARGIN >= 0.5 then it may calculate a wrong result.

Performance (pi_fftc5: old version)

Machine 1

CPU : Pentium III / 550MHz (100MHz X 5.5)

Memory : SDRAM / 512MB (128MB CL2 X 4)

DISK : IDE U-ATA / 22GB (IBM DJNA-372200 X 1)

OS : Linux 2.2.12 (Slackware 4.0), Windows 98 (OEM)

Compiler : pgcc 2.95.2 19991024 pi_cws5
(pi_fftcw.c + fftsg_h.c) 71 sec. total
[65 sec. cpu] 1702 sec. (28 min.) total
[1563 sec. (26 min.) cpu] 23533 sec. (6 h. 32 min.) total
[15748 sec. (4 h. 22 min.) cpu] Super_PI@ Kanada Lab. 237 sec. total 5440 sec. (90 min.) total

pi_fftc*.c + fft4*.c:
44.625 * nfft * (log_2(nfft))^2 [Operations]

pi_fftc*.c + fft8*.c:
42.875 * nfft * (log_2(nfft))^2 [Operations]

pi_fftc*.c + ffts*.c:
42 * nfft * (log_2(nfft))^2 [Operations] ---- Relationship between Number of Digits and FFT Length ----
ndigit = nfft*log_10(R), R >= 10000 or 1000
R is a radix of multiple-precision format. R depends on DBL_ERROR_MARGIN and FFT+machine+compiler's tolerance.

Memory Use (pi_fftc5)

pi_fftc.c, pi_fftca:
nfft * (6 * sizeof(int) + 3.5 * sizeof(double)) [Bytes]

pi_fftcs.c:
nfft * (6 * sizeof(short int) + 3 * sizeof(double)) [Bytes]

pi_fftcw.c:
nfft * (3 * sizeof(short int) + sizeof(double)) [Bytes]

FFT Algorithm

FFT Links

Summary of FFT Programming (in Japanese)

AGM Algorithm

---- a formula based on the AGM (Arithmetic-Geometric Mean) ---- c = sqrt(0.125); a = 1 + 3 * c; b = sqrt(a); e = b - 0.625; b = 2 * b; c = e - c; a = a + e; npow = 4; npow = 2 * npow; e = (a + b) / 2; b = sqrt(a * b); e = e - b; b = 2 * b; c = c - e; a = e + b; } while (e > SQRT_SQRT_EPSILON); e = e * e / 4; a = a + b; pi = (a * a - e - e / 2) / (a * c - e) / npow; ---- modification ---- This is a modified version of Gauss-Legendre formula (by T.Ooura). It is faster than original version.

Reference

E.Salamin, Computation of PI Using Arithmetic-Geometric Mean, Mathematics of Computation, Vol.30 1976.

R.P.Brent, Fast Multiple-Precision Evaluation of Elementary Functions, J. ACM 23 1976.

D.Takahasi, Y.Kanada, Calculation of PI to 51.5 Billion Decimal Digits on Distributed Memoriy Parallel Processors, Transactions of Information Processing Society of Japan, Vol.39 No.7 1998.

T.Ooura, Improvement of the PI Calculation Algorithm and Implementation of Fast Multiple-Precision Computation, Information Processing Society of Japan SIG Notes, 98-HPC-74, 1998.

source files:
You may use, copy, modify and distribute this code for any purpose (include commercial use) and without fee. Please refer to this package when you modify this code.