Compile time calculation

[Darryl]

Hi guys,

Supposing I had a function that generated a list of non continuous numbers, for example fibonnoci sequence, is there a way to generate and store that list at compile time to be use at run time in some other function.

I've been searching the web for compile time/metaprogramming algorithms and most of the ones I've found use enums and then only really to have access to a particular Nth value where I want all the values in a given range available in say a vector.

[Alvaro]

You can combine the usual metaprogramming tricks with a little abuse of macros to get something like what you want.

However, I have a hard time thinking of a situation where this would be a good idea. Normally, you want to compute the table at run time. In certain circumstances (e.g., if the computation is expensive) you can make an auxiliary program that computes the table, dumps it to a file and then your main program reads it at startup.

[Darryl]

It's for a speed contestto generate primes... I wanted it to generate a table of small primes ie < 64k, to be used to find large primes > 2^32, but after actually writing the preliminary program, I have found the small primes generate really fast and the bulk of the time in my program is finding the large primes. I have to find 100000 of them over 2^32 that fits in a 64 bit variable, you got any suggestions? The program I have now does it in about 30 seconds on a older P4 3.0ghz machine.

Here's what I tried...

Code: Select all


#include <iostream>

const size_t ROOTS_NEEDED = 6546; //precalculated

bool is_prime(unsigned __int64* known_primes, unsigned __int64 value)
{   
    for ( size_t i = 0; i < ROOTS_NEEDED; ++i)
    {
        if(known_primes[i]!=0 && value%known_primes[i]==0 ) return false;
        if (known_primes[i]==0)return true;
    }
    return true;
}


void PrimeFunc(unsigned __int64* PrimeList)
{ 
    unsigned __int64 primes[ROOTS_NEEDED] ={3,5,7,11,13,17,19,23,29,31}; // allowed to seed up to 10 numbers
    const unsigned __int64 max_root = 65552; //precalculated
    size_t end = 9;

    while (primes[end]< max_root)
    {
        int inc = 2;
        while (!is_prime(primes,primes[end]+inc))
        {
            inc+=2;
        }
        primes[end+1] = (primes[end]+inc);
        ++end;
    }
    std::cout << "small primes generated\n";


    int index = 0;
    unsigned __int64 begin      = 0x00000000ffffffffui64;
    unsigned __int64 finish        = 0xffffffffffffffffui64;

    while (begin < finish)
    {
         if (is_prime (primes,begin))
         {
             PrimeList[index++] = begin;
             if (index == 100000)return;
         }
         begin+=2;
    }
}

int main()
{
    unsigned __int64 test[100000];
    PrimeFunc(test);
    int n = 0;
    do
    {     

        std::cout << "Enter Number> ";
        std::cin >> n;
        std::cout << test[n] << "\n";

    }while (n !=0);
}


[Alvaro]

Here's an example of how to populate a list in compile time with some abuse of macros:
[syntax="cpp"]#include <iostream>

#define DL8(x) CompileTimeBitCount<x>::value
#define DL7(x) DL8(3*(x)),DL8(3*(x)+1),DL8(3*(x)+2)
#define DL6(x) DL7(3*(x)),DL7(3*(x)+1),DL7(3*(x)+2)
#define DL5(x) DL6(3*(x)),DL6(3*(x)+1),DL6(3*(x)+2)
#define DL4(x) DL5(3*(x)),DL5(3*(x)+1),DL5(3*(x)+2)
#define DL3(x) DL4(3*(x)),DL4(3*(x)+1),DL4(3*(x)+2)
#define DL2(x) DL3(3*(x)),DL3(3*(x)+1),DL3(3*(x)+2)
#define DL1(x) DL2(3*(x)),DL2(3*(x)+1),DL2(3*(x)+2)
#define DL0 DL1(0),DL1(1),DL1(2)

template <int n>
struct CompileTimeBitCount {
static const int value=CompileTimeBitCount<n/2>::value+(n%2);
};

template <>
struct CompileTimeBitCount<0> {
static const int value=0;
};

int bit_count[6561]={DL0};

int main() {
std::cout << bit_count[4097] << '\n';
}
[/syntax]