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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 29 - (hide annotations) (download)
Sat Oct 8 07:08:47 2016 UTC (8 years, 1 month ago) by dashley
File MIME type: text/plain
File size: 7703 byte(s)
Directories relocated.
1 dashley 27 //$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