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

Contents 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 - (show 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 //$Header$
2 //********************************************************************************
3 //Copyright (c) 2003, 2018 David T. Ashley.
4 //********************************************************************************
5 //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 //
20 //The above copyright notice and this permission notice shall be included in all
21 //copies or substantial portions of the Software.
22 //
23 //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 //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