1 |
dashley |
27 |
//$Header: /cvsroot/esrg/sfesrg/esrgnxpj/sfnthcgi0304/arith_large_cgi.c,v 1.6 2003/07/01 03:46:58 dtashley Exp $
|
2 |
|
|
//********************************************************************************
|
3 |
|
|
//This source file is the main function of a program to support number theory
|
4 |
|
|
//web pages.
|
5 |
|
|
//********************************************************************************
|
6 |
|
|
//Copyright (C) 2003 David T. Ashley
|
7 |
|
|
//********************************************************************************
|
8 |
|
|
//This program is free software; you can redistribute it and/or modify
|
9 |
|
|
//it under the terms of the GNU General Public License as published by
|
10 |
|
|
//the Free Software Foundation; either version 2 of the License, or
|
11 |
|
|
//(at your option) any later version.
|
12 |
|
|
//
|
13 |
|
|
//This program or source file is distributed in the hope that it will
|
14 |
|
|
//be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
|
15 |
|
|
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
16 |
|
|
//GNU General Public License for more details.
|
17 |
|
|
//
|
18 |
|
|
//You may have received a copy of the GNU General Public License
|
19 |
|
|
//along with this program; if not, write to the Free Software
|
20 |
|
|
//Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
21 |
|
|
//********************************************************************************
|
22 |
|
|
//This program is written exclusively to support a PHP script which must calculate and
|
23 |
|
|
//display a number of number theory results. The necessity of this script
|
24 |
|
|
//(rather than using BCMATH) comes about because SourceForge does not have
|
25 |
|
|
//bcmath installed on its PHP system.
|
26 |
|
|
//
|
27 |
|
|
//This program is meant to be called by the PHP script using the exec()
|
28 |
|
|
//call, but could also be run by hand (and in fact this method is used for testing).
|
29 |
|
|
//
|
30 |
|
|
//The first parameter after the program name is the suboperation to be performed
|
31 |
|
|
//(each CGI page probably uses a different suboperation). This program
|
32 |
|
|
//will return a non-zero exit code only if there is a missing or unrecognized
|
33 |
|
|
//suboperation. Otherwise, error reporting is controlled by the rules of the
|
34 |
|
|
//suboperation.
|
35 |
|
|
//
|
36 |
|
|
//The currently defined suboperations are:
|
37 |
|
|
//
|
38 |
|
|
// a)"help"
|
39 |
|
|
// Display information about what the program is and how to use
|
40 |
|
|
// it.
|
41 |
|
|
// b)"gcd"
|
42 |
|
|
// Calculate the gcd of two integers using Euclid's classic
|
43 |
|
|
// algorithm and also display the intermediate results.
|
44 |
|
|
// c)"gmp_prob_prime"
|
45 |
|
|
// Use Miller-Rabin to determine to high certainty whther a
|
46 |
|
|
// number is prime or composite.
|
47 |
|
|
// d)"pfact_18"
|
48 |
|
|
// Attempt to factor a number of 18 decimal digits or less into
|
49 |
|
|
// component primes.
|
50 |
|
|
// e)"cfbrap"
|
51 |
|
|
// Finds the best rational approximation to a rational number subject
|
52 |
|
|
// to constraints on the denominator and numerator using continued
|
53 |
|
|
// fraction techniques.
|
54 |
|
|
|
55 |
|
|
#include <stdio.h>
|
56 |
|
|
#include <stdlib.h>
|
57 |
|
|
#include <string.h>
|
58 |
|
|
|
59 |
|
|
#include "auxfuncs.h"
|
60 |
|
|
#include "subfunc_cfbrap.h"
|
61 |
|
|
#include "subfunc_gcd.h"
|
62 |
|
|
#include "subfunc_gmp_prob_prime.h"
|
63 |
|
|
#include "subfunc_pfact_18.h"
|
64 |
|
|
|
65 |
|
|
//Single function prototype needed for a forward reference.
|
66 |
|
|
static void dump_subfunction_choices(int indent);
|
67 |
|
|
|
68 |
|
|
//Implements the help.
|
69 |
|
|
int SUBFUNC_HELP_main(int argc, char *argv[])
|
70 |
|
|
{
|
71 |
|
|
int i;
|
72 |
|
|
char *help[] =
|
73 |
|
|
{
|
74 |
|
|
"This program is a compiled 'C'-language program designed to be called from a",
|
75 |
|
|
"PHP script to assist in calculating number theory and large integer",
|
76 |
|
|
"arithmetic results. This scheme (of having a separate executable like this",
|
77 |
|
|
"one) was used with SourceForge web content because SourceForge did not have",
|
78 |
|
|
"the bcmath library compiled into PHP, and it was determined experimentally",
|
79 |
|
|
"that writing large integer arithmetic functions in PHP directly resulted in",
|
80 |
|
|
"unusably slow performance. This program makes use of the GMP library, which",
|
81 |
|
|
"gives it superior performance.",
|
82 |
|
|
"",
|
83 |
|
|
"This program can of course be invoked from a shell or from another scripting",
|
84 |
|
|
"language besides PHP. It is designed, however, for execution from a",
|
85 |
|
|
"scripting language, as you might guess from the human-unfriendly output.",
|
86 |
|
|
"",
|
87 |
|
|
"Please contact Dave Ashley (dtashley@aol.com) with any questions or",
|
88 |
|
|
"concerns.",
|
89 |
|
|
"",
|
90 |
|
|
"Dave Ashley, Detroit, Michigan, USA, April, 2003.",
|
91 |
|
|
"",
|
92 |
|
|
"The available subfunction choices (the first parameter on the command",
|
93 |
|
|
"line) are:",
|
94 |
|
|
};
|
95 |
|
|
|
96 |
|
|
for (i=0; i<sizeof(help)/sizeof(help[0]); i++)
|
97 |
|
|
printf("%s\n", help[i]);
|
98 |
|
|
dump_subfunction_choices(3);
|
99 |
|
|
}
|
100 |
|
|
|
101 |
|
|
//Structure type used to hold the jump table of different functions
|
102 |
|
|
//to handle different subcommands.
|
103 |
|
|
struct struct_ARITH_LARGE_CGI_subcmd_jmp
|
104 |
|
|
{
|
105 |
|
|
char *subfunc_string;
|
106 |
|
|
int (*subfunc_ptr)(int argc, char *argv[]);
|
107 |
|
|
};
|
108 |
|
|
|
109 |
|
|
//The jump table. The last element is defined to have both a
|
110 |
|
|
//NULL string pointer and a NULL function pointer.
|
111 |
|
|
static struct struct_ARITH_LARGE_CGI_subcmd_jmp subcmd_jump_tbl[] =
|
112 |
|
|
{
|
113 |
|
|
{"cfbrap", SUBFUNC_CFBRAP_main },
|
114 |
|
|
{"gcd", SUBFUNC_GCD_main },
|
115 |
|
|
{"gmp_prob_prime", SUBFUNC_GMP_PROB_PRIME_main },
|
116 |
|
|
{"pfact_18", SUBFUNC_PFACT_18_main },
|
117 |
|
|
{"help", SUBFUNC_HELP_main },
|
118 |
|
|
{NULL, NULL }
|
119 |
|
|
};
|
120 |
|
|
|
121 |
|
|
//Dumps the available choices for the subfunction code to the
|
122 |
|
|
//standard output, each indented by "indent" characters.
|
123 |
|
|
static void dump_subfunction_choices(int indent)
|
124 |
|
|
{
|
125 |
|
|
int i, j;
|
126 |
|
|
|
127 |
|
|
for (i=0; subcmd_jump_tbl[i].subfunc_string != NULL; i++)
|
128 |
|
|
{
|
129 |
|
|
for (j=0; j<indent; j++)
|
130 |
|
|
printf(" ");
|
131 |
|
|
printf("%s\n", subcmd_jump_tbl[i].subfunc_string);
|
132 |
|
|
}
|
133 |
|
|
}
|
134 |
|
|
|
135 |
|
|
|
136 |
|
|
int main(int argc, char *argv[])
|
137 |
|
|
{
|
138 |
|
|
int i;
|
139 |
|
|
int rv;
|
140 |
|
|
|
141 |
|
|
if (argc < 2)
|
142 |
|
|
{
|
143 |
|
|
printf("Missing subfunction code. Choices are:\n");
|
144 |
|
|
dump_subfunction_choices(3);
|
145 |
|
|
exit(4);
|
146 |
|
|
}
|
147 |
|
|
|
148 |
|
|
for (i=0; subcmd_jump_tbl[i].subfunc_string != NULL; i++)
|
149 |
|
|
{
|
150 |
|
|
if (!strcmp(argv[1], subcmd_jump_tbl[i].subfunc_string))
|
151 |
|
|
{
|
152 |
|
|
rv = (subcmd_jump_tbl[i].subfunc_ptr)(argc, argv);
|
153 |
|
|
goto normal_return;
|
154 |
|
|
}
|
155 |
|
|
}
|
156 |
|
|
|
157 |
|
|
printf("Invalid subfunction code. Choices are:\n");
|
158 |
|
|
dump_subfunction_choices(3);
|
159 |
|
|
exit(4);
|
160 |
|
|
|
161 |
|
|
normal_return:
|
162 |
|
|
exit(rv);
|
163 |
|
|
}
|
164 |
|
|
|
165 |
|
|
//********************************************************************************
|
166 |
|
|
//$Log: arith_large_cgi.c,v $
|
167 |
|
|
//Revision 1.6 2003/07/01 03:46:58 dtashley
|
168 |
|
|
//Edits towards working continued fraction best rational approximation
|
169 |
|
|
//functionality.
|
170 |
|
|
//
|
171 |
|
|
//Revision 1.5 2003/06/29 22:51:49 dtashley
|
172 |
|
|
//Edits toward CF best approximation functionality.
|
173 |
|
|
//
|
174 |
|
|
//Revision 1.4 2003/04/17 20:02:05 dtashley
|
175 |
|
|
//License text for the GPL added. All source files are now under the GPL,
|
176 |
|
|
//after some discussion on the GMP list.
|
177 |
|
|
//
|
178 |
|
|
//Revision 1.3 2003/04/15 23:55:43 dtashley
|
179 |
|
|
//SUBFUNC_PFACT_18 added.
|
180 |
|
|
//
|
181 |
|
|
//Revision 1.2 2003/04/14 23:27:01 dtashley
|
182 |
|
|
//Subfunction GMP_PROB_PRIME finished.
|
183 |
|
|
//
|
184 |
|
|
//Revision 1.1 2003/04/14 20:38:40 dtashley
|
185 |
|
|
//Initial checkin.
|
186 |
|
|
//********************************************************************************
|
187 |
|
|
//End of file ARITH_LARGE_CGI.C.
|
188 |
|
|
//********************************************************************************
|