CODEWITHSUNDEEP
cfactorial
user8735693
user8735693

Reputation:

Why doesn't this factorial compute correctly?

I am trying to learn some C programming, and to test my basic skills, I am making a simple program that computes factorials. However, instead of giving the correct answer of 120 for the factorial of 5, it gives -1899959296. What's wrong? Here's my code below:

#include <stdio.h>

int factorial(int x)
{
    int i;
    for(i=1; i < x; i++)
        x *= i;
    return x;
}

int main() 
{ 
    int a = 5, b;
    b = factorial(a);
    printf("The factorial of %d is %d \n", a, b);
    return 0;
}

Thanks in advance!

Upvotes: 1

Views: 802

Answers (4)

Gabriel A. S. Braga
Gabriel A. S. Braga

Reputation: 111

The error is in the for, the factorial of a number is n * n-1 * ... * n-(n-1), so to solve this, just start the index in x - 1 and decrement it until it turns 1, sorry for my bad English, I hope you understood what I said.

here is the answer:

for ( i = x - 1; i > 1; --i )
        x *= i;

Just to explain why the negative number, first we must understand what happens in the for which it was declared.

for(i=1; i < x; i++)
        x *= i;

As we can see the condition for it to continue in the loop is i < x, but within it is assigned to x the value of x * i (x * = i or x = x * i), so x has no constant value and is always increasing, the i increases at a velocity smaller than that of x because the i is always added to 1 (i ++, i + = 1 or i = i + 1), which causes the x to be unreachable , then the for will be in an infinite loop.

But every type has its range, and int is 4 bytes, therefore 32 bit, what happens is that there comes a time when x exceeds this range having the famous integer overflow, this is why its value is negative, then the condition of the for becomes false and then the for stop.

We have to remember that a number is represented in memory in binary form, and the last binary number is what represents whether the number is positive or negative, 0 is positive, 1 is negative, when integer overflow happens the last number changes to 1 , making it so negative.

To better understand this here are some links that can help:

https://en.wikipedia.org/wiki/Two%27s_complement

https://en.wikipedia.org/wiki/Integer_overflow.

Upvotes: 1

Andrew Pikul
Andrew Pikul

Reputation: 251

C) You're using x as an upperbound for your for loop i < x

B) You're also increasing x nearly exponentially on every loop x *= i, your loop won't work.

You might have noticed that you get a negative number back. The reason the loop exits at all is that you've chosen to type x as a 32 bit signed integer (the default int)- The processor works in binary: so once you go higher than is actually possible with just 32 bits, it still tries to do math but it loses data and loops back around to negative numbers. So once x loops back around and becomes negative, then i > x and the loop exits.

Here: http://tpcg.io/8sX5ls

Upvotes: 0

Peter
Peter

Reputation: 36607

Your problem is that the function factorial() is continually modifying x. For any of x which is initially 3 or more, x will keep increasing, so the loop will keep running.

Consider if you call fact(3).

The function is called with x = 3. First iteration of the loop with i = 1 will multiply x by 1. So x will still have the value of 3. i i will be incremented to 2, which is less than 3, so the next iteration starts.

The second iteration of the loop will multiply x by 2, giving the result of 6. i is incremented to 3, which is less than 6, so the next iteration starts.

The third iteration will multiply x by 3, giving the result of 18. i is incremented to 4, which is less than 18, so the next iteration starts.

Notice the pattern in the above ..... the end condition is i < x. i is incremented in each iteration. x is multiplied by i. This means that x increases substantially faster than i does .... which means i < x is always true.

Well almost ..... eventually the logic breaks down.

Eventually x will overflow - the result of multiplying it by i will produce a result that exceeds what can be stored in an int. The result of overflowing an int is undefined ..... anything can happen at that point.

Compare the description above with what YOU would do if asked to compute the factorial of 3. Would you do similar steps? Probably not.

Upvotes: 3

Sandeep P Pillai
Sandeep P Pillai

Reputation: 743

    int factorial(int x)
    {
        int i;
        int count =x;
        for(i=1; i < count ; i++)
            x *= i;
        return x;
    }

Modify like this. your issue is with the loop count.. Since value of x is changing the loop may become infinite..

Upvotes: 2

Related Questions