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;
}

• AJNeufeld: The code is reasonably fast, there is not much you can do to optimize it. Unfortunately, the algorithm is O(n^0.333). A faster algorithm does exist, which allows you to compute the answer in \$O(1)\$ time. Since this is a programming puzzle, I won't provide you the algorithm, but read this comment carefully for a hint.
• vnp: @AJNeufeld If we are on the same page, I want to challenge the \$O(1)\$ possibility for unrestricted \$n\$ (for int n everything is \$O(1)\$). \$O(\log \log n)\$ seems more likely.
• AJNeufeld: @vnp Challenge accepted. Assuming I've done this right, I've created a chat-room between you & me, where we can explore this.
• Calak: Point me where I'm wrong please. Your formula don't match the nth triangular number but 6 * nth triangular number. That's right ? triangular number
• Thales Santos: @Calak The formula that is used in this code was given by my professor. After seeing the pages that you linked i think that you are right.

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.

• Tom Zych: Since my answer currently has more upvotes, I feel obliged to point out that I consider @Toby Speight’s answer more valuable, as it addresses issues of correctness, robustness, and simplicity. I say this even though the OP asked for ways to speed things up; speed is nice but correctness is essential.

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;
}