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 |
|
|
//******************************************************************************** |