01: #include<stdio.h>
02: #include<stdlib.h>
03: #include<string.h>
04: 
05: char *binary(unsigned int);
06: void printresults(FILE *, const char *);
07: 
08: int main(int argc, char **argv){
09: 
10:   FILE *fp = fopen("output.txt", "w"); // open file for task #5
11:   if(!fp)
12:   {
13:     perror("");
14:     exit(EXIT_FAILURE);
15:   }
16: 
17:   for(int n = 2; n <= 1023; ++n)
18:   {
19:     printf("%4d:", n);           // print on screen
20:     fprintf(fp, "%4d:", n);      // print also on file
21: 
22:     char *fullbin = binary(n);
23:     char *redbin = fullbin + 1;  // using pointer math, this is the address of a string without the most signficant bit
24: 
25:     printresults(fp, redbin);    // invoke function that prints (and save in a file) partial steps of Pingala' algorithm
26: 
27:     free(fullbin);               // free memory to avoid memory leak
28:   }
29: 
30:   fclose(fp);
31:   return 0;
32: }
33: 
34: // print on screens and file:
35: //  - steps of Pingala' approach
36: //  - number of multiplications to be performed
37: void printresults(FILE *p, const char *bin)
38: {
39:   int mult = 0;                // to compute how many moltiplications are needed
40:   int exp  = 1;                // exponent for X, initially we start from X namely X^1
41:   for(int d = 0; d < strlen(bin); ++d) // loop over bits from most significant one toward least significant one
42:   {
43:     if(bin[d] == '0')  // we need to perform a pow by 2 of previous result (1 multiplication)
44:     {
45:       mult += 1;
46:       exp   = 2*exp;
47:     }
48:     else                 // when we find an 1, we need to compute pow by 2 plus multiplication by X (2 multiplications)
49:     {
50:       mult += 2;
51:       exp   = 2*exp + 1;
52:     }
53:     printf(" X^%d", exp);
54:     fprintf(p, " X^%d", exp);
55:   }
56:   printf(" -> %d multiplications\n", mult);
57:   fprintf(p, " -> %d multiplications\n", mult);
58: }
59: 
60: // recursive function used by binary()
61: void binaryhelper(unsigned int n, char *r)
62: {
63:   // initially I compute the Least Significant Bit of n
64:   // this can be done simply computing the remainder of n/2 
65:   // I need this to be a string, therefore:
66:   char lsb[2]; // 1 binary digit and string ending
67:   lsb[0] = n%2 + '0'; // LSB
68:   lsb[1] = '\0';      // string terminator
69: 
70:   if(n > 1) // if true, we have more binary digits other than LSB
71:   {
72:     // compute other binary digits
73:     binaryhelper(n/2, r);
74:   }
75:   strcat(r, lsb); // add LSB as ending bit
76: }
77: 
78: // return a string containing the binary representation of n
79: char *binary(unsigned int n)
80: {
81:   char *r = malloc(11); // 1023 is 2^10-1, therefore I need up to 10 binary digits + '\0'
82:                         // realloc() would be more efficient from a memory point of view, but it would also lead to very complex code
83:   r[0] = '\0';          // init the string as empty one
84: 
85:   binaryhelper(n, r);
86: 
87:   return r;
88: }
89: