Calculating and Printing Factorial at Compile Time in C++

Calculating and printing factorial at compile time in C++

The factorial can be printed in compiler-generated message as:

template<int x> struct _;
int main() {
        _<Factorial<10>::value> __;
        return 0;
}

Error message:

prog.cpp:14:32: error: aggregate ‘_<3628800> __’ has incomplete type and cannot be defined
_::value> __;
^

Here 3628800 is factorial of 10.

See it at ideone : http://ideone.com/094SJz

So are you looking for this?

---

EDIT:

Matthieu asked for a clever trick to both print the factorial AND let the compilation continue. Here is one attempt. It doesn't give any error, hence the compilation succeeds with one warning.

template<int factorial> 
struct _{ operator char() { return factorial + 256; } }; //always overflow
int main() {
        char(_<Factorial<5>::value>());
        return 0;
}

It gets compiled with this warning:

main.cpp: In instantiation of '_::operator char() [with int
factorial = 120]': main.cpp:16:39: required from here
main.cpp:13:48: warning: overflow in implicit constant conversion
[-Woverflow] struct _{ operator char() { return factorial + 256; } };
//always overflow

Here 120 is factorial of 5.

Demo at ideone : http://coliru.stacked-crooked.com/a/c4d703a670060545

You could just write a nice macro, and use it instead as:

#define PRINT_AS_WARNING(constant) char(_<constant>())    

int main() 
{
         PRINT_AS_WARNING(Factorial<5>::value);
         return 0;
}

That looks great.

Is it possible to calculate number factorial at compile time, but without enums

While there are alternative notations, It's written that way because more compilers accept that enum-style notation. The language supports const integral-type class members with an inline initialization, but some compilers aren't compliant with the standard in that regard. On compilers that are compliant in this regard, the following works just fine:

#include <iostream>
template <unsigned int n>
struct fact
{   
    static const unsigned int value = n*fact<n-1>::value;
};  

template<>
struct fact<0>
{   
    static const unsigned int value = 1;
};  

int main()
{   
    std::cout << fact<10>::value << "\n";
}   

Printing sizeof(T) at compile time

Yes. The possible duplicate prints the size as error message, which means the compilation will not succeed.

However, my solution prints the size as warning message, which means, it will print the size, and the compilation will continue.

template<int N> 
struct print_size_as_warning
{ 
   char operator()() { return N + 256; } //deliberately causing overflow
};

int main() {
        print_size_as_warning<sizeof(int)>()();
        return 0;
}

Warning message:

prog.cpp: In member function ‘char print_size_as_warning<N>::operator()() [with int N = 4]’:
prog.cpp:8:   instantiated from here
prog.cpp:4: warning: overflow in implicit constant conversion

Demo : http://www.ideone.com/m9eg3

Note : the value of N in the warning message is the value of sizeof(int)

---

The above code is improved one, and my first attempt was this:

template<int N> 
struct _{ operator char() { return N+ 256; } }; //always overflow

int main() {
        char(_<sizeof(int)>());
        return 0;
}

Warning message:

prog.cpp: In member function ‘_<N>::operator char() [with int N = 4]’:
prog.cpp:5:   instantiated from here
prog.cpp:2: warning: overflow in implicit constant conversion

Demo : http://www.ideone.com/mhXjU

The idea is taken from my previous answer to this question:

• Calculating and printing factorial at compile time in C++

Factorial with while loop in C

Firstly, scanf expects the address of Wert, not its value, and also update your while loop to compare with 1. Here's the fixed version:

#include <stdio.h>

int main(void)
{
    int Wert;
    int fak = 1;

    scanf ("%d", &Wert);

    while ( Wert > 1 ) {
        fak = fak * Wert;
        Wert = Wert - 1;
    }
    printf ("%d", fak);
}

Input:

5

Output:

120

But since factorials easily overflow integers, it may be a better idea to use double instead:

#include <stdio.h>

double fact(double d)
{
    if (d < 1.0)
        return 1.0;
    return d * fact(d - 1.0);
}

int main(void)
{
    double d = 0;
    if (scanf("%lf", &d) != 1) {
        perror("Failed to read stdin");
        return -1;
    }
    printf("%lf! = %lf", d, fact(d));
    return 0;
}

Input:

100

Output:

100.000000! = 93326215443944102000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.000000

Just keep in mind that floating point math is broken.

C program to find the sum of factorials

There are some mistakes in your code.

The first one, is very common when we start learning C

1 / fact must be replaced by 1.0f / fact

Why? Because in C, 1 / 2 is performed using integer arithmetic and returns 0. If you want to perform computation using floating numbers you must force at least one argument being a floating number, this can be done by 1.0/2, 1/2.0 or 1.0/2.0. The previous expressions will be evaluated using double floating number type (which is the C default type for floating number). If you want to use simple precision floating numbers, float, you can use 1.0f

the second one is certainly an inadvertent error:

sum += fact; must be replace by sum += term;

---

Here is a "working" code

#include <stdio.h>

void
main()
{
  /*Any problems with the variables ?*/

  int i, lim, fact = 1;
  float sum = 0.0, term;

  printf("Enter the limit for the sum of series: ");
  scanf("%d", &lim);

  /*Any problems in the loop ? */

  for (i = 1; i <= lim; i++)
  {
    fact *= i;
    term = 1. / fact; /* instead of 1/fact */
    sum += term;      /* instead of sum += fact */
  }

  printf("%f is the sum of the series\n", sum);
}

Enter the limit for the sum of series: 5

1.716667 is the sum of the series

---

There is a more subtle error. By instance, if you want lim = 50,

Enter the limit for the sum of series: 50

inf is the sum of the series

The reason is that 50! is way too big to be stored in an int.

The solution is to compute directly 1/i! using floating number (and not i! using int then 1/i!)

A modified program, that also uses double for an higher precision is :

#include <stdio.h>

void
main()
{
  /*Any problems with the variables ?*/

  int lim;
  double sum = 0.0, term = 1.0;

  printf("Enter the limit for the sum of series: ");
  scanf("%d", &lim);

  /*Any problems in the loop ? */

  for (int i = 1; i <= lim; i++)
  {
    term = term / i;
    sum += term;
  }

  printf("%f is the sum of the series\n", sum);
}

that now works, even when lim=50

---

Do not be discouraged by these mistakes. These are mistakes we all made when we learned C !

---

Expected result:

exp(1) = exp(0) + sum_{i=1}^\infty 1/i!

thus your expected result is exp(1)-exp(0) = 1.718281828459045....

Calculate the factorial of an arbitrarily large number, showing all the digits

GNU Multiprecision library is a good one! But since you say using of external libraries are not allowed, only way I believe its possible is by taking an array of int and then multiplying numbers as you do with pen on paper!

Here is the code I wrote some time back..

#include<iostream>
#include<cstring>

int max = 5000;

void display(int arr[]){
    int ctr = 0;
    for (int i=0; i<max; i++){
        if (!ctr && arr[i])         ctr = 1;
        if(ctr)
            std::cout<<arr[i];
    }
}

void factorial(int arr[], int n){
    if (!n) return;
    int carry = 0;
    for (int i=max-1; i>=0; --i){
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i]/10;
        arr[i] %= 10;
    }
    factorial(arr,n-1);
}

int main(){
    int *arr = new int[max];
    std::memset(arr,0,max*sizeof(int));
    arr[max-1] = 1;
    int num;
    std::cout<<"Enter the number: ";
    std::cin>>num;
    std::cout<<"factorial of "<<num<<"is :\n";
    factorial(arr,num);
    display(arr);
    delete[] arr;
    return 0;
}

'arr' is just an integer array, and factorial is a simple function that multiplies the given number to the 'large number'.

Hope this solves your query..

C program for calculating the value of e

For more precision I would use double instead of float.

for (i=1; i<=n, i++)
    e= 1+1/factorial(i);

This is wrong, you are not adding to e, you are assigning always the last
value of the series, which is always 0 (except for i = 1). So your e will
always be 1.

factorial is a function that returns an int. A int divided by an int is
an int and in C anything 1/x (for x > 1, x integer) is 0. You you to use
1.0 or cast at least one of the arguments to double (or float if you are
using floats):

double e = 1; // initializing e

for(i = 1; i <= n; ++i)
    e += 1.0/factorial(i);

Also, the value of 1/n! must be calculated until it's value is smaller than epsilon, also entered by the user.

I don't understand what that means, if n is a fixed value given by the user,
what do you keep calculating? Is this really what the exercise says?

My interpretation would be: if by n steps |e_real - e_calculated| > epsilon,
keep incrementing n, otherwise stop. That would be

#include <stdio.h>
#include <math.h>
#include <stdint.h>

uint64_t factorial (uint64_t i)
{
    if (i==0)
        return 1;
    else
        return i*factorial(i-1);
}

int main(void)
{
    int n;
    double e = 1;
    double epsilon;

    printf("what is the value of epsilon: ");
    scanf("%lf", &epsilon);

    printf("what is the value of n: ");
    scanf("%d",&n);

    int i = 1;
    while(1)
    {
        e += 1.0/factorial(i++);

        if(i >= n && (fabs(e - M_E) < epsilon))
            break;
    }

    printf("e: %.20lf, calculated e: %.20lf, error: %.20lf, steps: %d\n", M_E, e, fabs(e-M_E), i);

    return 0;
}

Note: if you are using GCC, you have to compile it with the -lm option:

$ gcc e.c -oe -lm

3 Function plus Main Function C Program calculating and displaying a Factorial

First of all, you should change your call to GetData to :

GetData(&x);

as you want to pass a pointer. Then, its declaration should change to :

void GetData(int *x)
{
    printf("Please enter a number:\n");
    scanf("%d%*c", x);
}

Then, you should return variable factorial instead of x. Change line :

return(x);

to :

return(factorial);

and consequently call Factorial function as follows :

factorial = Factorial(x);

as right now, variable factorial is uninitialized, and by passing it to Factorial you will be getting garbage, as you said.

calculating factorial using template meta-programming

• What is this weird template that takes <int N>?

In C++, template arguments can either be types (prefixed with class or typename) or integers (prefixed with int or unsigned int). Here we are in the second case.

• What is this second weird template <>?

template<> struct Factorial<0> is a complete specialization of Factorial class template, which means that 0 is considered a special value to which corresponds its own version of Factorial.

• What are the enums for?

enums are the way to compute values in metaprogramming C++

• What is the advantage of using this rather than normal runtime factorial calculation?

The reason why this code was created in the first place is to create a proof of concept that calculus can be done using metaprogramming. The advantage is that generated code is extremely efficient (calling Factorial<4>::value is equivalent to simply writing "24" in your code.

• How often do you people use this? I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

Such functionality is rarely achieved using this method, but metaprogramming is used more and more nowadays. See Boost meta-programming library to get a hint of what can be done.

---

Related Topics