Calculating triangular numbers

Question

A triangular number is a product of three factors as follows:

$$ \text{Triangular number} = x(x + 1)(x + 2) $$

Is there a way to make this code faster? As it is the code calculates every triangular number less than or equal to the integer given by the user.

#include <stdio.h>

int main(void) {       

    int firstFactor = 0;
    int secondFactor = 1;
    int thirdFactor = 2;

    int userInput;
    int product = 0;

    printf("Enter a integer: ");
    scanf("%d", &userInput);

    if(userInput == 0) {
        printf("User input is a triangular number\n");
        return 0;
    }

    do {
        firstFactor++;
        secondFactor++;
        thirdFactor++;
        product = firstFactor * secondFactor * thirdFactor;
    } while(product < userInput);

    if(product == userInput) {
        printf("User input is a triangular number\n");
    } else {
        printf("User input is not a triangular number\n");
    }
    return 0;
}

Answer 1

I see a couple of ways to speed this up.

Observe that at least one factor is even, and exactly one factor is a multiple of 3, so these numbers are all divisible by 6. Assuming random input, testing for that at the beginning will find the answer in one inexpensive operation in 5 out of 6 cases:

if (userInput % 6) {
    printf("User input is not a triangular number\n");
    return 0;
}

As for the rest of it, if we set n = x + 1, we get

$$T(n-1)=(n-1)(n)(n+1)=n^3-n$$

Thus, we can solve in O(1) time, though the cube root is a somewhat expensive operation:

#include <math.h>    /* Link with -lm in gcc */

int n;

n = (int) (ceil(cbrt(userInput)) + 0.1);
if (n * (n-1) * (n+1) == userInput)
    printf("User input is a triangular number\n");
else
    printf("User input is not a triangular number\n");

We add 0.1 after the ceil because the double value might be something like 6.9999999999759, which would round to the wrong number when converted to int. The (int) cast suppresses a compiler warning about conversion from double to int.

Answer 2

This looks a reasonably competent attempt. It's very clear how it works. I have a few observations or improvements:

• When reading input using scanf() (or otherwise), it's imperative to check for errors. In this case, we just need to ensure that the return value (number of conversions made) is 1 (i.e. scanf() has assigned to userInput):

  if (scanf("%d", &userInput) != 1) {
      fprintf(stderr, "User input is not a number!\n");
      return 1;
  }
  

• Should we be accepting negative inputs? I think it would be better to use unsigned int and to ask the user only for positive values.

• We don't really need three variables for the factors. Since secondFactor is always equal to firstFactor+1 and thirdFactor is always equal to firstFactor+2, we can replace them with those expressions:

  do {
      firstFactor++;
      product = firstFactor * (firstFactor + 1) * (firstFactor + 2);
  } while(product < userInput);
  

  I might re-write that as a for loop, since there's an increment step (firstFactor++;).

• Beware of arithmetic overflow - if the input is near INT_MAX (or UINT_MAX after moving to unsigned type), then product might exceed the limit of integer type - that's particularly bad for signed types, where overflow is Undefined Behaviour. We might want to ensure that we don't reach that limit, either by using a wider type for product than int (if one exists - long long int could be the same size) or by testing product against the cube root of the limit (perhaps using cbrt() from <math.h>).

• We don't need a special test for userInput == 0. If we compute product before incrementing firstFactor, then the first iteration of the loop will produce 0.

• We could improve the printing, by formatting the tested number as part of the output.

---

Modified code

#include <stdio.h>

int main(void)
{
    printf("Enter an integer: ");

    unsigned int userInput;
    if (scanf("%u", &userInput) != 1) {
        fprintf(stderr, "User input is not a number!\n");
        return 1;
    }

    /* avoid overflow by dividing input by one of the factors */
    for (unsigned int firstFactor = 0;  firstFactor * (firstFactor + 1) <= userInput / (firstFactor + 2);  ++firstFactor) {
        if (userInput == firstFactor * (firstFactor + 1) * (firstFactor + 2)) {
            printf("%u is a triangular number\n", userInput);
            return 0;
        }
    }

    printf("%u is not a triangular number\n", userInput);
    return 0;
}