Calculate Fibonacci At C++ Compile Time – C++ Template metaprogramming

I was asked a question about calculate the Fibonacci number at the compile time not at run time in C++.

Initially, I have no idea about how to solve this problem, how to make the calculation happen in the compile time? Then the key solution is: Using Template.

Template metaprogramming can make compile-time class generation, and also can perform polymorphism in a static, which is well-known as the Curiously Recurring Template Pattern (CRTP).

So the solution is listed as following:

 

<br />
template&lt;int N&gt;<br />
class Fibonacci {<br />
public:<br />
    enum { value = Fibonacci&lt;N-1&gt;::value + Fibonacci&lt;N-2&gt;::value };<br />
};</p>
<p>template&lt;&gt;<br />
class Fibonacci&lt;1&gt; {<br />
public:<br />
    enum { value = 1 };<br />
};</p>
<p>template&lt;&gt;<br />
class Fibonacci&lt;0&gt; {<br />
public:<br />
    enum { value = 0 };<br />
};</p>
<p>int main() {<br />
    int i =  Fibonacci&lt;6&gt;::value;<br />
    return i;<br />
}<br />

Compile it to assembly “g++ -O2 -S Fibonacci_template.cpp

 

<br />
_main:                                  ## @main<br />
	.cfi_startproc<br />
## BB#0:<br />
	pushq	%rbp<br />
Ltmp0:<br />
	.cfi_def_cfa_offset 16<br />
Ltmp1:<br />
	.cfi_offset %rbp, -16<br />
	movq	%rsp, %rbp<br />
Ltmp2:<br />
	.cfi_def_cfa_register %rbp<br />
	movl	$8, %eax<br />
	popq	%rbp<br />
	retq<br />
	.cfi_endproc<br />

 

You can find: The assembly output (Line 12) is compiled into the exact number of Fibonacci(6) is to be 8.

Leave a Reply

Your email address will not be published. Required fields are marked *