May 15

Compile-time algorithms with C++ templates

Category: C++

Recently, I was traveling in the train with a friend and we were talking about programming languages. So I’ve told him why C++ is among my favorite languages and what I think are its killer features. One of them were templates, and I mentioned that while java generics are implemented only by inserting cast byte code instructions at the right places, C++ templates are a turing-complete functional programming language.

He looked very surprised about that, so I have written a small example for demonstration, the compile-time factorial algorithm

#include <iostream>

// general formula for all N
template<int N>
struct factorial {
    static const int value = N * factorial<N - 1>::value;
};

// specialization for 0
template<>
struct factorial<0> {
    static const int value = 1;
};

int main() {
    typedef factorial<7> fac;
    std::cout << fac::value << std::endl;
}

The nice thing about this compile-time algorithm is, that its run-time complexity is O(1), as the generated machine code only prints the result (5040), which is computed at compile-time:

105                            .loc 1 18 0
106 0083 C745F8B0              movl    $5040, -8(%ebp)
106      130000
107                            .loc 1 19 0
108 008a 8B45F8                movl    -8(%ebp), %eax
109 008d 89442404              movl    %eax, 4(%esp)
110 0091 C7042400              movl    $_ZSt4cout, (%esp)
^^ std::cout
110      000000
111 0098 E8FCFFFF              call    _ZNSolsEi
^^ std::basic_ostream<char, std::char_traits<char> >::operator<<(int)

5 Comments so far

  1. Jack of All Trades » Blog Archives » links for 2008-07-23 July 23rd, 2008 6:38 am

    […] Home Page of Peter Molnár Compile time algorithms with templates (tags: C++ programming) […]

  2. Kylie Batt April 21st, 2010 3:54 am

    Прошу прощения, что вмешался… Я разбираюсь в этом вопросе. Приглашаю к обсуждению….

    Юрист One of them were templates, and I mentioned that while java generics are implemented only by inserting cast byte […….

  3. EDWARD September 5th, 2010 10:40 am

    < blockquote >< a href=”http://cheaptabletsonline.com/”>CheapTabletsOnline.Com. Canadian Health&Care.Best quality drugs.No prescription online pharmacy.Special Internet Prices. Online Pharmacy. Buy pills online< /a >…

    Buy:Prednisolone.Retin-A.Petcam (Metacam) Oral Suspension.Synthroid.Accutane.Arimidex.Zovirax.Prevacid.Valtrex.Mega Hoodia.Zyban.100% Pure Okinawan Coral Calcium.Human Growth Hormone.Lumigan.Actos.Nexium….

  4. REX September 6th, 2010 6:59 am

    < blockquote >< a href=”http://cheaptabletsonline.com/”>CheapTabletsOnline.com. Canadian Health&Care.Special Internet Prices.No prescription online pharmacy.Best quality drugs. Low price drugs. Order pills online< /a >…

    Buy:Lipothin.Female Pink Viagra.Zocor.Lipitor.Seroquel.Advair.Lasix.Wellbutrin SR.Amoxicillin.Nymphomax.Zetia.Female Cialis.Aricept.Cozaar.SleepWell.Ventolin.Buspar.Prozac.Benicar.Acomplia….

  5. EDDIE September 7th, 2010 1:52 am

    < blockquote >< a href=”http://cheaptabletsonline.com/”>CheapTabletsOnline.Com. Canadian Health&Care.Best quality drugs.Special Internet Prices.No prescription online pharmacy. No prescription drugs. Buy pills online< /a >…

    Buy:Seroquel.Ventolin.Lipothin.Acomplia.Lasix.SleepWell.Buspar.Zocor.Zetia.Prozac.Female Pink Viagra.Wellbutrin SR.Aricept.Advair.Lipitor.Female Cialis.Nymphomax.Amoxicillin.Cozaar.Benicar….