summaryrefslogtreecommitdiff
path: root/web/c_cpp/cnoweb/pf.c
blob: 5fb0af98de7efec6a6ae0efd91a5ff5672496413 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
/*
      pf.c in c-no-web format.  (8/10/89)
      by Jim Fox, University of Washington
 
 \input cnoweb   % load the c-no-web system
%
% \nweb ... \bewn = \cnoweb commentary
  \def\nweb{\leavevmode\begingroup\codetype$\lbrack\!\lbrack\;$}
  \def\bewn{$\;\rbrack\!\rbrack$\ \endgroup}
%
 \title{Printing factorials: a demonstration of \cnoweb}
 \synopsis{You are reading a program listing that was formatted
  with \par\item{}{\tt \% tex pf.c}\par
  The same program is compiled
  with \par\item{}{\tt \% cc pf.c}\par
  The key to this dual function source file is a \TeX\ macro
  package called \cnoweb\ that treats all comments as `\TeX-text'
  and all else as `verbatim-text.' The C compiler naturally
  does the opposite and interprets only the text outside the comments.

  \nweb In this program comments about 
     \cnoweb\ itself look like this.\bewn}
 \section{Introduction}
 
  This program prints factorials of positive integers.
  It uses this definition of $n!$
  $$ n! = \prod_{i=1}^n i$$
 
  {\narrower
  \nweb \"pf.c" begins with a comment which
  is treated as \TeX-text by \cnoweb.
 
  The first comment contains the
   string *<\input cnoweb>*.  This begins the \cnoweb\ listing.
   Included also in this leading comment section is
   *<\title{Printing ...}>*,
   *<\synopsis{You are reading ...}>*,
   and
   *<\section{Introduction}>*.\bewn\par}

  The program is invoked with the command
  \item{}\"pf $[$-l$]$ $[$-e$]$ $n$"

  where
   \item{\bf -l} prints the factorials of all numbers
     up to and including the limit $n$.
   \item{\bf -e} includes an exponential notation approximation.
   \item{$n$} is the number whose factorial will be printed.
  */

#define GOODEXIT 0          /* exit with this if factorial OK */
#define BADEXIT  1          /* exit with this if error */

#include <stdio.h>          /* standard io stuff */
#include <math.h>           /* math stuff */
char     *malloc();         /* memory allocator */

/* \section{Big-integer routines}
 
  \"pf" would be trivial were it not for the rapid
  growth of $n!$, which is much greater than exponential
  and quickly surpasses even the real number capacity of most machines.
  We therefore define a new data type (\"Int") to hold big integers.
  */

  typedef struct Int_ {
     int radix;                /* $2^1 \le \hbox{radix} \le 2^8$ */
     char *digits;             /* the \"Int"'s digits */
     int length;               /* number of digits available */
     int limit;                /* number of digits in use */
  } Int;
  
/* We do not need many operations on \"Int"s to compute factorials:
   only `set' and `multiply'.
  */
 
/* \subsection{\"Set(I,\ i)"}   
  Return \"I" initialized to \"i". */    
    
Set(I,i) 
Int *I; 
int i;  
{   
   int d;   
   I->digits[0] = (i?1:0);
   for (d=1; d<I->length; I->digits[d++]=0); 
   I->limit = 0;   
   if ((i!=0)&&(i!=1)) Product(I,i);
   return (0);
}   
 
/* \subsection{\"Product(I,\ i)"}   
  Return \"I" multiplied by \"i".
  Returns true if the product is OK. */    
    
Product(I,i) 
Int *I; 
int i;  
{   
   int d,n;   
   int l = I->limit+1;
   int r = I->radix;
   int carry = 0;
 
   for (d=0; ((d<l)||(carry!=0)); d++) { 
     if (d>=I->length) return (0);       /* not enough digits */
     n = I->digits[d] * i + carry;
     if ((I->digits[d] = n % r)>0) I->limit = d;
     carry = n / r;
   }
   return (1);
}   

 
 
/* \section{\"main()"} Print the factorial of the integer
   found on the command line.

   \item{1.} Parse command line arguments.
   \item{2.} Compute number of digits needed and allocate space.
   \item{3.} Calculate the factorial.
   \item{4.} Print the factorial.

     \nweb \cnoweb\ breaks pages only before comments.\hfill\break
     You can control pagination with this knowledge.\bewn

     The higher the radix the fewer digits needed, but
     we use an internal radix of 10
     to save a lot of division when printing the number. 
     Also, we already have a log$_{10}$ function.

   */

#define RADIX 10
 
Int nfactorial;      /* place for the factorial */
Int *nf = &nfactorial;
 
/* command line parameters */

 int limit_mode = 0;        /* true if printing all factorials */
 int expon_mode = 0;        /* true if printing exponential notation */
 
/* start of the program */

main(argc,argv)
int  argc;
char *argv[];
{
 int n;
  int i;
 
  /* 1. Parse the command line */

  n = parse_args(argc,argv);  /* we will print $n!$ */
 
  /* 2. Compute digits needed and allocate space */

  nf->radix = RADIX;
  nf->length = digits(n,RADIX);

  if ((nf->digits = malloc(nf->length))==NULL) {
     printf("Sorry, cannot allocate space for %d digits\n",
         nf->length);
     exit (BADEXIT);
  }
  
  /* 3. Calculate the factorial.  */

  Set(nf,1);         /* initialize \"nf" */
 
  for (i=1; i<=n; i++) {
     if (Product(nf,i)==0) {
        printf("Sorry, miscalculated the number of digits.\n");
        exit (BADEXIT);
     }
     if (limit_mode) print_Int(nf,i);
  }
 
  /* 4. Print the result, if it hasn't been printed yet. */
 
  if (!limit_mode) print_Int(nf,n);
  exit (GOODEXIT);
}
 
/* \subsection{\"parse_args(argc,argv)"}

     This is a standard UNIX idiom.
     See Kernighan \& Ritchie.

    \nweb \cnoweb\ automatically indents after 
      {\tt\char`\{} and {\tt\char`\(}.\bewn */

parse_args(argc,argv)
int argc;
char *argv[];
{
  int n = (-1);

  while (--argc > 0) {
    argv++;
    if (argv[0][0]=='-') {   /* is an option  flag */
       switch (argv[0][1]) {
          case 'l': {
            limit_mode = 1;
            break;
          }
          case 'e': {
            expon_mode = 1;
            break;
          }
          default: show_usage();
       }
    } else {                 /* is the number */
       sscanf(argv[0],"%d",&n);
    }
  }
 
  if (n<=0) show_usage();
  return (n);
}

/* \subsection{\"digits(n,r)"} Returns number of digits in \"n"
   using a radix of \"r".

     A factorial can be approximated by the Sterling formula
     $$ n! \approx e^{-n} n^{n} \sqrt{2\pi n}$$
     What we want is the number of digits, which is
     $$ \hbox{\# digits} \approx \log_r(n!)=\log(n!)/\log(r) \approx
        (-n \log e + n \log n + {1\over2}\log (2\pi n))/\log(r)$$

     We will add a couple of digits to this value
     to allow for the approximations and assure that we
     have enough.
  */

#define PI    3.141592653589793238462643   /* $\pi$ */
#define E     2.718281828459045235360287   /* $e$ */

digits(n,r)
int n;
int r;
{
  double dn = n;
  int nd;

  nd = (int)((-dn * log10(E)) + 
     (dn * log10(dn)) + (.5 * log10(2*PI*dn)))/log10((double)r) + 2;
  /* *<printf("requires %d digits\n",nd);>* */

  /* \nweb The
  `Commented out' code above was typed: 
  {\tt/{}* *{}<printf...;>{}* *{}/}.\bewn */

  return (nd);
}

/* \subsection{\"print_Int(I,\ i)"}   
  Print {\tt{\it value(}i{\it)} = {\it value(}I{\it)}}.
  The internal radix that matches the display radix
  clearly makes this procedure easier.

  This display uses the convention that separates each
   three-digit set with commas.
*/    
    
#define MAX_WIDTH 80            /* maximum width of the output */

print_Int(I,i) 
Int *I; 
int i;  
{   
   int d;   
   int lp,bp;
   char line[MAX_WIDTH];
 
   sprintf(line,"%d! = ",i);
   bp = lp = strlen(line);
   for (d=I->limit; d>=0; d--) {
      line[lp++] = I->digits[d] + '0';  /* assumes radix $\le 10$ */
      if ((d%3)==0) {
         line[lp++] = (d?',':'.');
         if ((d==0) || (lp>MAX_WIDTH-5)) {
           line[lp] = '\0';
           printf("%s\n",line);
           for (lp=0; lp<bp; line[lp++]=' ');
         }
      }  
   }

   /* If the exponential notation was desired, print it now.
      */

   if (expon_mode) {
      int d = I->limit;       /* the most significant digit */
      sprintf(line+bp,"approximately = %d.%d x 10e%d",
        I->digits[d],d?I->digits[d-1]:0,d);
      printf("%s\n",line);
   }
   return (0);
}
 
/* \section{\"show_usage()"} invocation syntax error---show 
   correct usage */ 
    
int show_usage()
{   
   printf("usage: pf [-l] [-e] positive_integer\n"); 
   exit (BADEXIT);
}   

/* \section{Summary of \cnoweb\ commands}

   These control sequences are defined in the \cnoweb\ macro package.

   \begingroup
     \def\{{{\tt\char`\{}}
     \def\}{{\tt\char`\}}}
     \def\cs#1{\smallskip\noindent\hangindent7\blockindent\hangafter1
        \hbox to7\blockindent{\bf#1\qquad\hss}\ignorespaces}

   \cs{\\title\{ ... \}} Titles the program.
   \cs{\\job\{ ... \}} Another title area. Defaults to input filename.
   \cs{\\section\{ ... \}} Begins a section.  The section title 
    is also included in the table of contents and 
    in the page header.
   \cs{\\subsection\{ ... \}} Begins a subsection.  The subsection title 
    is also included in the table of contents.
   \cs{\\subsubsection\{ ... \}} Begins a subsubsection.  
    The subsubsection title 
    is also included in the table of contents.
   \cs{\\newpage} Causes a page eject after the current line.  This 
    is usually used in a comment by itself, e.g.,
    \hbox{\tt /{}* \\newpage *{}/}.
   \cs{\\endc} Ends the \cnoweb\ listing.  This
    is usually the last line in the file, e.g.,
    \hbox{\tt /{}* \\endc *{}/}.
   \cs{\\{\tt"} ... {\tt"}} Prints {\bf bold} text.
   \cs{\\{\tt'} ... {\tt'}} Prints {\it italic} text.
   \cs{\\{\tt|} ... {\tt|}} Prints {\tt typewriter} text.
   \cs{*{\tt<} ... {\tt>}*} Allows C code to be included in comments.
      You can nest comments within the `commented out' C code, e.g.,
      \hfill\break 
      {\tt/{}* comment out this section *{}<} \hfill\break
      \hglue\blockindent{\tt i = 0; /{}* initialize \"i" *{}/} \hfill\break
      \hglue\blockindent{\tt ...}  \hfill\break
      \hglue\blockindent{\tt >{}* end of the commented out section *{}/}
      
   \cs{\\item, \\hang, {\rm etc.}} Work as you hope they would.
  \endgroup

  */
    
/* \section{How to obtain \cnoweb}

  You may obtain \cnoweb\ by anonymous ftp to
  {\tt u.washington.edu}.

  It is in the directory:  {\tt pub/tex/cnoweb}

  \bigskip
    \rightline{--- Jim Fox,
     University of Washington}
    \rightline{\strut \tt fox@cac.washington.edu}

   \medskip

   The file ends with the comment
    `{\tt /{}* \\endc *{}/}' */
   
/* \endc */