fbpx

C++: Compile-Time Calculation

Bjarne-stroustrup
 

Some programming languages allow calculation of values at compile time. For this task, calculate 10! at compile time. Print the result when the program is run.

This is called Template metaprogramming. In fact, templates in C++ are Turing-complete, making deciding whether a program will compile undecidable.

#include <iostream>

template<int i> struct Fac
{
	static const int result = i * Fac<i-1>::result;
};

template<> struct Fac<1>
{
	static const int result = 1;
};


int main()
{
	std::cout << "10! = " << Fac<10>::result << "\n";
	return 0;
}

Compile-time calculations in C++ look quite different from normal code. We can only use templates, type definitions and a subset of integer arithmetic. It is not possible to use iteration. C++ compile-time programs are similar to programs in pure functional programming languages, albeit with a peculiar syntax.

Works with: C++11

Alternative version, using constexpr in C++11:

#include <stdio.h>

constexpr int factorial(int n) {
	return n ? (n * factorial(n - 1)) : 1;
}

constexpr int f10 = factorial(10);

int main() {
	printf("%d\n", f10);
	return 0;
}

Output:

3628800

The asm produced by G++ 4.6.0 32 bit (-std=c++0x -S), shows the computation is done at compile-time:

_main:
	pushl	%ebp
	movl	%esp, %ebp
	andl	$-16, %esp
	subl	$16, %esp
	call	___main
	movl	$3628800, 4(%esp)
	movl	$LC0, (%esp)
	call	_printf
	movl	$0, %eax
	leave
	ret

SOURCE

Content is available under GNU Free Documentation License 1.2.