c - 为什么使用 unsigned int 的模数比使用 unsigned long long 的模数运行得更快？

Question

为什么要测试取模速度？

<小时/>

我有一个应用程序，模数运算每秒执行数百万次。我必须处理非常大的数字，因此我选择 unsigned long long 作为数据类型。大约一周前，我为我的应用程序编写了一种新算法，该算法需要对比我以前使用的数字小得多的数字执行模数运算(例如26而不是10000000)。我选择使用 unsigned int 作为数据类型。 速度显着提高，而算法几乎相同。

测试...

<小时/>

我用 C 语言编写了两个简单的程序来测试模数计算的速度。

#include <stdio.h>

typedef unsigned long long ull;

int main(){
   puts("Testing modulus with ull...");
   ull cnt;
   ull k, accum=0;
   for(k=1, cnt=98765432;k<=10000000;++k,--cnt) 
      accum+=cnt%80;
   printf("%llu\n",accum);
   return 0;
}

我唯一要更改的是名为 cnt 的变量的类型。

我用time ./progname测试了这些程序，结果如下。

• 使用unsigned long long:3.28秒
• 使用 unsigned int:0.33 秒

注意:我正在越狱的 iPad 上测试它，这就是为什么它需要这么多时间。

为什么？

<小时/>

为什么带有 unsigned long long 的版本需要这么长时间才能运行？

更新1:将--cnt添加到循环中，因此cnt%80不会是常量；结果还是一样。

更新2:删除了printf并添加了accum以消除printf占用的时间；现在的结果要少得多，但仍然有很大不同。

Answer 1

从根本上讲，执行算术运算所需的时间至少与操作数中的位数成线性。对于现代 CPU，当操作数适合寄存器时，加法、减法、逻辑运算以及乘法的时间是恒定的(通常是一个周期)，但是扩展到 RSA 数量级或其他“bignum”用法，您将清楚地看到执行算术的时间如何衡量。

在除法和求余运算的情况下，它们本质上成本更高，并且通常您会注意到不同操作数大小的显着差异。当然，如果您的 cpu 是 32 位，则执行 64 位除法/求余运算将涉及通过多个较小的运算构建它(很像“bignum”算术的小型特例)，因此它将是速度慢得多。

但是，您的测试完全无效。除法是恒定的，因此甚至不应该在每次循环迭代时重新计算，循环中花费的时间应该由 printf 和您与 printf 一起使用的格式说明符主导code> 对于打印 unsigned long long 类型的参数无效，因此您的程序具有未定义的行为。