cosTable[] - Pré-calculer les valeurs de sin/cos à l'éxecution

Objectif

Économiser du temps cpu en pré-calculant 512 valeurs de SIN/COS, pour optimiser l’exécution sur des système peu puissant ( ici MIPS R3000 de la PSX ).

La discussion

@NicolasNoble :

Alors, quand tu fais une multiplication 32 bits, sur PC ou sur PSX, le résultat est toujours 64 bits
et quand tu fais des maths en fixed point, quand tu fais une multiplication, tu es obligé de passer en "2x"
la taille d'origine pour pouvoir ajuster le résultat

fixed math signifie par exemple que tu écris 1.5 sous la forme 1.5*1024 = 1536

donc si tu fais 1.5 * 1.5 = 2.25, ça donne 1536 * 1536 / 1024 = 2,359,296 / 1024 = 2304
(et effectivement, 2.25 * 1024 = 2304)

donc dans mon code, je pars sur du fixed point où j'utilise 2^24 comme partie après la virgule 
(et 2^8 pour la partie avant la virgule) donc je suis obligé de diviser par 2^24 après une multiplication
Le calcul de la série est 2 * f(1) * f(n - 1) - f(n - 2), donc je dois ajuster le résultat de la seconde
multiplication en divisant par 2^23 (vu que sinon ça fait un peu con de multiplier par 2 puis de tout rediviser par 2^24)
d'où mon >> 23 dans la formule en C++

donc dans ton cas, il faut savoir quelle précision tu veux utiliser pour pouvoir ajuster

32bits, ça ça génère une table de précision 2048
à savoir 512 entrées dans la table, qui permet un calcul de 0 à 2*pi sur 2048 entrées
(vu que tu peux bricoler en fonction de l'angle où tu te trouves, tu as juste besoin de 512 entrées)

ça se voit là : [https://github.com/grumpycoders/Balau/blob/master/tests/test-Handles.cc##L28-L47](https://github.com/grumpycoders/Balau/blob/master/tests/test-Handles.cc##L28-L47)
donc si tu veux garder la même précision on a juste à recalculer les valeurs initiales pour du fixed point 4096

[https://github.com/grumpycoders/Balau/blob/master/tests/test-Handles.cc##L65-L66](https://github.com/grumpycoders/Balau/blob/master/tests/test-Handles.cc##L65-L66)

C est 64 bits pour forcer le calcul en bas correctement vu que sinon ça overflow
mais le compilateur C fera les choses correctement et gardera tout en 32 bits

costable 0 c'est 1.0 donc 4096 dans ton cas et costable 1 c'est ce que la formule dit:

 4096 * cos(1 * 2pi / 2048) 

Mais ça donne pas une valeur super ça : [https://www.wolframalpha.com/input/?i=4096+*+cos%281+*+2pi+%2F+2048%29](https://www.wolframalpha.com/input/?i=4096+*+cos%281+*+2pi+%2F+2048%29)

Donc, on peut garder la valeur que j'avais au début (2^24)
mais on peut du coup changer ce qu'on renvoie des fonctions cos et sin pour faire un shift du bon nombre de bits
du coup on peut calculer la table en haute précision, et diminuer la précision quand on fait une requête

Le code


// this is from gere : https://github.com/grumpycoders/Balau/blob/master/tests/test-Handles.cc##L20-L102
static int m_cosTable[512];                         
static const unsigned int DC_2PI = 2048;        
static const unsigned int DC_PI  = 1024;
static const unsigned int DC_PI2 = 512;
int ncos(unsigned int t) {
    t %= DC_2PI;
    int r;

    if (t < DC_PI2) {
        r = m_cosTable[t];
    } else if (t < DC_PI) {
        r = -m_cosTable[DC_PI - 1 - t];
    } else if (t < (DC_PI + DC_PI2)) {
        r = -m_cosTable[t - DC_PI];
    } else {
        r = m_cosTable[DC_2PI - 1 - t];
    };

    return r >> 12;                     // We're using 2^24 precision, but returning the value with 2^12 (4096) precision
};

// sin(x) = cos(x - pi / 2)
int nsin(unsigned int t) {
    t %= DC_2PI;

    if (t < DC_PI2){
        return ncos(t + DC_2PI - DC_PI2);
    };
    return ncos(t - DC_PI2);
};
// f(n) = cos(n * 2pi / 2048) <- 2048 == DC_2PI value
// f(n) = 2 * f(1) * f(n - 1) - f(n - 2)
void generate(void){

    m_cosTable[0] = 16777216;               // 2^24 * cos(0 * 2pi / 2048) => 2^24 * 1 = 2^24 : here, 2^24 defines the precision we want after the decimal point
    static const long long C = 16777137;    // 2^24 * cos(1 * 2pi / 2048) = C = f(1);
    m_cosTable[1] = C;

    for (int i = 2; i < 512; i++){
        m_cosTable[i] = ((C * m_cosTable[i - 1]) >> 23) - m_cosTable[i - 2];

        m_cosTable[511] = 0;
    }
};