| 1 |
/* |
| 2 |
* spigot.c - calculate pi and e by spigot algorithm |
| 3 |
* |
| 4 |
* Written by Shiro Kawai ([email protected]) |
| 5 |
* I put this program in public domain. Use it as you like. |
| 6 |
*/ |
| 7 |
|
| 8 |
#include <gauche.h> |
| 9 |
#include <gauche/extend.h> |
| 10 |
#include <math.h> |
| 11 |
#include "spigot.h" |
| 12 |
|
| 13 |
/* The spigot algorithm for pi: |
| 14 |
|
| 15 |
pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + ... (2 + k/(2k+1)*(2 + ...)) ...))) :[1] |
| 16 |
|
| 17 |
The last term can be approximated by: |
| 18 |
|
| 19 |
2 + k/(2k+1)*(4) |
| 20 |
|
| 21 |
where |
| 22 |
|
| 23 |
k = n * log2 (10) |
| 24 |
|
| 25 |
for a desired precision of n decimal digits. |
| 26 |
|
| 27 |
Now, pi is 3.14159 ... in decimal. That means: |
| 28 |
|
| 29 |
pi = 3 + 1/10*(1 + 1/10*(4 + 1/10*(1 + 1/10*(5 + 1/10*(9 + ....))))) :[2] |
| 30 |
|
| 31 |
Note the similality of [1] and [2]. If we think a special variable |
| 32 |
base system that the k-th digit after point has the weight of k/(2k+1) |
| 33 |
of the previous digit, [1] means pi can be written as [2.222222...] |
| 34 |
in such a base system. |
| 35 |
|
| 36 |
Base: [1/3, 2/5, 3/7, ... , k/(2k+1), ...] |
| 37 |
Number: [2 . 222222222 ...] |
| 38 |
|
| 39 |
Base: [1/10, 1/10, 1/10, ....] |
| 40 |
Number: [3 . 141592653 ...] |
| 41 |
|
| 42 |
Now, calculating pi is effectively a base conversion problem. |
| 43 |
|
| 44 |
The actual calculation process is explained in detail at: |
| 45 |
http://membres.lycos.fr/bgourevitch/mathematiciens/goutte/goutte.html |
| 46 |
|
| 47 |
It uses a table, but the rows "A" and "B" are mechanically calculated, |
| 48 |
and the rows "retenue", "somme", and "reste" can share the same array |
| 49 |
for those columns are calculated left to right for each iteration. |
| 50 |
Thus we need to keep only one array to hold intermediate calculation. |
| 51 |
|
| 52 |
E can be calculated in the same way, starting from the following number: |
| 53 |
|
| 54 |
Base: [1, 1/2, 1/3, 1/4, ... , 1/(k-1), ...] |
| 55 |
Number: [1 . 11111111 ...] |
| 56 |
|
| 57 |
The following code is a very naive implementation of the algorithm. |
| 58 |
You would get less memory footprint and faster calculation by using |
| 59 |
big digit, like 10000 instead of 10. |
| 60 |
*/ |
| 61 |
|
| 62 |
ScmObj Spigot_calculate_pi(int digits) |
| 63 |
{ |
| 64 |
int k, i, j, l, b, q, r, *array; |
| 65 |
ScmObj rvec, *relts; |
| 66 |
|
| 67 |
if (digits <= 0) Scm_Error("digits must be a positive integer"); |
| 68 |
|
| 69 |
/* Scheme vector to keep the result */ |
| 70 |
rvec = Scm_MakeVector(digits, SCM_MAKE_INT(0)); |
| 71 |
relts = SCM_VECTOR_ELEMENTS(rvec); |
| 72 |
|
| 73 |
/* Prepare the array for variable base system */ |
| 74 |
k = (int)floor(digits * 3.3219280948873626); |
| 75 |
array = SCM_NEW_ATOMIC2(int *, (k+1)*sizeof(int)); |
| 76 |
for (i=0; i<k; i++) array[i] = 2; |
| 77 |
array[k] = 4; |
| 78 |
|
| 79 |
for (i=0, b=2; i<digits; i++) { |
| 80 |
q = 0; |
| 81 |
for (j=k; j>0; j--) { |
| 82 |
q += array[j] * 10; |
| 83 |
array[j] = q % (2*j+1); |
| 84 |
q /= 2*j+1; |
| 85 |
q *= j; |
| 86 |
} |
| 87 |
r = b + q/10; |
| 88 |
b = q % 10; |
| 89 |
/* Here, we have the i-th digit in r. |
| 90 |
In rare occasions, r becomes more than 10, and we need to back-up |
| 91 |
to increment the previous digit(s). (It's rarely the case that |
| 92 |
this back-up cascades for more than one digit). */ |
| 93 |
if (r < 10) { |
| 94 |
relts[i] = SCM_MAKE_INT(r); |
| 95 |
} else { |
| 96 |
relts[i] = SCM_MAKE_INT(r%10); |
| 97 |
for (l=i-1, r/=10; r && l>=0; l--, r/=10) { |
| 98 |
r += SCM_INT_VALUE(relts[l]); |
| 99 |
relts[l] = SCM_MAKE_INT(r%10); |
| 100 |
} |
| 101 |
} |
| 102 |
} |
| 103 |
return rvec; |
| 104 |
} |
| 105 |
|
| 106 |
ScmObj Spigot_calculate_e(int digits) |
| 107 |
{ |
| 108 |
int k, i, j, l, b, q, r, *array; |
| 109 |
ScmObj rvec, *relts; |
| 110 |
|
| 111 |
if (digits <= 0) Scm_Error("digits must be a positive integer"); |
| 112 |
|
| 113 |
/* Scheme vector to keep the result */ |
| 114 |
rvec = Scm_MakeVector(digits, SCM_MAKE_INT(0)); |
| 115 |
relts = SCM_VECTOR_ELEMENTS(rvec); |
| 116 |
|
| 117 |
/* Prepare the array for variable base system */ |
| 118 |
k = (int)floor(digits * 3.3219280948873626); |
| 119 |
array = SCM_NEW_ATOMIC2(int *, (k+1)*sizeof(int)); |
| 120 |
for (i=0; i<k; i++) array[i] = 1; |
| 121 |
array[k] = 2; |
| 122 |
|
| 123 |
for (i=0, b=1; i<digits; i++) { |
| 124 |
q = 0; |
| 125 |
for (j=k; j>0; j--) { |
| 126 |
q += array[j] * 10; |
| 127 |
array[j] = q % j; |
| 128 |
q /= j; |
| 129 |
} |
| 130 |
r = b + q/10; |
| 131 |
b = q % 10; |
| 132 |
/* Here, we have the i-th digit in r. |
| 133 |
In rare occasions, r becomes more than 10, and we need to back-up |
| 134 |
to increment the previous digit(s). (It's rarely the case that |
| 135 |
this back-up cascades for more than one digit). */ |
| 136 |
if (r < 10) { |
| 137 |
relts[i] = SCM_MAKE_INT(r); |
| 138 |
} else { |
| 139 |
relts[i] = SCM_MAKE_INT(r%10); |
| 140 |
for (l=i-1, r/=10; r && l>=0; l--, r/=10) { |
| 141 |
r += SCM_INT_VALUE(relts[l]); |
| 142 |
relts[l] = SCM_MAKE_INT(r%10); |
| 143 |
} |
| 144 |
} |
| 145 |
} |
| 146 |
return rvec; |
| 147 |
} |
| 148 |
|
| 149 |
/* |
| 150 |
* Module initialization function. |
| 151 |
* This is called when math--spigot.so is dynamically loaded into gosh. |
| 152 |
*/ |
| 153 |
void Scm_Init_math__spigot(void) |
| 154 |
{ |
| 155 |
ScmModule *mod; |
| 156 |
|
| 157 |
/* Register this DSO to Gauche */ |
| 158 |
SCM_INIT_EXTENSION(spigot); |
| 159 |
|
| 160 |
/* Create "spigot" module if it doesn't exist yet. */ |
| 161 |
mod = SCM_MODULE(SCM_FIND_MODULE("spigot", TRUE)); |
| 162 |
|
| 163 |
/* Initialize spigotlib.scm */ |
| 164 |
Scm_Init_spigotlib(); |
| 165 |
} |