Title: Student Code Critique Competition 29

Let's start by solving the immediate problem. If pf() encounters a prime number it returns an "empty" array i.e. the first element is zero. This means that the body of the while loop in main() is not executed and the ugly flag is not altered; it retains its value from the previous number in the range, which is often ugly, at least for low ranges. The solution is therefore to reset the ugly flag to zero in each iteration of the enclosing for loop. Immediately before or after the line idx = 0; is ideal.

However, the code is still not performing the correct test. It only proves whether or not the last factor in the array is ugly, not that they all are. This may work with the defined set of ugly factors and because of the order in which pf() fills its arrays, but we should rewrite the test instead of relying on this. It's easiest to prove that a number is not ugly, so we'll start by assuming it is until we find a non-ugly factor, not forgetting the initial problem with primes.

But we have something else to take into account: 2, 3 and 5 are prime, so pf() will return an "empty" array and the test will not realise they're also ugly. We could deal with this in pf() by copying quotient's initial value from the variable number rather than 0, but this leads to an inconsistency when the pf() function is considered in its own right: prime numbers have themselves listed as a factor, other numbers don't.

As we're also excluding the number 1 as a factor it makes sense to continue to exclude the number itself and explicitly check for 2, 3 and 5 in our test. Thus the main for loop becomes:

for(n = start; n < stop + 1; ++n) {
  idx = 0;
  flist = pf(n);
  if(flist[0] == 0 && n > FIVE) ugly = 0;
  else ugly = 1;
  while(flist[idx]) {
    if(flist[idx] != TWO &&
       flist[idx] != THREE &&
       flist[idx] != FIVE) {
      ugly = 0;
    }
  ++idx;
  }
  if(ugly == 1)
    printf("%d\n", n);
  free(flist);
}

Now to give the code a complete makeover, starting from the top and working down:

The first issue we encounter is a number of preprocessor macros. Macros should only be used for jobs that nothing else can do, but these can be replaced with const int and/or enum. Furthermore, the purpose of replacing "magic numbers" with named constants is so that if the values need to be changed they only need to be changed in one place. If we want to change this program to deal with a different set of ugly factors, the current names of the constants will be very confusing; if we don't ever want to change it the names are redundant. I've rewritten these constants as:

const int MaxFactors = 20;
  /* Max number of prime factors to find */
enum UglyFactors {
  UglyFac1 = 2,
  UglyFac2 = 3,
  UglyFac3 = 5
};

(Sorry about the pun).

Next we have a prototype for pf(). The name is far too terse, let's make it more descriptive: prime_factors(). The function is only used in the same source file, so it should be declared static. I'm not sure whether the student has covered linkage types yet, but I think it's a relatively straightforward concept and a good habit to learn early.

It appears to be common practice to declare all function prototypes in advance and define static functions towards the end of a file. However, I prefer to avoid separate prototypes except in headers on the grounds that they are a form of repetition. Therefore I've brought the body of the function forward to this point. The comment that precedes it should highlight any points of interest about its parameters and return value - in this case that it returns an array that's been allocated on the heap and that the array is zero-terminated.

Inside the function I've separated the variable declarations because int* and int are actually two quite different types and it's considered bad form to make them share the declaration with commas. I also prefer to give all variables their own distinct declarations unless two or more are closely related and have no initialisers.

I also decided to use the variable name i instead of idx. There is an argument for short variable names as well as long descriptive ones, and while idx was a good name to start with, being concise but still meaningful to almost any programmer, I always use i for the (primary) array index in loops myself and sticking to that convention makes the code more readable to me.

I've changed the while loop condition to (divisor <= number); I think it's less clutter than the original. But we should also check that we haven't exceeded the array bounds. If we really want to know all the prime factors we should extend the array when necessary or come up with a rough figure that's guaranteed to be an overestimate - e.g. the upper limit of the range given to the program - and make the array this size in the first place. However, for this purpose it's adequate to return when the array is filled, remembering to leave room for the terminating zero - which does not need to be inserted explicitly because of the use of calloc instead of malloc. The complete condition is now (divisor <= number && i < MaxFactors - 1).

I noticed that it's possible for the same factor to be entered more than once in the list if its square is also a factor e.g. 2 will appear twice if number is 8 or 12. We can prevent this by checking whether the previous entry is equal to the one we're about to add - remembering that if i is 0 we mustn't try to check element-1:

if(i == 0 || flist[i - 1] != divisor)
  flist[i++] = divisor;

I also have a rule about braces around single statements such as a simple if or for body. Although these are optional I often include them, especially if:

Next I've done some refactoring. Breaking programs down into smaller functions almost invariably makes them more readable, and providing a function to test whether a given number is ugly is a logical step. The body of this function is pretty much as above except that I replaced the while loop with a for loop. Also, bearing in mind being able to change the values of the UglyFac constants, it's unsafe to assume that there are no non-ugly primes below UglyFac3, so we should test against each of them instead of testing whether n > UglyFac3.

I've given main() a comment about its arguments, which is basically an alternative to the "enter a range" comment which I thought was misleading: it implied the range would be read from stdin rather than arguments. Again I've separated the variable declarations. I've kept the variable name n because it's ideal for a loop variable describing a number other than an index, but I've renamed start and stop to first and last, which I think makes it clearer that the range is inclusive. The for loop terminating condition is again changed to use <= instead of <

Just a couple of minor semantics remaining. As ugly is a boolean flag, I prefer to write if(ugly) and if(!ugly) rather than if(ugly==1) and if(ugly==0). And as we're using EXIT_FAILURE we might as well use EXIT_SUCCESS too. Here is my first complete rewrite (keep on reading for my description of a slightly different approach to the problem):

/* Find "ugly numbers": their prime factors
   are all 2, 3 or 5 */
#include <stdio.h>
#include <stdlib.h>

const int MaxFactors = 20;
     /* Max number of prime factors to find */

enum UglyFactors {
  UglyFac1 = 2,
  UglyFac2 = 3,
  UglyFac3 = 5
};

/* Returns a zero-terminated array of number's
   prime factors, allocated on the heap */
static int *prime_factors(int number) {
  int *flist;
  int quotient = 0;
  int divisor = 2;
  int i = 0;

  flist = calloc(MaxFactors, sizeof(int));
  while(divisor <= number
        && i < MaxFactors - 1) {
    if(divisor == number) {
      flist[i] = quotient;
      break;
    }
    if(number % divisor == 0) {
      if(i == 0 || flist[i - 1] != divisor)
        flist[i++] = divisor;
      quotient = number / divisor;
      number = quotient;
    }
    else {
      ++divisor;
    }
  }
  return flist;
}

/* Returns 1 if number is ugly, otherwise 0 */
static int is_ugly(int number) {
  int i = 0;
  int ugly;
  int *flist = prime_factors(number);
  if(flist[0] == 0 && number != UglyFac1
     && number != UglyFac2
     && number != UglyFac3) {
    ugly = 0;
  }
  else {
    ugly = 1;
  }
  for(i = 0; flist[i]; ++i) {
    if(flist[i] != UglyFac1 &&
       flist[i] != UglyFac2 &&
       flist[i] != UglyFac3) {
      ugly = 0;
    }
  }
  free(flist);
  return ugly;
}

/* Range is given in arguments */
int main(int argc, char **argv) {
  int n;
  int first, last;
  if(argc !=3)
    exit(EXIT_FAILURE);
  first = atoi(argv[1]);
  last = atoi(argv[2]);
  for(n = first; n <= last; ++n) {
    if(is_ugly(n))
      printf("%d\n", n);
  }
  return EXIT_SUCCESS;
}

This solution works, but is not the most efficient. We don't actually need to list all the prime factors of ugly candidates, just check them until we find a factor that proves the number isn't ugly, again taking care not to pass primes as false positives. Therefore the prime_factors function can be deleted and is_ugly() replaced with the version below.

/* Returns 1 if a number is ugly, 0 if it
   isn't */
static int is_ugly(int number) {
  int divisor = 2;
  int ugly = 0;
  for(divisor = 2; divisor <= number;
      ++divisor) {
    if(number % divisor == 0) {
      if(divisor % UglyFac1 != 0 &&
         divisor % UglyFac2 != 0 &&
         divisor % UglyFac3 != 0) {
        ugly = 0;
        break;
      }
      else {
        ugly = 1;
      }
    }
  }
  return ugly;
}

I'm newbie to C++ and I would like to know which would be the best (elegant and correct) solution for the following small (string) read problem with gets.

#include <iostream>
using namespace std;
#include <cstdio>

main() {
  int n;
  int waste; // needs this to work (read)
             // properly!!
  char name[51];
  cout << "Enter any integer number...\n";
  cin  >> n;
  cout << "Enter your name...\n";
  cin  >> waste; // 'gets' does not read the
                 // name without this line!!
  gets(name);
}

Mixing C and C++ functions doesn't seem the best way to write this program. Please provide alternatives, taking also into account its security implications.

If I enter 23 and 5 the answer should be 23 * 5 = 115 my answer is off by five or whatever number 2 is. I was told I am not including the first two numbers in the loop. I thought when I cin the numbers it is including them. Does anyone have any suggestions on how I can fix this?

#include<iostream>
#include<iomanip>
#include<string>
using namespace std;
int main()
{
  while (1){
int   num1, num2, total = 0;
cout<<"Enter two numbers: ";
cin>>num1>>num2;
while (num1 != 1)
cout<<setw(5)<<num1<<setw(5)<<num2<<endl;
  num1 /= 2;
    num2 *= 2; 
  if (num1 % 2 != 0)
    total += num2;
}
cout<<"the total is  "<<total <<endl;
}  //End While 1
return 0;
}

There are numerous errors in both the code and the student's understanding. Please address these comprehensively.

#include<iostream>
#include<iomanip>
#include<string>
using namespace std;
int main() {
  while(1) {
    int num1, num2, total = 0;
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;
    while (num1 != 1) {
      cout << setw(5) << num1 
           << setw(5) << num2 << endl;
      num1 /= 2;
      num2 *= 2; 
      if((num1 % 2) != 0) total += num2;
    }
    cout << "the total is " << total << endl;
  }  // End While 1
  return 0;
}

I strongly advocate that the default form of the definition of main() should encapsulate its code in a try block. That seems to me to be a good discipline for students as soon as they are conscious that errors may occur at runtime that result in an exception. Indeed they should be encouraged to validate such things as input and exceptions make it easy for them to have a default action when validation fails. So I would start with:

int main() {
  try {
    // main code
  }
  catch(...) {
    cerr << "An exception occurred.\n";
    return EXIT_FAILURE;
  }
  return EXIT_SUCCESS;
}

Now that is a fixed framework and it isn't even tedious to type because you just copy and paste it from a text file of standard bits of source code.

The first problem with the student's code is that it has no termination. He puts it all in a forever loop without any internal exit. I have no problem with forever loops (except that I use while(true)) as long as they have an internal exit (that is unless you are writing a process which must continue until the machine is switched off). In this case I would write something such as:

while(true) {
  // main process
  cout << "Do you want another? (y/n)";
  char yn;
  cin >> yn;
  if(yn == 'n' || yn == 'N') break;
}

Now we can argue about the details but the general idea should be considered as an idiom of programming (not just C++).

As an ex-maths teacher I quickly recognised the algorithm being implemented by this program (goes under several names, try using Google to search for 'Russian Peasant Multiplication') but the variable names were not helpful. Let me suggest some others and polish up the code whilst I am at it.

cout << "Enter the pair of numbers you want "
     << "to multiply together: ";
int multiplicand(getint());
int multiplier(getint());
int product(0);

Now the variable names give a hint as to what is being done. Validation and handling bad input is all handled by the getint() function. Actually I would use my read() set of templates but that is just a convenience. However avoiding repetitious coding whilst always validating input should be learnt from the very beginning.

Now we get to the actual reason the program does not work. Look at that inner while loop. Look at the test. Surely this is too early, or it is the wrong test because it fails immediately if the multiplicand is one. In other words multiplying one by anything will give a product of zero. There are several solutions but I would prefer:

while(multiplicand)

or if you do not like that form:

while(multiplicand != 0)

For the algorithm (which is effectively using binary for multiplication) we add in the current value of the multiplier into the product if the current value of the multiplicand is odd (i.e. would end in one in binary), then the multiplicand is halved (shifted left) and the multiplier is doubled (shifted right). The order of these operations is vital and is the second point of error in the student's code. Leaving aside the display of the interim results, which I would have preferred to see include the interim value of the product in a third column) the meat of the algorithm is coded as:

if(multiplicand % 2) product += multiplier;
multiplicand /= 2;
multiplier *= 2;

Here is my complete program (well I have left out the front matter of headers and using directive):

int main() {
  try {
    while(true) {
      cout << "Enter the pair of numbers you "
           << "want to multiply together: ";
      int multiplicand(getint());
      int multiplier(getint());
      int product(0);
      while(multiplicand) {
        cout << setw(5) << multiplicand
             << setw(5) << multiplier
             << setw(10) << product
             << '\n';
        if(multiplicand % 2)
          product += multiplier;
        multiplicand /= 2;
        multiplier *= 2;
      }
      cout << "The product is " << product
           << ".\n\n";
      cout << "Do you want another? (y/n)";
      char yn;
      cin >> yn;
      if(yn == 'n' || yn == 'N') break;
    }
  }
  catch(...) {
    cerr << "An exception occurred.\n";}
    return EXIT_FAILURE;
  }
  return EXIT_SUCCESS;
}

Note that the depth of nesting for structures suggests that some refactoring into functions might be desirable. I would probably make the outermost loop a do-while one and use the return value from a function asking about repeating the process in the while. Something like:

do {
  // process
while(do_again());

I would also move out the display of the intermediate results to a function. I would also probably replace the computation block with a function call, but that is much more marginal because all the arguments have to be passed by reference and I doubt that we get much more clarity in exchange for using a function.

Now do feel free to comment on the coding style and anything else that you want to criticise. Remember that this column is supposed to be a kind of seminar and not a lecture.