/home/toolbox/public_html/solutions/3/324/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 2021-01-04
19 * Purpose: fun
20 * Problem: 324 - Factorial Frequencies
21 */
22
23 /*
24 * This template reads data until a terminating value is reached.
25 */
26
27
28 /*
29 * LargeNumber library
30 *
31 * authors: Isaac Traxler & students
32 *
33 * This is a project started back in 2000 that was not finished
34 * and forgotten. It has now been resurrected.
35 *
36 * The goal of this project is to produce a usable c source library
37 * for large number arithmetic.
38 *
39 * Students in my Psychology of Programming class in 2000 contributed.
40 * Since I have largely restructured it, individual names have been
41 * removed from the individual routines. So here are the names of the
42 * original contributing students:
43 * - Paul Miller
44 * - Wojciech Stryjewski
45 * - Phil Bordelon
46 * - John Walker
47 * - Erin Valentine
48 * - Jay Ponville
49 * - Jamie Ahmad
50 * - Helen
51 *
52 * Contributed to revamped version:
53 * - Josh Abadie
54 */
55 /* Updates:
56 * 20210205 IWT change strncpy to sprintf (for initializing string)
57 * 20210205 IWT convert comments from C++ (//) style to C style
58 */
59 #include <ctype.h>
60 /*
61 * Make sure that LN_MAX_DIGITS is large enough to handle worst case.
62 * Be aware that as many as 5 LN instances might exist in a routine.
63 * Be aware that excessively large values will result in CPU consumption
64 * in certain situations (like division of repeating decimals).
65 */
66 #define LN_MAX_DIGITS 1000
67
68 typedef struct LARGE_NUMBER_STRUCT
69 {
70 unsigned short int array[LN_MAX_DIGITS]; /* might consider unsigned char here
71 * to reduce storage by 50% */
72 signed short int sign;
73 signed long int exponent;
74 signed short int digitCount;
75 }
76 LARGE_NUMBER_STRUCT;
77 /*
78 * ASSUMPTIONS:
79 * 1) That no value sent to the library will exceed bounds
80 * a) Exponent will fit into a signed long at ALL times
81 * b) Significant digit count will not exceed LN_MAX_DIGITS
82 *
83 * 2) LN instances are ALWAYS normalized when passed into a routine
84 *
85 * 3) Adding or subtracting two 501 digit numbers can exceed 1000 digits
86 *
87 * 4) No bounds checking is done against LN_MAX_DIGITS
88 *
89 * 5) Normalization does the following:
90 * a) Adjusts exponent, adjusts digitCount, and removes leading zeroes
91 * b) Adjusts digitCount and removes trailing zeroes
92 * c) Leaves number so that a decimal point is implied before the first digit
93 *
94 *
95 * ********************************************************************************
96 * rules:
97 * - all routines return 0 if everything is okay, a different positive number
98 * for each different error
99 * - Any result passed back (except from LNshift) is normalized
100 * - LNadd adds any two numbers with same sign (calls subtract if signs differ)
101 * - LNsubtract subtracts any two numbers with same sign (calls add if signs differ)
102 *
103 * a = 1
104 * b = -1
105 * add(a,b,c) ==> subtract(a,(-b),c)
106 * subtract(a,b,c) ==> add(a,(-b),c)
107 *
108 * - 0 ALWAYS has a + sign and an exponent of 0
109 *
110 */
111
112 void LNprint(LARGE_NUMBER_STRUCT *n)
113 /* simple routine to print large number */
114 {
115 /* BEGIN function LNprint -- (200302) */
116 char str[LN_MAX_DIGITS+25];
117
118 LNarr2strExp(n, str);
119 printf("[%s]\n", str);
120 } /* END function LNprint -- (200302) */
121
122 int LNnegate(LARGE_NUMBER_STRUCT *ln1)
123 /* changes sign of ln1 */
124 {
125 /* BEGIN function LNnegate -- (200302) */
126 if (0 != ln1->digitCount)
127 ln1->sign *= -1;
128 return 0;
129 } /* END function LNnegate -- (200302) */
130
131 int LNcompare(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2)
132 /* compares to see if a<b (-1), a=b (0), a>b (1); assumes both numbers */
133 /* are normalized (have first digit non-zero and no trailing zeros) */
134 {
135 /* BEGIN function LNcompare -- (200303) */
136 int toReturn = 0;
137
138 /* XOR the two, if same 0 (false) results, if different -2 (true) */
139 if (ln1->sign ^ ln2->sign) /* signs are same, result is 0 */
140 {
141 /* have different signs */
142 toReturn = (0 > ln1->sign) ? -1 : 1;
143 } /* have different signs */
144 else
145 {
146 /* have same sign */
147 if (ln1->exponent != ln2->exponent)
148 {
149 /* exponents not equal, return 1 (1st one) or -1 (2nd one) to show larger */
150 toReturn = (ln1->exponent > ln2->exponent) ? 1 : -1;
151 } /* exponents not equal, return 1 (1st one) or -1 (2nd one) to show larger */
152 else
153 {
154 /* numbers have same exponent */
155 int i, t;
156
157 t = (ln1->digitCount > ln2->digitCount) ? ln2->digitCount : ln1->digitCount;
158 for (i=0; (i<t) && (0 == toReturn) ; i++)
159 {
160 /* for - compare each digit */
161 if (ln1->array[i] != ln2->array[i])
162 toReturn = (ln1->array[i] > ln2->array[i]) ? ln1->sign : - ln2->sign;
163 } /* for - compare each digit */
164 /* digits identical, but one number has extra digits, so number with extra digits */
165 /* is bigger if positive, smaller if negative. */
166 if ((0 == toReturn) && (ln1->digitCount != ln2->digitCount))
167 toReturn = (ln1->digitCount > ln2->digitCount) ? ln1->sign : - ln2->sign;
168 } /* numbers have same exponent */
169 } /* have same sign */
170 return toReturn;
171 } /* END function LNcompare -- (200303) */
172
173 int LNstr2arr(char str[], LARGE_NUMBER_STRUCT *ln)
174 /* convert from string into LN data structure
175 * assume no invalid characters in string (but skip over leading and trailing blanks)
176 *
177 * State diagram:
178 *
179 * state | val | whitespace | - | + | . | digit | Ee | end of string`
180 * ------+-----+------------+------+------+------+-------+------+--------------
181 * start | 1 | start | num1 | num1 | dec1 | num2 | err | 0
182 * num1 | 2 | err | err | err | dec1 | num2 | err | err
183 * num2 | 3 | normalize | err | err | dec2 | num2 | exp1 | normalize
184 * dec1 | 4 | err | err | err | err | dec2 | err | err
185 * dec2 | 5 | normalize | err | err | err | dec2 | exp1 | normalize
186 * exp1 | 6 | err | exp2 | exp2 | err | exp3 | err | err
187 * exp2 | 7 | err | err | err | err | exp3 | err | err
188 * exp3 | 8 | normalize | err | err | err | exp3 | err | normalize
189 */
190 {
191 /* BEGIN function LNstr2arr -- (200302) */
192 #define START 1
193 #define NUM1 2
194 #define NUM2 3
195 #define DEC1 4
196 #define DEC2 5
197 #define EXP1 6
198 #define EXP2 7
199 #define EXP3 8
200 /*
201 * status - (succes/failure) flag (init to SUCCESS)
202 * done - are we done yet? (init to NO)
203 * dpflag - decimal point flag - Have we encountered one yet? (init to NO)
204 * numflag - number flag - Have we encountered any NON-ZERO digits yet? (init to NO)
205 * n - counter/subscript for large number (init to start)
206 * ch - point to main string
207 * These next two need not be used if their values are stored directly into large number.
208 * sign
209 * exp
210 */
211 int state = START, done = 0, n = 0;
212 signed short int dpflag = 0, numflag = 0, sign = 1;
213 signed long int exp;
214 char *ch = str;
215
216 /* skip leading blanks and leading zeroes (start < > start)
217 while ( (isspace(*ch)) || ('0' == *ch) ) ch++; */
218
219 if (0 != *ch) /* is it end of string? */
220 {
221 /* not empty string */
222 /* do we have a sign (must be first char) */
223 if ('-' == *ch)
224 {
225 /* negative - state is NUM1 */
226 sign = -1;
227 ch++;
228 } /* negative - state is NUM1 */
229 else
230 /* Check for plus sign: Not really necessary...(these 4 lines may */
231 /* be omitted) if numbers are not going to have unary pluses */
232 if (*ch == '+')
233 {
234 /* positive (the default) - state is NUM1 */
235 ch++;
236 } /* positive (the default) - state is NUM1 */
237
238 /* now get digits until the decimal point or exponent */
239 while (isdigit(*ch))
240 {
241 /* process digits -- into state NUM2 */
242 state = NUM2;
243 ln->array[n++] = *ch - '0';
244 ch++; /* move to next char in string */
245 } /* process digits -- into state NUM2 */
246 exp = n;
247
248 if ('.' == *ch)
249 {
250 /* decimal point */
251 /* set state to DEC1 if no digits, DEC2 if digits already */
252 state = (NUM2 != state) ? DEC1 : DEC2;
253 ch++;
254
255 /* now get digits after the decimal point */
256 if (isdigit(*ch)) state = DEC2;
257 while (isdigit(*ch))
258 {
259 /* process digits -- into state NUM2 */
260 ln->array[n++] = *ch - '0';
261 ch++; /* move to next char in string */
262 } /* process digits -- into state NUM2 */
263 } /* decimal point */
264
265 /* only things left are Ee (exponent), whitespace and end of string */
266 if (('E' == *ch) || ('e' == *ch))
267 {
268 /* okay we have an exponent */
269 signed long int texp;
270
271 state = EXP2;
272 ch++;
273 sscanf(ch, "%d", &texp);
274 exp += texp;
275 } /* okay we have an exponent */
276 } /* not empty string */
277
278 if ((EXP2 == state) || (DEC2 == state) || (NUM2 == state))
279 {
280 /* normalize number */
281 ln->sign = sign;
282 ln->exponent = exp;
283 ln->digitCount = n;
284 state = 0;
285 } /* normalize number */
286 return state;
287 } /* END function LNstr2arr -- (200302) */
288
289 int LNicnvrt(long int number, LARGE_NUMBER_STRUCT *n)
290 /* convert a long int to Large Number */
291 {
292 /* BEGIN function LNicnvrt -- (200302) */
293 int idx, digit, j;
294
295 /* do sign */
296 n->sign = (number < 0) ? -1 : 1;
297
298 /* set mantissa and exponent */
299 n->exponent = 0;
300 idx = LN_MAX_DIGITS;
301 while (number > 0)
302 {
303 /* while */
304 digit = number % 10;
305 n->array[--idx] = digit;
306 number /= 10;
307 } /* while */
308 n->exponent = LN_MAX_DIGITS - idx;
309 n->digitCount = n->exponent;
310 for (j=0; LN_MAX_DIGITS > (j + idx); j++)
311 {
312 /* for */
313 n->array[j] = n->array[idx+j];
314 } /* for */
315 return 0;
316 } /* END function LNicnvrt -- (200302) */
317
318 int LNarr2strExp(LARGE_NUMBER_STRUCT *ln, char str[])
319 /* convert the ln struct to a string in scientific notation */
320 {
321 /* BEGIN function LNarr2strExp -- (200302) */
322 int i, cnt = 0;
323
324 if (0 == ln->digitCount)
325 {
326 /* handle zero */
327 sprintf(str, "+0E0");
328 } /* handle zero */
329 else
330 {
331 /* handle non-zero */
332 str[cnt++] = (0 > ln->sign) ? '-' : '+';
333 str[cnt++] = '0' + ln->array[0];
334 str[cnt++] = '.';
335 for (i = 1; i < ln->digitCount; i++)
336 str[cnt++] = '0' + ln->array[i];
337 str[cnt++] = 'E';
338 sprintf(&(str[cnt]), "%+ld", (ln->exponent-1));
339 } /* handle non-zero */
340 return 0;
341 } /* END function LNarr2strExp -- (200302) */
342
343 int LNarr2strInt(LARGE_NUMBER_STRUCT *ln, char str[])
344 /* convert the ln struct to a string n integer format with truncate */
345 {
346 /* BEGIN function LNarr2strInt -- (200302) */
347 int i, cnt = 0;
348
349 if ((0 > ln->exponent) || (0 >= ln->digitCount))
350 {
351 /* abs(number) less than 0 or number is zero */
352 sprintf(str, "+0");
353 } /* abs(number) less than 0 or number is zero */
354 else
355 {
356 /* something to convert */
357 int x;
358
359 str[cnt++] = (0 > ln->sign) ? '-' : '+';
360 x = (ln->exponent > ln->digitCount) ? ln->digitCount : ln->exponent;
361 for (i = 0; i < x; i++)
362 str[cnt++] = '0' + ln->array[i];
363 x = ln->exponent - ln->digitCount;
364 for (i=0; i < x; i++)
365 str[cnt++] = '0';
366 str[cnt] = 0;
367 } /* something to convert */
368 return 0;
369 } /* END function LNstrInt -- (200302) */
370
371 int LNln2strFloat(LARGE_NUMBER_STRUCT *ln, char str[])
372 /* convert the ln struct to a string in float format */
373 {
374 /* BEGIN function LNln2strFloat -- (200302) */
375 int i, cnt = 0;
376
377 if (0 == ln->digitCount)
378 {
379 /* handle 0 */
380 sprintf(str, "+0.0");
381 } /* handle 0 */
382 else
383 {
384 /* not zero */
385 int x1, x2;
386
387 str[cnt++] = (0 > ln->sign) ? '-' : '+';
388 x1 = (ln->exponent > ln->digitCount) ? ln->digitCount : ln->exponent;
389 for (i = 0; i < x1; i++)
390 str[cnt++] = '0' + ln->array[i];
391 x2 = ln->exponent - ln->digitCount;
392 if (0 > x2)
393 {
394 /* digitCount larger */
395 str[cnt++] = '.';
396 for (i = x1; i < ln->digitCount; i++)
397 str[cnt++] = '0' + ln->array[i];
398 } /* digitCount larger */
399 else
400 {
401 /* exponent larger */
402 for (i=0; i < x2; i++)
403 str[cnt++] = '0';
404 str[cnt++] = '.';
405 str[cnt++] = '0';
406 } /* exponent larger */
407 str[cnt++] = 0;
408 } /* not zero */
409 return 0;
410 } /* END function LNstrFloat -- (200302) */
411
412 int LNshift(LARGE_NUMBER_STRUCT *ln, int cnt)
413 /* shift the implied decimal point */
414 {
415 /* BEGIN function LiNshift -- (200302) */
416 /* errorLevel - Errorlevel to return. */
417 /* i - Loop variable. */
418 int i, errorLevel = 0;
419
420 if (0 < ln->digitCount)
421 if (0 < cnt)
422 {
423 /* non-negative - do the shift */
424 for ((i = ln->digitCount - 1); i >= 0 ; i --)
425 ln->array[i + cnt] = ln->array[i];
426 for (i = 0; i < cnt; i ++)
427 ln->array[i] = 0;
428 ln->exponent += cnt;
429 ln->digitCount += cnt;
430 } /* non-negative - do the shift */
431 else if (0 != cnt)
432 {
433 /* can't do it */
434 fprintf (stderr, "Error: Cannot shift negative bits.\n");
435 errorLevel = 1;
436 } /* can't do it */
437 return errorLevel;
438 } /* END function LNshift -- (200302) */
439
440 int LNnormalize(LARGE_NUMBER_STRUCT *ln)
441 /* fix LN so that arr[0] <> 0 (if possible) */
442 {
443 /* BEGIN function LNnormalize -- (200302) */
444 /* errorLevel - Errorlevel to return.
445 * zeroCount - How many zeroes?
446 * i - Loop variable
447 */
448 int i, errorLevel = 0, zeroCount = 0;
449
450 if (0 < ln->digitCount)
451 {
452 /* digits to process */
453 while ((ln->array[zeroCount] == 0) && (zeroCount < ln->digitCount))
454 {
455 /* count leading zeroes */
456 zeroCount ++;
457 } /* count leading zeroes */
458 if (0 < zeroCount)
459 {
460 /* found leading zeroes */
461 if (zeroCount == ln->digitCount)
462 {
463 /* entire number is zero */
464 ln->exponent = 0;
465 ln->digitCount = 0;
466 ln->sign = 1;
467 } /* entire number is zero */
468 else
469 {
470 /* digits to shift */
471 ln->digitCount -= zeroCount;
472 ln->exponent -= zeroCount;
473 for (i = 0; i < ln->digitCount; i++)
474 {
475 /* shift them */
476 ln->array[i] = ln->array[i + zeroCount];
477 } /* shift them */
478 } /* digits to shift */
479 } /* found leading zeroes */
480 /* handle railing zeroes */
481 i = ln->digitCount - 1;
482 while ((i >= 0) && (0 == ln->array[i]))
483 {
484 /* while */
485 ln->digitCount--;
486 i--;
487 } /* while */
488 if (0 == ln->digitCount)
489 {
490 /* entire number is zero */
491 ln->exponent = 0;
492 ln->sign = 1;
493 } /* entire number is zero */
494 } /* digits to process */
495 return (errorLevel);
496 } /* END function LNnormalize -- (200302) */
497
498 int LNadd(LARGE_NUMBER_STRUCT *lna, LARGE_NUMBER_STRUCT *lnb,
499 LARGE_NUMBER_STRUCT *ln3)
500 /* ln3=ln1+ln2 */
501 {
502 /* BEGIN function LNadd -- (200302) */
503 int i, cnt, state = 0, carry = 0;
504 LARGE_NUMBER_STRUCT ln1, ln2;
505
506 if (0 == lna->digitCount)
507 *ln3 = *lnb;
508 else if (0 == lnb->digitCount)
509 *ln3 = *lna;
510 else
511 {
512 /* add non-zero numbers */
513 ln1 = *lna;
514 ln2 = *lnb;
515 if (ln1.sign != ln2.sign)
516 {
517 /* signs different */
518 LNnegate(&ln2);
519 state = LNsubtract(&ln1, &ln2, ln3);
520 } /* signs different */
521 else
522 {
523 /* signs are same -- continue adding */
524 if (ln1.exponent > ln2.exponent)
525 {
526 /* ln1 is bigger */
527 LNshift(&ln1, 1);
528 LNshift(&ln2, (ln1.exponent - ln2.exponent));
529 } /* ln1 is bigger */
530 else
531 {
532 /* ln2 is bigger */
533 LNshift(&ln2, 1);
534 LNshift(&ln1, (ln2.exponent - ln1.exponent));
535 } /* ln2 is bigger */
536
537 if (ln1.digitCount > ln2.digitCount)
538 {
539 /* 1 has more digits */
540 for (i = ln1.digitCount - 1; i >= ln2.digitCount; i--)
541 ln3->array[i] = ln1.array[i];
542 cnt = ln2.digitCount;
543 ln3->digitCount = ln1.digitCount;
544 } /* 1 has more digits */
545 else
546 {
547 /* 2 has more digits */
548 for (i = ln2.digitCount - 1; i >= ln1.digitCount; i--)
549 ln3->array[i] = ln2.array[i];
550 cnt = ln1.digitCount;
551 ln3->digitCount = ln2.digitCount;
552 } /* 2 has more digits */
553 /* now actually add */
554 ln3->exponent = ln1.exponent;
555 for (i = cnt - 1; i >= 0; i--)
556 {
557 /* for */
558 ln3->array[i] = ln1.array[i] + ln2.array[i] + carry;
559 if (ln3->array[i] > 9)
560 {
561 /* set carry */
562 carry = 1;
563 ln3->array[i] -= 10;
564 } /* set carry */
565 else
566 {
567 /* reset carry */
568 carry = 0;
569 } /* reset carry */
570 } /* for */
571 LNnormalize(ln3);
572 } /* signs are same -- continue adding */
573 } /* add non-zero numbers */
574 return state;
575 } /* END function LNadd -- (200302) */
576
577 int LNsubtract(LARGE_NUMBER_STRUCT *lna, LARGE_NUMBER_STRUCT *lnb,
578 LARGE_NUMBER_STRUCT *ln3)
579 /* ln3=ln1-ln2 */
580 {
581 /* BEGIN function LNsubtract -- (200303) */
582 int toReturn = 0;
583 LARGE_NUMBER_STRUCT ln1, ln2;
584
585 ln1 = *lna;
586 ln2 = *lnb;
587
588 if (0 == lna->digitCount)
589 {
590 /* first number is zero */
591 *ln3 = *lnb;
592 LNnegate(ln3);
593 } /* first number is zero */
594 else if (0 == lnb->digitCount)
595 *ln3 = *lna;
596 else
597 {
598 /* subtract non-zero numbers */
599 if (ln1.sign != ln2.sign)
600 {
601 /* signs different */
602 LNnegate(&ln2);
603 toReturn = LNadd(&ln1, &ln2, ln3);
604 } /* signs different */
605 else
606 {
607 /* signs are same - so subtract */
608 int t, i, tmp, borrow = 0;
609
610 t = LNcompare(&ln1, &ln2);
611 if (0 == t)
612 {
613 /* same number - return 9 */
614 ln3->sign = 1;
615 ln3->exponent = 0;
616 ln3->digitCount = 0;
617 } /* same number - return 9 */
618 else if (0 > t)
619 {
620 /* first number smaller */
621 toReturn = LNsubtract(&ln2, &ln1, ln3);
622 ln3->sign = -1 * ln3->sign;
623 } /* first number smaller */
624 else
625 {
626 /* everything okay - actually subtract */
627 ln3->sign = ln1.sign;
628 ln3->exponent = ln1.exponent;
629 LNshift(&ln2, (ln1.exponent - ln2.exponent));
630 if (ln1.digitCount != ln2.digitCount)
631 if (ln1.digitCount > ln2.digitCount)
632 {
633 /* add zeroes to ln2 */
634 for (i=ln2.digitCount; i < ln1.digitCount; i++)
635 ln2.array[i] = 0;
636 ln2.digitCount = ln1.digitCount;
637 } /* add zeroes to ln2 */
638 else
639 {
640 /* add zeroes to ln1 */
641 for (i=ln1.digitCount; i < ln2.digitCount; i++)
642 ln1.array[i] = 0;
643 ln1.digitCount = ln2.digitCount;
644 } /* add zeroes to ln1 */
645
646 for (i = ln1.digitCount - 1; i >= 0; i--)
647 {
648 /* loop through each digit */
649 tmp = borrow + ln2.array[i];
650 if (ln1.array[i] > tmp)
651 {
652 /* no borrow */
653 ln3->array[i] = ln1.array[i] - tmp;
654 borrow = 0;
655 } /* no borrow */
656 else
657 {
658 /* have to borrow */
659 ln3->array[i] = (10 + ln1.array[i]) - tmp;
660 borrow = 1;
661 } /* have to borrow */
662 } /* loop through each digit */
663 LNnormalize(ln3);
664 } /* everything okay - actually subtract */
665 } /* signs are same - so subtract */
666 } /* subtract non-zero numbers */
667 return toReturn;
668 } /* END function LNsubtract -- (200303) */
669
670 int LNmultiply(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2,
671 LARGE_NUMBER_STRUCT *ln3)
672 /* ln3=ln1*ln2 */
673 {
674 /* BEGIN function LNmultiply -- (200303) */
675 if ((0 == ln1->digitCount) || (0 == ln2->digitCount))
676 {
677 /* multiply by 0 and get 0 */
678 ln3->digitCount = 0;
679 ln3->sign = 0;
680 ln3->exponent = 0;
681 ln3->array[0] = 0;
682 } /* multiply by 0 and get 0 */
683 else
684 {
685 /* guess we have to multiply */
686 int i1, i2, i3, dig, tmp, carry;
687
688 ln3->sign = ln1->sign * ln2->sign;
689 ln3->exponent = ln1->exponent + ln2->exponent;
690 ln3->digitCount = ln1->digitCount + ln2->digitCount;
691 dig = ln3->digitCount - 1;
692 /* zero out ln3 so that it can be summed into */
693 for (i3=0; i3 <= dig; i3++)
694 ln3->array[i3] = 0;
695 for (i2=ln2->digitCount - 1; i2 >= 0; i2--)
696 {
697 /* loop through the second numbers digits */
698 carry = 0;
699 i3 = dig--;
700 for (i1=ln1->digitCount - 1; i1 >= 0; i1--)
701 {
702 /* process first number */
703 tmp = (ln1->array[i1] * ln2->array[i2]) + carry + ln3->array[i3];
704 if (tmp > 9)
705 {
706 /* deal with overflow */
707 carry = tmp / 10;
708 ln3->array[i3] = (tmp % 10);
709 } /* deal with overflow */
710 else
711 {
712 /* no overflow */
713 carry = 0;
714 ln3->array[i3] = tmp;
715 } /* no overflow */
716 i3--;
717 } /* process first number */
718 ln3->array[i3] = ln3->array[i3] + carry;
719 } /* loop through the second numbers digits */
720 LNnormalize(ln3);
721 } /* guess we have to multiply */
722 return 0;
723 } /* END function LNmultiply -- (200303) */
724
725 int LNdivide(LARGE_NUMBER_STRUCT *ln1, long int i2, LARGE_NUMBER_STRUCT *ln3)
726 /* ln3=ln1/i2 */
727 {
728 /* BEGIN function LNdivide -- (200303) */
729 int i, tot = 0;
730
731 ln3->exponent = ln1->exponent;
732 ln3->sign = ln1->sign * ((0 < i2) ? 1 : -1);
733 for (i=0; i < ln1->digitCount; i++)
734 {
735 /* for each digit */
736 tot += ln1->array[i];
737 if (tot >= i2)
738 {
739 /* we can divide */
740 ln3->array[i] = tot / i2;
741 tot = (tot % i2) * 10;
742 } /* we can divide */
743 else
744 {
745 /* can't divide yet, so add a zero */
746 ln3->array[i] = 0;
747 tot *= 10;
748 } /* can't divide yet, so add a zero */
749 } /* for each digit */
750
751 ln3->digitCount = i;
752 while ((LN_MAX_DIGITS > ln3->digitCount) && (0 < tot))
753 {
754 /* add zeroes on right */
755 if (tot >= i2)
756 {
757 /* we can divide */
758 ln3->array[ln3->digitCount] = tot / i2;
759 tot = (tot % i2) * 10;
760 } /* we can divide */
761 else
762 {
763 /* can't divide yet, so add a zero */
764 ln3->array[ln3->digitCount] = 0;
765 tot *= 10;
766 } /* can't divide yet, so add a zero */
767 ln3->digitCount++;
768 } /* add zeroes on right */
769 LNnormalize(ln3);
770 return 0;
771 } /* END function LNdivide -- (200303) */
772
773 int LNdcnvrt(double d, LARGE_NUMBER_STRUCT *n)
774 /* convert a double to Large Number */
775 {
776 /* BEGIN function LNdcnvrt -- (200303) */
777 char str[LN_MAX_DIGITS];
778
779 sprintf(str, "%ld:", d);
780 return LNstr2arr(str, n);
781 } /* END function LNdcnvrt -- (200303) */
782
783 int LNcopy(LARGE_NUMBER_STRUCT *ln1, LARGE_NUMBER_STRUCT *ln2)
784 /* copy from ln1 to ln2 */
785 {
786 /* BEGIN function LNcopy -- (200302) */
787 int i;
788
789 ln2->sign = ln1->sign;
790 ln2->exponent = ln1->exponent;
791 ln2->digitCount = ln1->digitCount;
792 for (i=0; i < ln1->digitCount; i++)
793 ln2->array[i] = ln1->array[i];
794 return 0;
795 } /* END function LNcopy -- (200302) */
796
797 #define LN_DIMM 1000
798 #define MAXX 367
799
800 LARGE_NUMBER_STRUCT a;
801 LARGE_NUMBER_STRUCT b;
802 LARGE_NUMBER_STRUCT c;
803 int num;
804 int cach[MAXX][10];
805
806 void dump(int i)
807 {
808 /* FUNCTION dump */
809 int j;
810
811 printf(" (%d) %3d", 0, cach[i][0]);
812 for (j=1; j<5; j++)
813 {
814 /* for each digit */
815 printf(" (%d) %3d", j, cach[i][j]);
816 } /* for each digit */
817 printf("\n");
818 printf(" (%d) %3d", 5, cach[i][5]);
819 for (j=6; j<10; j++)
820 {
821 /* for each digit */
822 printf(" (%d) %3d", j, cach[i][j]);
823 } /* for each digit */
824 printf("\n");
825 } /* FUNCTION dump */
826
827 void init()
828 {
829 /* FUNCTION init */
830 int i;
831 int j;
832 long int x;
833
834 /* manually set 1 */
835 for (j=0; j<10; j++)
836 {
837 /* for each digit */
838 cach[1][j] = 0;
839 } /* for each digit */
840 cach[1][1] = 1;
841 DEBUG dump(1);
842 x = 1;
843 LNicnvrt(x, &b);
844 DEBUG printf("b: ");
845 DEBUG LNprint(&b);
846 /* 2 thru 366 */
847 for (i=2; i<MAXX; i++)
848 {
849 /* for each possible fact */
850 x = i;
851 LNicnvrt(x, &a);
852 DEBUG printf("a: ");
853 DEBUG LNprint(&a);
854 LNmultiply(&a, &b, &c);
855 DEBUG printf("a: ");
856 DEBUG LNprint(&a);
857 DEBUG printf("b: ");
858 DEBUG LNprint(&b);
859 DEBUG printf("c: ");
860 DEBUG LNprint(&c);
861 LNcopy(&c, &b);
862 for (j=0; j<10; j++)
863 {
864 /* for each digit */
865 cach[i][j] = 0;
866 } /* for each digit */
867 DEBUG LNprint(&c);
868 for (j=0; j<c.digitCount; j++)
869 {
870 /* for each digit */
871 cach[i][c.array[j]] = cach[i][c.array[j]] + 1;
872 DEBUG printf("%d", c.array[j]);
873 } /* for each digit */
874 cach[i][0] = cach[i][0] - c.digitCount + c.exponent;
875 DEBUG printf("\n");
876 DEBUG dump(i);
877 } /* for each possible fact */
878 } /* FUNCTION init */
879
880 int getInput()
881 {
882 /* FUNCTION getInput */
883 int dataReadFlag;
884
885 scanf(" %d ", &num);
886 dataReadFlag = (0 < num);
887 return (dataReadFlag);
888 } /* FUNCTION getInput */
889
890 void process()
891 {
892 /* FUNCTION process */
893 printf("%d! --\n", num);
894 dump(num);
895 } /* FUNCTION process */
896
897 int main()
898 {
899 /* main */
900 int moreToDo;
901
902 init();
903 moreToDo = getInput();
904 while (moreToDo)
905 {
906 /* while */
907 process();
908 moreToDo = getInput();
909 } /* while */
910
911 return EXIT_SUCCESS;
912 } /* main */
913