1
\$\begingroup\$

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

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.

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

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.