Calculating triangular numbers

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

• 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. – AJNeufeld Nov 16 '18 at 3:33
• @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. – vnp Nov 16 '18 at 4:28
• @vnp Challenge accepted. Assuming I've done this right, I've created a chat-room between you & me, where we can explore this. – AJNeufeld Nov 16 '18 at 5:53
• 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 – Calak Nov 16 '18 at 6:23
• @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. – Thales Santos Nov 16 '18 at 12:57

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.

• 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. – Tom Zych Dec 18 '18 at 9:34

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