1 |
<html> |
2 |
|
3 |
<head> |
4 |
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"> |
5 |
<meta name="GENERATOR" content="Microsoft FrontPage 4.0"> |
6 |
<meta name="ProgId" content="FrontPage.Editor.Document"> |
7 |
<title>How To Use The GMP And Perform Large Integer Or High-Precision Arithmetic |
8 |
On SourceForge Web Sites</title> |
9 |
<base target="main"> |
10 |
</head> |
11 |
|
12 |
<body background="../../bkgnds/bk10.gif"> |
13 |
|
14 |
<p align="center"><b><font size="4">How To Use The <a href="http://www.swox.com/gmp"> GMP</a> And Perform Large Integer |
15 |
Or High-Precision Arithmetic On <a href="http://www.sourceforge.net"> SourceForge</a> Web Sites</font></b></p> |
16 |
<hr> |
17 |
<p><b>04/15/03:</b> I (Dave Ashley) have several number theory CGI pages |
18 |
here at <a href="http://www.sourceforge.net">SourceForge</a>. These pages |
19 |
do things like calculate the GCD of two integers, find best rational |
20 |
approximations, etc.; and they do need arbitrarily large integer capability to |
21 |
be useful. It was quite difficult to obtain large integer capability for |
22 |
these pages. Here are the steps I went through, and the eventual solution |
23 |
(in the hopes that it helps others).</p> |
24 |
<ul> |
25 |
<li>I had used the <i>bcmath</i> library with PHP before (it is built into the |
26 |
version of PHP I have on my Linux box at home). Unfortunately, I |
27 |
discovered immediately that the version of PHP used by <i>SourceForge</i> |
28 |
does not have <i>bcmath</i> built in.</li> |
29 |
<li>I tried writing arbitrary integer functions using PHP. These proved |
30 |
to be painfully inefficient. I abandoned the effort when early |
31 |
observations indicated that these probably would not allow calculation of a |
32 |
couple hundred rounds of <a href="../../phpcgibin/euclid_gcd.php">Euclid's |
33 |
GCD algorithm</a> in a practical time (not too long for a user to wait, and |
34 |
within the CPU time limits for a PHP script).</li> |
35 |
<li>I tried writing a separate program in 'C' to do the calculations using the |
36 |
<a href="http://www.swox.com/gmp">GMP library</a>, and tried calling this |
37 |
program from the PHP script using the <i>exec()</i> function. This |
38 |
worked famously at home, but did not work at <i>SourceForge</i>. The |
39 |
behavior at <i>SourceForge</i> was a mystery because using a shell I could |
40 |
invoke the program successfully, but PHP could not invoke it.</li> |
41 |
<li>I completed a <i>SourceForge</i> support ticket. The response to the |
42 |
ticket indicated that: |
43 |
<ul> |
44 |
<li>The GMP is installed on the shell servers but not the web servers, |
45 |
which is why I could run the compiled external program from a shell but |
46 |
not from PHP.</li> |
47 |
<li>The solution is to compile the GMP library, place it in the <i>SourceForge</i> |
48 |
web space, and link to it.</li> |
49 |
</ul> |
50 |
</li> |
51 |
<li>After much experimentation, I discovered that I could not figure out how |
52 |
to place another copy of the GMP library in the web space at SourceForge and |
53 |
link to it. As best I could glean, there are security implications to |
54 |
replacing libraries (perhaps one could trick a program into dynamically |
55 |
linking with the a trojan library), and so dynamically linked libraries |
56 |
could only exist in certain locations (all paths which belong to <i>root</i>).</li> |
57 |
<li>However, I also discovered that I could statically link my program with |
58 |
the GMP (which gives a much larger executable), and place that much larger |
59 |
executable on <i>SourceForge</i> and run it. The executable went from |
60 |
about 20K to 500K when static linking was specified.</li> |
61 |
</ul> |
62 |
<p>All that being said, here are the specific steps I took to use the GMP from |
63 |
PHP:</p> |
64 |
<ul> |
65 |
<li>Be sure that the GMP is installed on your system (the one you are using |
66 |
for compiling). You need both the library and the development |
67 |
files. Here is what shows on my system at home:<br> |
68 |
<br> |
69 |
<font face="Courier">[apache@khinchin apache]$ rpm -q -a | grep gmp<br> |
70 |
gmp-4.0.1-3<br> |
71 |
gmp-devel-4.0.1-3</font><br> |
72 |
<br> |
73 |
Note that both GMP and GMP-devel are installed.<br> |
74 |
<br> |
75 |
On a <a href="http://www.redhat.com">RedHat</a> system, you can use <font face="Courier">rpm</font> |
76 |
to install the packages. On other systems, you may need to install |
77 |
differently or compile and install them from source.</li> |
78 |
<li>Because static linking bloats the executable, the sanest approach (and the |
79 |
one I use) is to write <i>one</i> executable and have it do all the number |
80 |
crunching for all of your PHP scripts. (By writing one executable, the |
81 |
GMP library is present in only one place--that one executable.) The |
82 |
executable I wrote accepts a subfunction code, which is essentially an |
83 |
indication of which PHP script is calling it. Thus, my single |
84 |
executable does GCD calculation, best rational approximations, Miller-Rabin |
85 |
testing, etc., depending on the command-line parameters (which are |
86 |
controlled by the calling PHP script).<br> |
87 |
<br> |
88 |
For example, when the GCD PHP script calls the executable, it uses the |
89 |
subfunction code "gcd" and gets output like this (when finding the |
90 |
GCD of 27 and 150):<br> |
91 |
<br> |
92 |
<font face="Courier" size="2">[apache@khinchin phpcgibin]$ ./arith_large_cgi gcd 27 150<br> |
93 |
S<br> |
94 |
27<br> |
95 |
150<br> |
96 |
1<br> |
97 |
150<br> |
98 |
27<br> |
99 |
5<br> |
100 |
15<br> |
101 |
2<br> |
102 |
27<br> |
103 |
15<br> |
104 |
1<br> |
105 |
12<br> |
106 |
3<br> |
107 |
15<br> |
108 |
12<br> |
109 |
1<br> |
110 |
3<br> |
111 |
4<br> |
112 |
12<br> |
113 |
3<br> |
114 |
4<br> |
115 |
0<br> |
116 |
3<br> |
117 |
S<br> |
118 |
</font><br> |
119 |
On the other hand, when doing Miller-Rabin testing to see if a certain |
120 |
number is prime (101, for example), the single executable is called like |
121 |
this and produces this output:<br> |
122 |
<br> |
123 |
<font face="Courier" size="2">[apache@khinchin phpcgibin]$ ./arith_large_cgi gmp_prob_prime |
124 |
101 25<br> |
125 |
S<br> |
126 |
101<br> |
127 |
25<br> |
128 |
2<br> |
129 |
S<br> |
130 |
</font><br> |
131 |
In the first example above, the numbers which are emitted by the program are |
132 |
data from successive rounds of Euclid's GCD algorithm (which the PHP script |
133 |
formats and displays). In the second case, the output is, |
134 |
respectively, the number whose primality is to be determined (an echo back), |
135 |
the number of rounds of Miller-Rabin testing (again, and echo-back), and |
136 |
finally a code to indicate the testing results (0 = a compsite number, 1 = |
137 |
probably a prime number, and 2 = definitely a prime number). The |
138 |
output of the program is meant to be interpreted by the calling PHP script |
139 |
(i.e. it is not human-friendly).<br> |
140 |
<br> |
141 |
Also note that the first and last lines of the output are |
142 |
"S". This prevents the calling PHP script from assuming all |
143 |
output is present if the program coredumps or somehow terminates. The |
144 |
calling PHP script checks the number of lines and also checks for the |
145 |
starting and ending "S" characters.</li> |
146 |
<li>Accomplishing static linking is a little bit tricky. Here are the |
147 |
conditions that need to be met: |
148 |
<ul> |
149 |
<li>The static GMP library has to be on the system you use for compilation |
150 |
(it is by default). If it is not present, you may need to compile |
151 |
and install the GMP from source code.</li> |
152 |
<li>When calling the <i>gcc</i> compiler, the <font face="Courier">-static</font> |
153 |
switch can be anywhere, but the <b><font face="Courier">-lgmp</font> |
154 |
switch must be near the end of the command line, after the modules that |
155 |
reference the GMP</b>. This is because <i>gcc</i> links from left |
156 |
to right. For example, my program is built like this:<br> |
157 |
<br> |
158 |
<font face="Courier">gcc -static -o arith_large_cgi arith_large_cgi.c auxfuncs.c subfunc_gcd.c subfunc_gmp_prob_prime.c -lgmp</font><br> |
159 |
<br> |
160 |
Notice that the <font face="Courier">-lgmp</font> switch is at the end |
161 |
of the command line.</li> |
162 |
</ul> |
163 |
</li> |
164 |
<li>The executable can be placed in the same directory as the PHP scripts (it |
165 |
will always find it there).</li> |
166 |
<li>The PHP <i>exec()</i> function is well-documented. You can give it a |
167 |
variable in which it will store the output of the called program in an |
168 |
array. For example, from one of my PHP scripts, here is the code which |
169 |
calls <i>exec()</i> and also checks the output for sanity.<br> |
170 |
<br> |
171 |
<font face="Courier" size="2"> //We can now run the external program to do the calculation.<br> |
172 |
$cgi_command_string = "./arith_large_cgi gcd " . $N1 . " " . $N2;<br> |
173 |
<br> |
174 |
exec($cgi_command_string, $cgi_result);<br> |
175 |
$cgi_result_nelem = count($cgi_result);<br> |
176 |
<br> |
177 |
//We need to perform some sanity checks on the CGI output to be sure it<br> |
178 |
//is what we want. If it seems wrong, we need to generate an error message<br> |
179 |
//and not try to display the output.<br> |
180 |
$cgi_output_is_sane = 1;<br> |
181 |
if ($cgi_result_nelem == 0)<br> |
182 |
$cgi_output_is_sane = 0;<br> |
183 |
if ($cgi_result_nelem > 0)<br> |
184 |
{<br> |
185 |
if (($cgi_result_nelem % 5) != 0)<br> |
186 |
$cgi_output_is_sane = 0;<br> |
187 |
if ($cgi_result[0] != "S")<br> |
188 |
$cgi_output_is_sane = 0;<br> |
189 |
if ($cgi_result[$cgi_result_nelem - 1] != "S")<br> |
190 |
$cgi_output_is_sane = 0;<br> |
191 |
}<br> |
192 |
<br> |
193 |
if (!$cgi_output_is_sane)<br> |
194 |
{<br> |
195 |
do_err_msg("An unspecified error occurred when ...<br> |
196 |
</font><br> |
197 |
Notice how the snippet above checks the output of the program for sanity.</li> |
198 |
<li>Finally, you must have the execute permission for <i>other</i> (the web |
199 |
server is <i>other</i>) set in your compiled executable, or else PHP cannot |
200 |
run the compiled program. You can change these permissions with the <i>chmod</i> |
201 |
command.</li> |
202 |
</ul> |
203 |
<p align="left">Please drop <a href="mailto:dtashley@users.sourceforge.net">me</a> |
204 |
an e-mail if I should change or enhance this documentation or if there is a |
205 |
better way to do something.</p> |
206 |
<hr> |
207 |
<p align="center" style="margin-top: -2; margin-bottom: -1"><font size="1">This |
208 |
web page is maintained by <a href="mailto:dtashley@users.sourceforge.net">David |
209 |
T. Ashley</a>.<br>$Header: /cvsroot/esrg/sfesrg/esrgweba/htdocs/howtos/sourceforge/use_the_gmp.htm,v 1.2 2003/04/27 21:01:30 dtashley Exp $</font></p> |
210 |
<hr noshade size="5"> |
211 |
|
212 |
</body> |
213 |
|
214 |
</html> |