Computing factorials

I am computing factorials as part of teaching myself C++. I am looking for feedback on efficiency, style and any bad practices I may be using.

#include <iostream>
#include <climits>

using namespace std;

int main()
{
unsigned int number{ 0 };
unsigned long long factorial{ 0 };
cout << "The factorial of a non-negative integer n is denoted as n! (n factorial)...\n" <<
"Example: 5! = 5x4x3x2x1 = 120\n\n";

cout << "Enter a non-negative integer and we will compute the factorial: ";
cin >> number;
while (cin.rdstate() || number < 0 || number > LLONG_MAX)
{
cin.clear();
cin.ignore(LLONG_MAX, '\n');//flush input buffer
cout << "The data entered was invalid. Try again?\n\n" << endl;
cout << "Enter a non-negative integer and we will compute the factorial: ";
cin >> number;
}
if (number == 0 || number == 1)//since 0! and 1! = 1 there is no need to do a calculation
{
cout << "!" << number << " = 1" << endl;
}
else
{
factorial = number * (number - 1);
for (size_t i = 2; i < number; ++i)
{
factorial *= (number - i);
}
cout << number << "! = " << factorial << endl;
}
}

You should separate the computation code from the input/output code. As you have written it, the factorial computation code will never be reusable in any other program. To be specific, you should define an unsigned long long factorial(int n) function.

You have a formatting bug in the special case:

!0 = 1

In fact, you should structure your code to avoid the need for special cases altogether.

unsigned long long factorial(int n) {
unsigned long long result = 1;
while (n > 1) {
result *= n--;
}
return result;
}

I have found a couple of things that could help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Decompose the program into smaller parts

Right now, all of the code is in main which isn't necessarily wrong, but as others have pointed out, it means that it's not only hard to reuse but also hard to troubleshoot. Better is to separate the code into small chunks. It makes it both easier to understand and easier to fix or improve.

Fix notation on output

The code prints !0 and !1 instead of 0! and 1! for those two numbers. Fortunately, that's a very simple fix.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Sanitize user input better

The code doesn't quite work as posted. If I compile and run the program on my 64-bit Linux machine and enter -5 as the input, the program just hangs. The code attempts to verify the input, but doesn't quite get it right.

unsigned int number{ 0 };
// ...
cin >> number;
while (cin.rdstate() || number < 0 || number > LLONG_MAX)

There are a couple of problems with this. First, let's consider the range that number can take. Since it's an unsigned number, it can't ever be less than zero, so we can eliminate that part entirely. Second, because it's an unsigned int and not a long long it's unlikely (even on a 64 bit machine like mine) that it's even possible to have a number that large stored in an unsigned int, so we can eliminate that one as well. That leaves us with cin.rdstate() which is true if the eofbit or badbit or failbit is asserted. However, there's a more idiomatic C++ way to express almost that same thing:

while (!(cin >> number))

This relies on the operator bool member function which returns false if either failbit or badbit are set. In a real program, I think I would want the program to simply exit if I sent it an empty file.

Consider using the user's preferred locale

Different countries and cultures use different formatting for large numbers. For example, in Germany, one might write one thousand as 1.000 while in the US, this would typically be written as 1,000 with a separator for each three digits. This can make large numbers easier to read and is very easy to implement in C++. Just #include <locale> and add a single line:

std::cout.imbue(std::locale{""});

Because of the nature of the factorial operation, the numbers get very big very quickly. So big, in fact that they overflow the size of even an unsigned long long even with numbers well under 100. At the moment, the code simply returns 0. So the code erroneously claims that $100! = 0$. We know that can't be right. So what is the maximum number that is correctly calculated? We could attempt to address this in a number of different ways. We could:

1. manually go through with successively higher integers until the program fails
2. write a separate program to calculate the maximum permissable input value
3. use math, such as perhaps Stirling's approximation to calculate it
4. incorporate a compile-time constant that the compiler itself calculates

If we do 1 or 2 or even 3, there is a risk that it will work on my computer and compiler but not with yours or vice versa, so option 4 is the most appealing, but how shall we do it? Fortunately, C++11 has a new keyword, constexpr which we can use to answer this question. The following steps show how this is done:

Write factorial as a constexpr function

We want to use factorial as a constexpr function, so the most straightforward way is to do it as a recursive function:

constexpr unsigned long long factorial(unsigned n)
{
return (n == 0) ? 1 : n*factorial(n-1);
}

This attempts to calculate a factorial, but still will give incorrect answers on overflow. We can use this fact to accomplish the next step.

Write a constexpr function to find the maximum correct input

We know that for all values of $n$ it must be true that $(n+1)! \ge n!$. In other words, if we step through the integers, factorial(n) had better be less than or equal to factorial(n+1) unless we have encountered an overflow. This suggests an easy way to test:

constexpr unsigned max_fact(unsigned n)
{
return (factorial(n) <= factorial(n+1)) ? max_fact(n+1) : n;
}

Unfortunately, this can fail because it may allow numbers that don't actually yield a correct result. On my machine, it claims to be able to calculate up to $22!$ but in fact, overflow occurs at $21!$. A more accurate function is this:

constexpr unsigned max_fact(unsigned n)
{
return (factorial(n+1)/factorial(n) == n+1) ? max_fact(n+1) : n;
}

It simply uses the definition of the factorial function to verify.

Define a constant for the max allowable input value

This is the easiest part.

const unsigned MAX_FACT_INPUT = max_fact(0);

Put it all together

Now that we have all of the pieces, here's what the code looks like when we put it all together:

#include <iostream>
#include <locale>

constexpr unsigned long long factorial(unsigned n)
{
return (n == 0) ? 1 : n*factorial(n-1);
}

constexpr unsigned max_fact(unsigned n)
{
return (factorial(n) <= factorial(n+1)) ? max_fact(n+1) : n;
}

const unsigned MAX_FACT_INPUT = max_fact(0);

int main()
{
unsigned int number;
std::cout.imbue(std::locale{""});
std::cout << "The factorial of a non-negative integer n is denoted as n! (n factorial)...\n"
"Example: 5! = 5x4x3x2x1 = 120\n\n"
"Enter a non-negative integer no greater than " << MAX_FACT_INPUT
<< " and we will compute the factorial: ";
if (std::cin >> number && number <= MAX_FACT_INPUT) {
std::cout << number << "! = " << factorial(number) << '\n';
} else {
std::cout << "Sorry, I can't compute that.\n";
}
}

Sample output:

The factorial of a non-negative integer n is denoted as n! (n factorial)...
Example: 5! = 5x4x3x2x1 = 120

Enter a non-negative integer no greater than 20 and we will compute the factorial: 20
20! = 2,432,902,008,176,640,000
• Very detailed answer, +1. Just a minor question: Any particular reason for not making MAX_FACT_INPUT a constexpr as well? – glampert Nov 3 '14 at 22:20
• It could also have been constexpr and arguably should be. My compiler happens to be smart enough to figure it out, but a hint wouldn't hurt. – Edward Nov 3 '14 at 22:29
using namespace std;

This is a bad practice to adopt, see here for why.

You have an awful lot of code in main. Usually you want to put most of the programming logic outside main so that it's easy to reuse the code.

if (number == 0 || number == 1)//since 0! and 1! = 1 there is no need to do a calculation
{
cout << "!" << number << " = 1" << endl;
}
else
{
factorial = number * (number - 1);
for (size_t i = 2; i < number; ++i)
{
factorial *= (number - i);
}
cout << number << "! = " << factorial << endl;
}

i should be the same type as number, since you are comparing and subtracting on them. However, you can replace this entire section with

std::cout << number << "! = " << factorial(number) << endl;

Note: endl flushes output. This may not be what you want to do in all cases (although it would be correct if unnecessary here).

Now define the factorial function:

unsigned long long factorial(unsigned int number) {
unsigned long long product = 1;

// if number is 0 or 1, this loop will never run
// correctly giving 0! = 1! = 1
for ( ; number > 1; number-- ) {
product *= number;
}

return product;
}
• A tiny nitpick but I initially misread your comment as "will never run correctly, giving..." rather than "will never run, correctly giving..." – Chris Nov 3 '14 at 12:10
• I disagree with your assertion that using namespace std; is a bad practice to adopt, but don't take my word for it, take Herb Sutter's and Andrei Alexandrescu's: stackoverflow.com/a/26722134/139091 – mattnewport Nov 3 '14 at 20:03

Factorial is used as one of those introductory lessons to recursion. It's a shame that you don't use recursion here. As an added bonus, by using recursion, you take the factorial code out of the main method, and reduce your multi-responsibilities on the main method too:

unsigned long long factorial(unsigned int number) {
if (number == 0) {
return 1;
}
return number * factorial(number - 1);
}

Note that the special-case for 0 is built in to the recursive method too. This reduces the code requirement in the handler as well.

The next logical step is to take the user-input and put it in a separate method, leaving something like:

int main()
{
unsigned int number = getUserInput();
cout << number << "! = " << factorial(number) << endl;
}

Excluding the user input, the code would look like this in Ideone

• What advantage does he get from using recursion? There are many situations where recursion could be used, but will fail fatally. Well known example Fibonacci numbers. Less well known example Pascal triangle. Obvious example adding numbers from 1 to n. So what makes this different? – gnasher729 Nov 3 '14 at 17:16
• @gnasher729 The use of recursion, or not, is not hugely important, other than, as I say, it is a good simple example of where recursion can be used. The downsides of recursion (stack overflows, etc.) are not important here in this function because other limiting factors come in to play first (and they are not checked in any of the solutions presented so far). The largest factorial number storable in the 64bit result is.... 22!, or is it 23!... Regardless, it's far, far away from any point where stack overflow or performance are a concern. – rolfl Nov 3 '14 at 18:22