/[dtapublic]/to_be_filed/sf_code/esrgnxpj/sfnthcgi0304/subfunc_gcd.c
ViewVC logotype

Contents of /to_be_filed/sf_code/esrgnxpj/sfnthcgi0304/subfunc_gcd.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 29 - (show annotations) (download)
Sat Oct 8 07:08:47 2016 UTC (7 years, 9 months ago) by dashley
File MIME type: text/plain
File size: 7703 byte(s)
Directories relocated.
1 //$Header: /cvsroot/esrg/sfesrg/esrgnxpj/sfnthcgi0304/subfunc_gcd.c,v 1.5 2003/07/01 03:46:58 dtashley Exp $
2 //
3 //********************************************************************************
4 //Copyright (C) 2003 David T. Ashley
5 //********************************************************************************
6 //This program or source file is free software; you can redistribute it and/or
7 //modify it under the terms of the GNU General Public License as published by
8 //the Free Software Foundation; either version 2 of the License, or (at your
9 //option) any later version.
10 //
11 //This program or source file is distributed in the hope that it will
12 //be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
13 //MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 //GNU General Public License for more details.
15 //
16 //You may have received a copy of the GNU General Public License
17 //along with this program; if not, write to the Free Software
18 //Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 //
20 //This module is the GCD subfunction of a general-purpose CGI-BIN program to support
21 //number theory demonstration applications.
22 //
23 //INPUT PARAMETERS
24 //----------------
25 //The subfunction accepts two parameters, the integers whose GCD is to be
26 //calculated. There is substantial tolerance for invalid characters.
27 //Naturally, the integers should be positive.
28 //
29 //OUTPUT RESULTS
30 //--------------
31 //The notation below gives the outputs of the program. In some cases, [i] notation
32 //is used to indicate line numbers.
33 //
34 //[01] An overall success or failure code for the operation. Valid responses
35 // are:
36 // S : Success.
37 // EP1A : The first integer could not be parsed, which means it is ill-formatted.
38 // EP1B : The first integer was zero or negative.
39 // EP2A : The second integer could not be parsed, which means it is ill-formatted.
40 // EP2B : The second integer was zero or negative.
41 // EQ : Other or unspecified error.
42 //
43 //[02] The fully normalized first integer entered. This means it has been
44 // stripped of all weird characters, etc. This can be used by the
45 // PHP script to repopulate the form boxes.
46 //[03] The fully normalized second integer entered.
47 //
48 //In the event that the status code indicates error, no further lines
49 //will be written.
50 //
51 //[04] The round number of the application of Euclid's algorithm, starting
52 // at "1".
53 //[05] "a".
54 //[06] "b".
55 //[07] a div b.
56 //[08] a mod b.
57 //[09] ... repeating sequence, starting back at [4] and repeating until a
58 // zero remainder.
59 //[..] The GCD of the two integers. This will be positive and
60 // contain no commas or extraneous characters.
61 //[..] "S", indicating success.
62 //
63 //Note that as per the definition above, any valid non-error output from
64 //this program will contain a number of lines which is a multiple of 5.
65 //
66 //The return value (exit code) from this subfunction is always 0.
67 //
68
69 #define MODULE_SUBFUNC_GCD
70
71 #include <assert.h>
72 #include <ctype.h>
73 #include <stddef.h>
74 #include <stdio.h>
75 #include <stdlib.h>
76 #include <string.h>
77 #include <time.h>
78
79 #include <gmp.h>
80
81 #include "auxfuncs.h"
82 #include "subfunc_gcd.h"
83
84 int SUBFUNC_GCD_main(int argc, char *argv[])
85 {
86 //Normalized first and second parameters (the integers).
87 char *arg1;
88 char *arg2;
89
90 //GMP types to maintain the algorithm.
91 int round;
92 mpz_t alg_a, alg_b, alg_adivb, alg_amodb;
93
94 //There must be an acceptable number of command-line arguments.
95 if (argc != 4)
96 {
97 printf("EQ\n0\n0\n");
98 return(0);
99 }
100
101 //Copy the command-line arguments to a safe place where we can manipulate them.
102 //Leave 2 characters of space in case we assign a "0".
103 arg1 = (char *)malloc((AUXFUNCS_size_t_max(1, strlen(argv[2])) + 1) * sizeof(char));
104 arg2 = (char *)malloc((AUXFUNCS_size_t_max(1, strlen(argv[3])) + 1) * sizeof(char));
105 if ((arg1 == NULL) || (arg2 == NULL))
106 {
107 printf("EQ\n%s\n%s\n", argv[2], argv[3]);
108 exit(0);
109 }
110 strcpy(arg1, argv[2]);
111 strcpy(arg2, argv[3]);
112
113 //Strip all of the non-digit trash out of the arguments.
114 AUXFUNCS_remove_non_digits(arg1);
115 AUXFUNCS_remove_non_digits(arg2);
116
117 //Remove all leading zeros from both arguments.
118 AUXFUNCS_remove_leading_zeros(arg1);
119 AUXFUNCS_remove_leading_zeros(arg2);
120
121 //If either argument is zero length, fill it in with 0.
122 if (!strlen(arg1))
123 strcpy(arg1, "0");
124 if (!strlen(arg2))
125 strcpy(arg2, "0");
126
127 //If either argument exceeds 1000 digits, abort.
128 if ((strlen(arg1)>1000) || (strlen(arg2) > 1000))
129 {
130 printf("EQ\n0\n0\n");
131 return(0);
132 }
133
134 //If either argument is zero, abort.
135 if (!strcmp(arg1, "0"))
136 {
137 printf("EP1B\n0\n0\n");
138 return(0);
139 }
140 if (!strcmp(arg2, "0"))
141 {
142 printf("EP2B\n0\n0\n");
143 return(0);
144 }
145
146 //Initialize all of the GMP variables.
147 mpz_init(alg_a);
148 mpz_init(alg_b);
149 mpz_init(alg_adivb);
150 mpz_init(alg_amodb);
151
152 //Assign a and b to initial values.
153 mpz_set_str(alg_a, arg1, 10);
154 mpz_set_str(alg_b, arg2, 10);
155
156 //We assume at this point that we will be successful. Output
157 //the header stuff.
158 printf("S\n");
159 mpz_out_str(stdout, 10, alg_a);
160 printf("\n");
161 mpz_out_str(stdout, 10, alg_b);
162 printf("\n");
163
164 //We require as an initial condition that a >= b. Make
165 //that happen.
166 if (mpz_cmp(alg_a, alg_b) < 0)
167 {
168 mpz_swap(alg_a, alg_b);
169 }
170
171 //To make the algorithm cleaner, we preload for the first
172 //assignment.
173 mpz_set(alg_amodb, alg_b);
174 mpz_set(alg_b, alg_a);
175
176 //Now begin the algorithm proper.
177 round = 0;
178 do
179 {
180 //We are at next round.
181 round++;
182
183 //Values for this round inherited from the last one.
184 mpz_set(alg_a, alg_b);
185 mpz_set(alg_b, alg_amodb);
186
187 //Calculate the quotient and remainder.
188 mpz_fdiv_qr(alg_adivb, alg_amodb, alg_a, alg_b);
189
190 //Output all the data from the round.
191 printf("%d\n", round);
192 mpz_out_str(stdout, 10, alg_a);
193 printf("\n");
194 mpz_out_str(stdout, 10, alg_b);
195 printf("\n");
196 mpz_out_str(stdout, 10, alg_adivb);
197 printf("\n");
198 mpz_out_str(stdout, 10, alg_amodb);
199 printf("\n");
200 }
201 while((round < 2000) && (mpz_sgn(alg_amodb) > 0));
202
203 //The GCD canonically will be the last non-zero remainder.
204 mpz_out_str(stdout, 10, alg_b);
205 printf("\n");
206
207 //Finally, we output the trailing "S".
208 printf("S\n");
209
210 return(0);
211 }
212
213 //********************************************************************************
214 // $Log: subfunc_gcd.c,v $
215 // Revision 1.5 2003/07/01 03:46:58 dtashley
216 // Edits towards working continued fraction best rational approximation
217 // functionality.
218 //
219 // Revision 1.4 2003/04/17 20:02:05 dtashley
220 // License text for the GPL added. All source files are now under the GPL,
221 // after some discussion on the GMP list.
222 //
223 // Revision 1.3 2003/04/14 23:27:01 dtashley
224 // Subfunction GMP_PROB_PRIME finished.
225 //
226 // Revision 1.2 2003/04/14 02:55:25 dtashley
227 // Final edits on GCD.
228 //
229 // Revision 1.1 2003/04/13 23:46:06 dtashley
230 // Initial checkin.
231 //********************************************************************************
232 // End of SUBFUNC_GCD.C.
233 //********************************************************************************

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25