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

Contents of /projs/dtats/trunk/projs/2018/20180707_cgi_web_tools_aux_exe/sieve_gen.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 175 - (show annotations) (download)
Mon Jul 9 00:00:34 2018 UTC (6 years ago) by dashley
File MIME type: text/plain
File size: 5735 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 //
32 //Sieve of Eratosthenes Table Generation
33 //--------------------------------------
34 //This utility generates a sieve table used in trial division prime number factorization.
35 //The table is a table of differentials to be added to trial divisors.
36 //--------------------------------------------------------------------------------
37 #include <stdio.h>
38
39 #define NAMING_PREFIX "SUBFUNC_PFACT_"
40 #define SIEVE_SIZE (2310) /* 2 * 3 * 5 * 7 * 11 */
41
42 unsigned int pfacts[] = {2, 3, 5, 7, 11};
43 unsigned int sieve_table_a[SIEVE_SIZE];
44 char *output_header[] =
45 {
46 "//This file is an automatically-generated sieve table, generated by the",
47 "//program \"sieve_gen.c\".",
48 "//",
49 NULL
50 };
51 char *output_footer[] =
52 {
53 "//",
54 "//End of automatically-generated file.",
55 NULL
56 };
57
58
59 int main(int argc, char *argv[])
60 {
61 int i, j;
62 unsigned p, q;
63 unsigned current_factor;
64 char **cptr;
65
66 //Initialize the sieve table. */
67 for (i=0; i < SIEVE_SIZE; i++)
68 {
69 sieve_table_a[i] = 1;
70 }
71
72 /* For each prime component, mark off all multiples. */
73 for (i=0; i<sizeof(pfacts)/sizeof(pfacts[0]); i++)
74 {
75 current_factor = pfacts[i];
76
77 p = 0;
78 while (p < SIEVE_SIZE)
79 {
80 sieve_table_a[p] = 0;
81 p += current_factor;
82 }
83 }
84
85 //Output the header.
86 cptr = output_header;
87 while (*cptr)
88 {
89 printf("%s\n", *cptr);
90 cptr++;
91 }
92
93 //Convert the table of multiples into a table of differentials. Each non-zero
94 //entry will be replaced by the distance to the next entry.
95 for (i=0; i < SIEVE_SIZE; i++)
96 {
97 if (sieve_table_a[i])
98 {
99 p = (i+1) % SIEVE_SIZE;
100 while (sieve_table_a[p] == 0)
101 {
102 sieve_table_a[i]++;
103 p = (p+1) % SIEVE_SIZE;
104 }
105 }
106 }
107
108 //Print out the table of differentials for reference. Each entry will
109 //be annotated with the prime factors that divide it.
110 printf("//\n");
111 printf("//For reference, below is the uncompressed table of differentials. Each table\n");
112 printf("//entry is annotated with the prime factors that divide it, if any.\n");
113 printf("//\n");
114 for (i=0; i < SIEVE_SIZE; i++)
115 {
116 printf("// sieve_table[%5d]: %3d (", i, sieve_table_a[i]);
117 q = 0;
118 for (j=0; j<sizeof(pfacts)/sizeof(pfacts[0]); j++)
119 {
120 if ((i % pfacts[j]) == 0)
121 {
122 printf("[%d]", pfacts[j]);
123 q = 1;
124 }
125 }
126 if (!q)
127 printf("NONE");
128 printf(")\n");
129 }
130 printf("//\n");
131
132 //Now we compress the table and output the code proper.
133 printf("#define %sN_SIEVE_FACTORS (%d)\n", NAMING_PREFIX, sizeof(pfacts)/sizeof(pfacts[0]));
134 printf("unsigned %ssieve_factors[] = {", NAMING_PREFIX);
135 for (i=0; i<sizeof(pfacts)/sizeof(pfacts[0]); i++)
136 {
137 printf("%d", pfacts[i]);
138 if (i != (sizeof(pfacts)/sizeof(pfacts[0]) - 1))
139 printf(",");
140 }
141
142 printf("}\n");
143 printf("//\n");
144 q = 0;
145 for (i=0; i < SIEVE_SIZE; i++)
146 if (sieve_table_a[i])
147 q++;
148 printf("#define %sN_SIEVE (%u)\n", NAMING_PREFIX, j);
149 printf("unsigned %ssieve[] = {\n", NAMING_PREFIX);
150 j = 0;
151 for (i=0; i < SIEVE_SIZE; i++)
152 {
153 if (sieve_table_a[i])
154 {
155 printf(" %3d", sieve_table_a[i]);
156 if (j==q)
157 printf(" ");
158 else
159 printf(",");
160 printf(" /* [%5d] (was [%d]) */\n", j, i);
161 j++;
162 }
163 }
164 printf(" };\n");
165
166 //Output the footer.
167 cptr = output_footer;
168 while (*cptr)
169 {
170 printf("%s\n", *cptr);
171 cptr++;
172 }
173
174 return(0);
175 }
176
177 //******************************************************************************************************
178 //End of file SIEVE_GEN.C
179 //******************************************************************************************************

Properties

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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25