Debian Codegraph @

examples/spigot-subdir/src/spigot.c

raw
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 /* Register this DSO to Gauche */
156 SCM_INIT_EXTENSION(spigot);
157
158 /* Create "spigot" module if it doesn't exist yet. */
159 ScmModule *mod = SCM_MODULE(SCM_FIND_MODULE("spigot", TRUE));
160
161 /* Initialize spigotlib.scm */
162 Scm_Init_spigotlib();
163 }