/[dtapublic]/projs/dtats/trunk/projs/2018/20180707_cgi_web_tools_aux_exe/subfunc_gcd.c
ViewVC logotype

Diff of /projs/dtats/trunk/projs/2018/20180707_cgi_web_tools_aux_exe/subfunc_gcd.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

Legend:
Removed from v.171  
changed lines
  Added in v.172

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25