Factorial Function in C

Question

I recently started reading Hacking: The Art of Exploitation by Jon Erickson. In the book he has the following function, which I will refer to as (A):

int factorial (int x)       // .......... 1
{                           // .......... 2
    int i;                  // .......... 3
    for (i = 1; i < x; i++) // .......... 4
        x *= i;             // .......... 5
    return x;               // .......... 6
}                           // .......... 7

This particular function is on pg. 17. Up until this function, I have understood everything he has described. To be fair, he has explained all of the elements within (A) in detail, with the exception of the return concept. However, I just don't see how (A) is suppose to describe the process of

x! = x * (x-1) * (x-2) * (x-3)

etc which I will refer to as (B). If someone could take the time to break this down in detail I would really appreciate it. Since I am asking for your help, I will go through the elements I believe I understand in order to potentially expose elements I believe I understand but actually do not but also to help you help me make the leap from how (A) is suppose to be a representation of (B).

Ok, so here is what I believe I understand.

• In line 1, in (int x), x is being assigned the type integer. What I am less sure about is whether in factorial (int x), int x is being assigned the type factorial, or if even factorial is a type.

• Line 3 is simple; i is being assigned the type integer.

• Line 4 I am less confident on but I think I have a decent grasp of it. I'm assuming line 4 is a while-control structure with a counter. In the first segment, the counter is referred to as i and it's initial value is established as 1. I believe the second segment of line 4, i < x, dictates that while counter i is less than x, keep looping. The third segment, i++, communicates that for every valid loop/iteration of this "while a, then b" situation, you add 1 to i.

• In line 5 I believe that x *= i is suppose to be shorthand for i * x but if I didn't know that this function is suppose to explain the process of calculating a factorial, I wouldn't be able to organically explain how lines 4 and 5 are suppose to interact.

'I humbly ask for your help. For any one who helps me get over this hump, I thank you in advance. '

Answer 1

I think the program given in the book is wrong. Theoretically, the for-loop will never terminate, as x is growing in every iteration, and much faster than i. In practice, x will overflow after some time, thus terminating the loop.

Answer 2

Forget about why this calculates the factorial for a moment. First let's figure out what it does:

int factorial (int x)       // .......... 1
{                           // .......... 2
    int i;                  // .......... 3
    for (i = 1; i < x; i++) // .......... 4
        x *= i;             // .......... 5
    return x;               // .......... 6
}                           // .......... 7

Line 1:

Ignoring the part in the parenthesis for now, the line says int factorial (...) - that means this is a function called factorial and it has a type of int. The bit inside the parenthesis says int x - that means the function takes a parameter that will be called x and is of type int. A function can take multiple parameters separated by commas but this function takes only one.

Line 3:

We are creating a variable which we will call i of type int. The variable will only exist inside these curly braces so when the function is finished i will not exist any more.

Line 4:

This is indeed a looping control that uses the variable i created on line 3 to keep the count. At the start of the loop, the i=1 makes sure the count starts at 1. The i<x means it will keep looping as long as i is less than x. The i++ means each time the loop finishes the stuff in the curly braces the variable i will be incremented. The important part of this line is that the loops stops when i gets to x - which, as we will see, never happens.

Line 5:

The x*=i means the value of x will be updated by multiplying it by i. This will happen each time the loop iterates. So, for example, if x was equal to 5 the loop will make i equal to the values 1, 2, 3 and 4 (the numbers from 1 up but less than x) and the value of x will be updated by multiplying it by 1, 2, 3 and 4, making it larger and larger. But now that x is larger, the loop doesn't end here as expected - in fact, it contines looping making x larger and larger until the value of x no longer fits into an int. At that point, the program has undefined behaviour. Because compilers assume no one would want undefined behaviour, the program can do absolutely anything at that point including crashing or looping infinitely or even rewriting the whole program so it doesn't do any calculations at all.

Line 6:

We need to get that value of x back to the outside world and that is what the return command does - if the program gets to here the return statement gives the factorial function the value of x (which is the value of the factorial of 5 in the example we just used).

Then somewhere else in your program you might do this:

int f;
f = factorial(5);

Which will make the parameter called x have an initial value of 5 and will make f have the final value of the function.

So what does it return? Well, there is undefined behaviour so anything could happen - but because x gets larger and larger it definitely will NOT return the factorial. Anything could happen, but in my tests factorial(5) returns a huge negative number.

Try it online!

So how do we fix it? Well, as @JonathanLeffler said, we can't change the value of x so we need a new variable to hold the result. We will call that variable r:

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

So this program changes the value of r and doesn't change the value of x. So the loop works properly now. But it still doesn't calculate the factorial of the value passed in - if x is 5 it multiplies all the values up to but not including x.

Try it online!

So how do we fix it? The factorial has to include all the values including x, so this actually calculates the factorial:

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

And this works as long as the value of x you pass in is small enough that the factorial can fit into a signed int.

Try it online!

You could get more range by using an unsigned long long but there is still a maximum value that can be calculated.

Answer 3

1. The program loops through integers 1 thru N-1. (Assume the input value is 'N')
2. Before loop starts, x=N.
3. After one iteration, x=N*1.
4. After 2 iterations, x=N*1*2.
5. After N-1 iterations, x=N*1*2*....(N-1).
6. Which is N factorial.

So N! is returned.

Answer 4

The fifth line is : x *= i;

You should understand here : x = x * i;

The loop will execute while i < x. Which means until reaches x - 1;

Knowing that i begins at 1 you will get this sum : x * 1 * 2 * 3 * ... * ( x - 1)

You can rearrange this so you get : 1 * 2 * 3 * ... * (x - 1) * x