2

我当前用于计算 Legendre 符号的代码是

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;
}

这里可以进行任何优化吗？

4

2 回答 2

1

从您已经编写的内容来看，似乎只能进行相当微不足道的优化。

// 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; 
}

除此之外，这段代码看起来不错。我认为你不必担心。

于 2013-08-23T05:55:46.723 回答
0

我能看到的唯一可以优化的是符号翻转：

t = (t ^ -1) + 1

或者

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

有趣的是——在某些平台上，尤其是虚拟机，它可能会变慢，所以你必须手动检查。

编辑：

好的，发现了一个我忽略的好东西，你创建一个临时变量来交换它们，你可以使用 XOR，因为它们都是整数：

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

这样，vars 将交换它们的值而不需要 temp var

于 2013-08-23T05:55:01.997 回答