Compile time calculation

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

Compile time calculation

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.

Darryl

Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

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.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

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; //precalculatedbool 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);}`

Darryl

Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

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]

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA