Keskustelu: Ohjelmointikysymykset: C: Jännien funktioiden rakentelu

Rakentelin huvikseni neliön, tosin aika karkean ja käytin vielä apumuuttujaa:

inline unsigned long pow2(long n)
{
        volatile unsigned long tulos = 0, apu = n;
        do{
                if(apu & 1){
                        tulos += n;
                }
                n <<= 1;
        } while(apu >>= 1);
        return tulos;
}

Suoritusaikaa tosin menee 6 kertaa enemmän kuin kaavalla n*n laskettaessa miljoonan ensimmäisen luvun neliöt. Onkos vinkkejä nopeuttamiseen? Tuskin tämä funktio pääsee nopeudessa ohi, mutta onhan se kiva oppia uusia menetelmiä.

Edit: Hassua, muuttamalla muuttujat volatileksi sain nipistettyä (keskiarvo kymmenestä toistosta) kolme millisekuntia tuosta miljoonasta suorituksesta :)

Minkälaisia jänniä funktioita olette itse rakennelleet?

Neliön laskemista voi olla hankalaa nopeuttaa, koska perustapa (n*n) on niin nopea.

Tässä on kuitenkin pari vaihtoehtoista toteutusta:

/* kertominen on logaritmien yhteenlasku */
int nelio(int n) {
    return (int)(exp(log(n)+log(n))+.5);
}

/* taulukko valmiiksi lasketuille neliöille */
int nelio[100];

/* neliöiden lasku */
void laske(void) {
    int i;
    for (i = 0; i < 100; i++) nelio[i] = i*i;
}

int main(void) {
    laske();
    /* neliön voi noutaa suoraan taulukosta */
    printf("%i\n", nelio[19]);
}

Kahden potensseille menisi näin näppärästi, ja nyt menee vain 2 kertaa enemmän aikaa kuin kertolaskuun:

static inline unsigned long log2(unsigned long n)
{
        unsigned long tulos = 0;
        asm volatile(
                "bsr %[n], %[tulos]"
                :[tulos] "=r" (tulos)
                :[n] "mr" (n)
        );
        return tulos;
}
inline unsigned long pow2(unsigned long n)
{
        unsigned long tulos = n;
        tulos <<= log2(n);
        return tulos;
}

Piti tosin logaritmiin käyttää assembleria, vastaava hoituisi kaiketi floatiksikin muuttamalla ja ottamalla sieltä eksponentti.

Tällä päästäänkin jo 80 prosenttiin n*n:n suoritusajasta kun turhia hyppyjä on karsittu välistä:

static inline const unsigned long pow2(unsigned long n)
{
        unsigned long tulos = n, apu;
        asm(
                "bsr %[n], %[apu]"
                :[apu] "=r" (apu)
                :[n] "mr" (n)
        );
        tulos <<= apu;
        return tulos;
}

Olisin verrannut funktioon joka käyttää mulia, mutta en viitsinyt alkaa ihmettelemään miksi "suffix or operand is invalid for 'mul'" 8)