c - C 中素数测试的 int 与 unsigned long long 的性能

Question

为什么对unsigned long long执行操作需要更长的时间比int ？

I've使用完全相同的代码使用函数查找第 n 个素数进行了多次测试，我不需要提供代码，您可以简单地说:为什么 int 会这样？/2比 unsigned long long 花费的时间更少/2 ？

我知道/ 2意味着强制转换为 unsigned long long .

这是代码:

int isPrime(int number) {
    if (number < 2) return 0;
    if (number == 2) return 1;
    if (number == 3) return 1;
    if (number == 5) return 1;
    if (!(number % 2)) return 0;
    if (!(number % 3)) return 0;
    if (!(number % 5)) return 0;
    if (number < 7 * 7) return 1;
    int step[] = { 7, 11, 13, 17, 19, 23, 29, 31 };
    int sentry = (int)sqrt((double)number);
    for (int r = 0; r < sentry; r += 30)
        for (int i = 0; i < 8; ++i)
            if (!(number % (r + step[i])))
                return 0;
    return 1;
} 

Answer 1

int 和 unsigned long long 很可能具有不同的大小。根据 CPU 架构和编译器设置，不同大小的整数的算术运算的执行效率可能会或多或少。

在没有看到任何代码的情况下，很难确定哪个操作可能会导致您所描述的性能差异。在 unsigned long long 上除以 2 实际上可能比在 int 上更有效，因为它总是可以实现为向右移动 1 位的单个位移位。如果未知该值为正值，则需要进行调整。

其他操作在 64 位值上可能比在 32 位值上花费更长的时间，例如乘法和除法或模运算，这可能是实现中的瓶颈。

您的代码使用了许多除法和模运算，这些在 unsigned long long 上比在 int 值上成本最高，特别是对于未编译除法的最后一个循环作为乘法。

请注意，通过这样定义step可以稍微提高效率:

static const int step[] = { 7, 11, 13, 17, 19, 23, 29, 31 };

还要注意，混合浮点运算和整数算术可能不是很有效，并且如果数字很大sqrt((double)number)实际上可能是不正确的unsigned long long 因为将 64 位整数转换为 53 位浮点尾数时精度损失。

这是一个测试较少的替代方案:

typedef unsigned long long int num_t;

#define PBITS64  ((1<<2) | (1<<3) | (1<<5) | (1<<7) | (1<<11) | (1<<13) | \
                  (1ULL<<17) | (1ULL<<19) | (1ULL<<23) | (1ULL<<29) | \
                  (1ULL<<31) | (1ULL<<37) | (1ULL<<41) | (1ULL<<43) | \
                  (1ULL<<47) | (1ULL<<53) | (1ULL<<59) | (1ULL<<61)
#define REMBITS30  ((1<<1) | (1<<7) | (1<<11) | (1<<13) | \
                    (1UL<<17) | (1UL<<19) | (1UL<<23) | (1UL<<29))

int isPrime(num_t number) {
    /* test all numbers below 64 */
    if (number < 64) return (PBITS64 >> number) & 1;
    /* test all multiples of 2, 3 and 5 */
    if (!((REMBITS30 >> (number % 30)) & 1)) return 0;
    static unsigned int const step[] = { 7, 11, 13, 17, 19, 23, 29, 31 };
    for (num_t r = 0; r * r < number - 16; r += 30) {
        for (int i = 0; i < 8; ++i) {
            if (!(number % (r + step[i])))
                return 0;
        }
    }
    return 1;
}

对于较小的数字以及 2、3 和 5 的倍数，此方法要快得多，它适用于所有 unsigned long long。