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

Annotation 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 - (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: 5735 byte(s)
Update license (GPL->MIT) and copyright information.  Remove CVS log, which SVN does not support.
1 dashley 172 //$Header$
2 dashley 175 //********************************************************************************
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 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     //
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 dashley 172 //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 dashley 175 //End of file SIEVE_GEN.C
179 dashley 172 //******************************************************************************************************

Properties

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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25