Comment Re:Quick question (Score 1) 67
/*
* Computation of the n'th decimal digit of \pi with very little memory.
* Written by Fabrice Bellard on January 8, 1997.
*
* We use a slightly modified version of the method described by Simon
* Plouffe in "On the Computation of the n'th decimal digit of various
* transcendental numbers" (November 1996). We have modified the algorithm
* to get a running time of O(n^2) instead of O(n^3log(n)^3).
*
* This program uses mostly integer arithmetic. It may be slow on some
* hardwares where integer multiplications and divisons must be done
* by software. We have supposed that 'int' has a size of 32 bits. If
* your compiler supports 'long long' integers of 64 bits, you may use
* the integer version of 'mul_mod' (see HAS_LONG_LONG).
*/
#include
#include
#include
#ifdef HAS_LONG_LONG
#define mul_mod(a,b,m) (( (long long) (a) * (long long) (b) ) % (m))
#else
#define mul_mod(a,b,m) fmod( (double) a * (double) b, m)
#endif
int inv_mod(int x, int y)
{
int q, u, v, a, c, t;
u = x;
v = y;
c = 1;
a = 0;
do {
q = v / u;
t = c;
c = a - q * c;
a = t;
t = u;
u = v - q * u;
v = t;
} while (u != 0);
a = a % y;
if (a > 1;
if (b == 0)
break;
aa = mul_mod(aa, aa, m);
}
return r;
}
int is_prime(int n)
{
int r, i;
if ((n % 2) == 0)
return 0;
r = (int) (sqrt(n));
for (i = 3; i = a) {
do {
t = t / a;
v--;
} while ((t % a) == 0);
kq = 0;
}
kq++;
num = mul_mod(num, t, av);
t = (2 * k - 1);
if (kq2 >= a) {
if (kq2 == a) {
do {
t = t / a;
v++;
} while ((t % a) == 0);
}
kq2 -= a;
}
den = mul_mod(den, t, av);
kq2 += 2;
if (v > 0) {
t = inv_mod(den, av);
t = mul_mod(t, num, av);
t = mul_mod(t, k, av);
for (i = v; i = av)
s -= av;
}
}
t = pow_mod(10, n - 1, av);
s = mul_mod(s, t, av);
sum = fmod(sum + (double) s / (double) av, 1.0);
}
printf("Decimal digits of pi at position %d: %09d\n", n,
(int) (sum * 1e9));
return 0;
}
