Does it gets faster than this?

Question

My current code for computing the legendre symbol is

inline int legendre(int pa, int pm){
    register unsigned int a = pa;
    register unsigned int m = pm;
    int t = 1;
    int tmp=0;
    while (a>1) {
        tmp=__builtin_ctz(a);//a=x*2^tmp, where x is odd
        a>>=tmp;
        if(tmp&1 &&((m&7)==3 || (m&7)==5))//if it is an odd power and m=3,5 mod 8
            t=-t;//invert result
        if((a&3)==3 && (m&3)==3)//if m=3 mod 4 and a=3 mod 4
            t=-t;//invert result
        m %= a;
        tmp=a;
        a=m;
        m=tmp;//exchange variables
    }
    if (m == 1) return t;
    return 0;
}

Is any optimisation possible here?

Answer 1

From what you've already written, it looks like only fairly negligible optimizations can be made.

// Get rid of the inline, it's pointless for functions this large.
// Some compilers might remove the inline for big functions.
int legendre(int pa, int pm){

// Rather than creating variables here, you COULD make global
// variables and assign them here. That would get rid of some
// time taken creating these local variables.
register unsigned int a = pa;
register unsigned int m = pm;
int t = 1;
int tmp=0;
while (a>1) {
    tmp=__builtin_ctz(a);//a=x*2^tmp, where x is odd
    a>>=tmp;

    // This just throws both if-statements into one.
    if((tmp&1 &&((m&7)==3 || (m&7)==5))
       || ((a&3)==3 && (m&3)==3)) t = -t;
    m %= a;
    tmp=a;
    a=m;
    m=tmp;//exchange variables
}
if (m == 1) return t;
return 0; 
}

Aside from that, this code looks fine. I don't think you'll have to worry about it.

Answer 2

The only possible thing that I could see can be optimized is the sign flipping:

t = (t ^ -1) + 1

or

t = ~t + 1; // I don't prefer this one

The funny thing is - it can be slower on some platforms, especially virtual machines, so you manually have to check.

EDIT:

OK, found a good thing that I overlooked, you create a temp variable to exchange them, you can use XOR for that, since they're both integers:

m = m^a;
a = a^m;
m = m^a;

that way the vars will exchange their values with no need for temp var