CS 47 - T. Howell - Spring, 2008

Homework Assignment #5

1. Minimal version (100%):bigfact.c
   

   You are to write one C file, bigfact.c and one short assembly language file mull.s.
   The assembly language file can be the same one used in HW #3. It multiplies two 32-bit unsigned numbers and puts the 64-bit product into memory locations given by two pointers. If you didn't write a successful mull.s for HW #3 you may use the posted solution. As in HW #3, the function defined by mull.s should have the following declaration in C before the procedure main in bigfact.c. void mull(unsigned int x, unsigned int y, unsigned int* low, unsigned int* high);
   
   You are to write a C program called bigfact.c that takes an integer input n and computes n! (n factorial) for n up to 436. The output is in hexadecimal format and gives the exact value of n! up to 800 hexadecimal digits. (This is enough for 436! but not 437!). The output should be broken into "words" of 8 hexadecimal digits with 5 words per line. The first "word" printed should contain the most significant nonzero digits. Here is an example for testing.
   
   100! =
   00001b30 964ec395 dc240695 28d54bbd a40d16e9
   66ef9a70 eb21b5b2 943a321c df103917 45570cca
   9420c6ec b3b72ed2 ee8b02ea 2735c61a 00000000
   00000000 00000000
   
   Your C program will take care of reading the input and printing the output, but it will call mull.s to do all the multiplications. You will store the products in an array of unsigned integers, eight hex digits per integer, and you will probably write a procedure to multiply that array by an unsigned integer.
   
   The compile command to test your programs will look like this:
   gcc -Wall -std=c99 -O2 -o bigfact.exe bigfact.c mull.s .
   
   

2. Extension 1 (150%): bigfactx.c
   

   Instead of a fixed size array to hold n!, use a variable size array. It will be allocated with the malloc function. Be sure to use free to free the space when your program is through using it. You should also check whether malloc fails to allocate your space by comparing its return pointer to NULL. The size of the array you need can be estimated with the following code segment. You may modify it if you wish, but please include the print statement so I can see the sizes you calculate for each n.
   
   int FACTSIZE = n;
   int nn = n;
   while(1 < (nn /= 2)) FACTSIZE += n;
   FACTSIZE = 1 + FACTSIZE/32;
   printf("n = %d, FACTSIZE = %d\n", n, FACTSIZE);
   
   You can test your program for large values of n by sending its output to a file: bigfactx 1000 > testfile.txt
   
   
   

3. Extension 2 (200%): subfactx.c
   

   Using a variable size array as in Extension 1, you may compute !n (n subfactorial, see HW #3 for definition) instead of n!. The computation is similar, but you will need to add or subtract 1 after each multiplication step. Be sure you account for possible carries. You can use the same FACTSIZE because !n is very close to n!/e.

Submission requirements and grading system

CS 47 Section X Homework #5 John Doe