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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 175 - (hide annotations) (download)
Mon Jul 9 00:00:34 2018 UTC (6 years, 4 months ago) by dashley
File MIME type: text/plain
File size: 7685 byte(s)
Update license (GPL->MIT) and copyright information.  Remove CVS log, which SVN does not support.
1 dashley 172 //$Header$
2     //********************************************************************************
3 dashley 175 //Copyright (c) 2003, 2018 David T. Ashley.
4 dashley 172 //********************************************************************************
5 dashley 175 //This file is part of "arith_large_cgi", a program that is designed to be
6     //invoked by a PHP script as part of serving a web page that performs
7     //calculations involving large integers. (A secondary compiled program is
8     //used because a compiled program can perform certain calculation-intensive
9     //tasks far more efficiently than a PHP script.) This program is provided by
10     //David T. Ashley (dashley@gmail.com) under the MIT License (reproduced
11     //immediately below).
12     //********************************************************************************
13     //Permission is hereby granted, free of charge, to any person obtaining a copy
14     //of this software and associated documentation files (the "Software"), to deal
15     //in the Software without restriction, including without limitation the rights
16     //to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17     //copies of the Software, and to permit persons to whom the Software is
18     //furnished to do so, subject to the following conditions:
19 dashley 172 //
20 dashley 175 //The above copyright notice and this permission notice shall be included in all
21     //copies or substantial portions of the Software.
22 dashley 172 //
23 dashley 175 //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24     //IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25     //FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26     //AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27     //LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28     //OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
29     //SOFTWARE.
30     //********************************************************************************
31 dashley 172 //This module is the GCD subfunction of a general-purpose CGI-BIN program to support
32     //number theory demonstration applications.
33     //
34     //INPUT PARAMETERS
35     //----------------
36     //The subfunction accepts two parameters, the integers whose GCD is to be
37     //calculated. There is substantial tolerance for invalid characters.
38     //Naturally, the integers should be positive.
39     //
40     //OUTPUT RESULTS
41     //--------------
42     //The notation below gives the outputs of the program. In some cases, [i] notation
43     //is used to indicate line numbers.
44     //
45     //[01] An overall success or failure code for the operation. Valid responses
46     // are:
47     // S : Success.
48     // EP1A : The first integer could not be parsed, which means it is ill-formatted.
49     // EP1B : The first integer was zero or negative.
50     // EP2A : The second integer could not be parsed, which means it is ill-formatted.
51     // EP2B : The second integer was zero or negative.
52     // EQ : Other or unspecified error.
53     //
54     //[02] The fully normalized first integer entered. This means it has been
55     // stripped of all weird characters, etc. This can be used by the
56     // PHP script to repopulate the form boxes.
57     //[03] The fully normalized second integer entered.
58     //
59     //In the event that the status code indicates error, no further lines
60     //will be written.
61     //
62     //[04] The round number of the application of Euclid's algorithm, starting
63     // at "1".
64     //[05] "a".
65     //[06] "b".
66     //[07] a div b.
67     //[08] a mod b.
68     //[09] ... repeating sequence, starting back at [4] and repeating until a
69     // zero remainder.
70     //[..] The GCD of the two integers. This will be positive and
71     // contain no commas or extraneous characters.
72     //[..] "S", indicating success.
73     //
74     //Note that as per the definition above, any valid non-error output from
75     //this program will contain a number of lines which is a multiple of 5.
76     //
77     //The return value (exit code) from this subfunction is always 0.
78     //
79    
80     #define MODULE_SUBFUNC_GCD
81    
82     #include <assert.h>
83     #include <ctype.h>
84     #include <stddef.h>
85     #include <stdio.h>
86     #include <stdlib.h>
87     #include <string.h>
88     #include <time.h>
89    
90     #include <gmp.h>
91    
92     #include "auxfuncs.h"
93     #include "subfunc_gcd.h"
94    
95     int SUBFUNC_GCD_main(int argc, char *argv[])
96     {
97     //Normalized first and second parameters (the integers).
98     char *arg1;
99     char *arg2;
100    
101     //GMP types to maintain the algorithm.
102     int round;
103     mpz_t alg_a, alg_b, alg_adivb, alg_amodb;
104    
105     //There must be an acceptable number of command-line arguments.
106     if (argc != 4)
107     {
108     printf("EQ\n0\n0\n");
109     return(0);
110     }
111    
112     //Copy the command-line arguments to a safe place where we can manipulate them.
113     //Leave 2 characters of space in case we assign a "0".
114     arg1 = (char *)malloc((AUXFUNCS_size_t_max(1, strlen(argv[2])) + 1) * sizeof(char));
115     arg2 = (char *)malloc((AUXFUNCS_size_t_max(1, strlen(argv[3])) + 1) * sizeof(char));
116     if ((arg1 == NULL) || (arg2 == NULL))
117     {
118     printf("EQ\n%s\n%s\n", argv[2], argv[3]);
119     exit(0);
120     }
121     strcpy(arg1, argv[2]);
122     strcpy(arg2, argv[3]);
123    
124     //Strip all of the non-digit trash out of the arguments.
125     AUXFUNCS_remove_non_digits(arg1);
126     AUXFUNCS_remove_non_digits(arg2);
127    
128     //Remove all leading zeros from both arguments.
129     AUXFUNCS_remove_leading_zeros(arg1);
130     AUXFUNCS_remove_leading_zeros(arg2);
131    
132     //If either argument is zero length, fill it in with 0.
133     if (!strlen(arg1))
134     strcpy(arg1, "0");
135     if (!strlen(arg2))
136     strcpy(arg2, "0");
137    
138     //If either argument exceeds 1000 digits, abort.
139     if ((strlen(arg1)>1000) || (strlen(arg2) > 1000))
140     {
141     printf("EQ\n0\n0\n");
142     return(0);
143     }
144    
145     //If either argument is zero, abort.
146     if (!strcmp(arg1, "0"))
147     {
148     printf("EP1B\n0\n0\n");
149     return(0);
150     }
151     if (!strcmp(arg2, "0"))
152     {
153     printf("EP2B\n0\n0\n");
154     return(0);
155     }
156    
157     //Initialize all of the GMP variables.
158     mpz_init(alg_a);
159     mpz_init(alg_b);
160     mpz_init(alg_adivb);
161     mpz_init(alg_amodb);
162    
163     //Assign a and b to initial values.
164     mpz_set_str(alg_a, arg1, 10);
165     mpz_set_str(alg_b, arg2, 10);
166    
167     //We assume at this point that we will be successful. Output
168     //the header stuff.
169     printf("S\n");
170     mpz_out_str(stdout, 10, alg_a);
171     printf("\n");
172     mpz_out_str(stdout, 10, alg_b);
173     printf("\n");
174    
175     //We require as an initial condition that a >= b. Make
176     //that happen.
177     if (mpz_cmp(alg_a, alg_b) < 0)
178     {
179     mpz_swap(alg_a, alg_b);
180     }
181    
182     //To make the algorithm cleaner, we preload for the first
183     //assignment.
184     mpz_set(alg_amodb, alg_b);
185     mpz_set(alg_b, alg_a);
186    
187     //Now begin the algorithm proper.
188     round = 0;
189     do
190     {
191     //We are at next round.
192     round++;
193    
194     //Values for this round inherited from the last one.
195     mpz_set(alg_a, alg_b);
196     mpz_set(alg_b, alg_amodb);
197    
198     //Calculate the quotient and remainder.
199     mpz_fdiv_qr(alg_adivb, alg_amodb, alg_a, alg_b);
200    
201     //Output all the data from the round.
202     printf("%d\n", round);
203     mpz_out_str(stdout, 10, alg_a);
204     printf("\n");
205     mpz_out_str(stdout, 10, alg_b);
206     printf("\n");
207     mpz_out_str(stdout, 10, alg_adivb);
208     printf("\n");
209     mpz_out_str(stdout, 10, alg_amodb);
210     printf("\n");
211     }
212     while((round < 2000) && (mpz_sgn(alg_amodb) > 0));
213    
214     //The GCD canonically will be the last non-zero remainder.
215     mpz_out_str(stdout, 10, alg_b);
216     printf("\n");
217    
218     //Finally, we output the trailing "S".
219     printf("S\n");
220    
221     return(0);
222     }
223    
224     //********************************************************************************
225     // End of SUBFUNC_GCD.C.
226     //********************************************************************************

Properties

Name Value
svn:eol-style native
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25