howtos/sourceforge/use_the_gmp.htm

<html>

<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>How To Use The GMP And Perform Large Integer Or High-Precision Arithmetic
On SourceForge Web Sites</title>
<base target="main">
</head>

<body background="../../bkgnds/bk10.gif">

<p align="center"><b><font size="4">How To Use The <a href="http://www.swox.com/gmp"> GMP</a> And Perform Large Integer
Or High-Precision Arithmetic On <a href="http://www.sourceforge.net"> SourceForge</a> Web Sites</font></b></p>
<hr>
<p><b>04/15/03:</b>&nbsp; I (Dave Ashley) have several number theory CGI pages
here at <a href="http://www.sourceforge.net">SourceForge</a>.&nbsp; These pages
do things like calculate the GCD of two integers, find best rational
approximations, etc.; and they do need arbitrarily large integer capability to
be useful.&nbsp; It was quite difficult to obtain large integer capability for
these pages.&nbsp; Here are the steps I went through, and the eventual solution
(in the hopes that it helps others).</p>
<ul>
  <li>I had used the <i>bcmath</i> library with PHP before (it is built into the
    version of PHP I have on my Linux box at home).&nbsp; Unfortunately, I
    discovered immediately that the version of PHP used by <i>SourceForge</i>
    does not have <i>bcmath</i> built in.</li>
  <li>I tried writing arbitrary integer functions using PHP.&nbsp; These proved
    to be painfully inefficient.&nbsp; I abandoned the effort when early
    observations indicated that these probably would not allow calculation of a
    couple hundred rounds of <a href="../../phpcgibin/euclid_gcd.php">Euclid's
    GCD algorithm</a> in a practical time (not too long for a user to wait, and
    within the CPU time limits for a PHP script).</li>
  <li>I tried writing a separate program in 'C' to do the calculations using the
    <a href="http://www.swox.com/gmp">GMP library</a>, and tried calling this
    program from the PHP script using the <i>exec()</i> function.&nbsp; This
    worked famously at home, but did not work at <i>SourceForge</i>.&nbsp; The
    behavior at <i>SourceForge</i> was a mystery because using a shell I could
    invoke the program successfully, but PHP could not invoke it.</li>
  <li>I completed a <i>SourceForge</i> support ticket.&nbsp; The response to the
    ticket indicated that:
    <ul>
      <li>The GMP is installed on the shell servers but not the web servers,
        which is why I could run the compiled external program from a shell but
        not from PHP.</li>
      <li>The solution is to compile the GMP library, place it in the <i>SourceForge</i>
        web space, and link to it.</li>
    </ul>
  </li>
  <li>After much experimentation, I discovered that I could not figure out how
    to place another copy of the GMP library in the web space at SourceForge and
    link to it.&nbsp; As best I could glean, there are security implications to
    replacing libraries (perhaps one could trick a program into dynamically
    linking with the a trojan library), and so dynamically linked libraries
    could only exist in certain locations (all paths which belong to <i>root</i>).</li>
  <li>However, I also discovered that I could statically link my program with
    the GMP (which gives a much larger executable), and place that much larger
    executable on <i>SourceForge</i> and run it.&nbsp; The executable went from
    about 20K to 500K when static linking was specified.</li>
</ul>
<p>All that being said, here are the specific steps I took to use the GMP from
PHP:</p>
<ul>
  <li>Be sure that the GMP is installed on your system (the one you are using
    for compiling).&nbsp; You need both the library and the development
    files.&nbsp; Here is what shows on my system at home:<br>
    <br>
    <font face="Courier">[apache@khinchin apache]$ rpm -q -a | grep gmp<br>
    gmp-4.0.1-3<br>
    gmp-devel-4.0.1-3</font><br>
    <br>
    Note that both GMP and GMP-devel are installed.<br>
    <br>
    On a <a href="http://www.redhat.com">RedHat</a> system, you can use <font face="Courier">rpm</font>
    to install the packages.&nbsp; On other systems, you may need to install
    differently or compile and install them from source.</li>
  <li>Because static linking bloats the executable, the sanest approach (and the
    one I use) is to write <i>one</i> executable and have it do all the number
    crunching for all of your PHP scripts.&nbsp; (By writing one executable, the
    GMP library is present in only one place--that one executable.)&nbsp; The
    executable I wrote accepts a subfunction code, which is essentially an
    indication of which PHP script is calling it.&nbsp; Thus, my single
    executable does GCD calculation, best rational approximations, Miller-Rabin
    testing, etc., depending on the command-line parameters (which are
    controlled by the calling PHP script).<br>
    <br>
    For example, when the GCD PHP script calls the executable, it uses the
    subfunction code &quot;gcd&quot; and gets output like this (when finding the
    GCD of 27 and 150):<br>
    <br>
    <font face="Courier" size="2">[apache@khinchin phpcgibin]$ ./arith_large_cgi gcd 27 150<br>
    S<br>
    27<br>
    150<br>
    1<br>
    150<br>
    27<br>
    5<br>
    15<br>
    2<br>
    27<br>
    15<br>
    1<br>
    12<br>
    3<br>
    15<br>
    12<br>
    1<br>
    3<br>
    4<br>
    12<br>
    3<br>
    4<br>
    0<br>
    3<br>
    S<br>
    </font><br>
    On the other hand, when doing Miller-Rabin testing to see if a certain
    number is prime (101, for example), the single executable is called like
    this and produces this output:<br>
    <br>
    <font face="Courier" size="2">[apache@khinchin phpcgibin]$ ./arith_large_cgi gmp_prob_prime
    101 25<br>
    S<br>
    101<br>
    25<br>
    2<br>
    S<br>
    </font><br>
    In the first example above, the numbers which are emitted by the program are
    data from successive rounds of Euclid's GCD algorithm (which the PHP script
    formats and displays).&nbsp; In the second case, the output is,
    respectively, the number whose primality is to be determined (an echo back),
    the number of rounds of Miller-Rabin testing (again, and echo-back), and
    finally a code to indicate the testing results (0 = a compsite number, 1 =
    probably a prime number, and 2 = definitely a prime number).&nbsp; The
    output of the program is meant to be interpreted by the calling PHP script
    (i.e. it is not human-friendly).<br>
    <br>
    Also note that the first and last lines of the output are
    &quot;S&quot;.&nbsp; This prevents the calling PHP script from assuming all
    output is present if the program coredumps or somehow terminates.&nbsp; The
    calling PHP script checks the number of lines and also checks for the
    starting and ending &quot;S&quot; characters.</li>
  <li>Accomplishing static linking is a little bit tricky.&nbsp; Here are the
    conditions that need to be met:
    <ul>
      <li>The static GMP library has to be on the system you use for compilation
        (it is by default).&nbsp; If it is not present, you may need to compile
        and install the GMP from source code.</li>
      <li>When calling the <i>gcc</i> compiler,&nbsp; the <font face="Courier">-static</font>
        switch can be anywhere, but the <b><font face="Courier">-lgmp</font>
        switch must be near the end of the command line, after the modules that
        reference the GMP</b>.&nbsp; This is because <i>gcc</i> links from left
        to right.&nbsp; For example, my program is built like this:<br>
        <br>
        <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>
        <br>
        Notice that the <font face="Courier">-lgmp</font> switch is at the end
        of the command line.</li>
    </ul>
  </li>
  <li>The executable can be placed in the same directory as the PHP scripts (it
    will always find it there).</li>
  <li>The PHP <i>exec()</i> function is well-documented.&nbsp; You can give it a
    variable in which it will store the output of the called program in an
    array.&nbsp; For example, from one of my PHP scripts, here is the code which
    calls <i>exec()</i> and also checks the output for sanity.<br>
    <br>
    <font face="Courier" size="2">   //We can now run the external program to do the calculation.<br>
   $cgi_command_string = "./arith_large_cgi gcd " . $N1 . " " . $N2;<br>
    <br>
    exec($cgi_command_string, $cgi_result);<br>
    $cgi_result_nelem = count($cgi_result);<br>
    <br>
   //We need to perform some sanity checks on the CGI output to be sure it<br>
   //is what we want.  If it seems wrong, we need to generate an error message<br>
   //and not try to display the output.<br>
   $cgi_output_is_sane = 1;<br>
   if ($cgi_result_nelem == 0)<br>
    &nbsp;&nbsp; $cgi_output_is_sane = 0;<br>
   if ($cgi_result_nelem > 0)<br>
    &nbsp;&nbsp; {<br>
    &nbsp;&nbsp; if (($cgi_result_nelem % 5) != 0)<br>
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $cgi_output_is_sane = 0;<br>
    &nbsp;&nbsp; if ($cgi_result[0] != "S")<br>
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $cgi_output_is_sane = 0;<br>
    &nbsp;&nbsp; if ($cgi_result[$cgi_result_nelem - 1] != "S")<br>
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $cgi_output_is_sane = 0;<br>
    &nbsp;&nbsp; }<br>
    <br>
   if (!$cgi_output_is_sane)<br>
    &nbsp;&nbsp; {<br>
    &nbsp;&nbsp; do_err_msg("An unspecified error occurred when ...<br>
    </font><br>
    Notice how the snippet above checks the output of the program for sanity.</li>
  <li>Finally, you must have the execute permission for <i>other</i> (the web
    server is <i>other</i>) set in your compiled executable, or else PHP cannot
    run the compiled program.&nbsp; You can change these permissions with the <i>chmod</i>
    command.</li>
</ul>
<p align="left">Please drop <a href="mailto:dtashley@users.sourceforge.net">me</a>
an e-mail if I should change or enhance this documentation or if there is a
better way to do something.</p>
<hr>
<p align="center" style="margin-top: -2; margin-bottom: -1"><font size="1">This
web page is maintained by <a href="mailto:dtashley@users.sourceforge.net">David
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>
<hr noshade size="5">

</body>

</html>
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>