为什么要测试取模速度?
<小时/>我有一个应用程序,模数运算每秒执行数百万次。我必须处理非常大的数字,因此我选择 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
占用的时间;现在的结果要少得多,但仍然有很大不同。
最佳答案
从根本上讲,执行算术运算所需的时间至少与操作数中的位数成线性。对于现代 CPU,当操作数适合寄存器时,加法、减法、逻辑运算以及乘法的时间是恒定的(通常是一个周期),但是扩展到 RSA 数量级或其他“bignum”用法,您将清楚地看到执行算术的时间如何衡量。
在除法和求余运算的情况下,它们本质上成本更高,并且通常您会注意到不同操作数大小的显着差异。当然,如果您的 cpu 是 32 位,则执行 64 位除法/求余运算将涉及通过多个较小的运算构建它(很像“bignum”算术的小型特例),因此它将是速度慢得多。
但是,您的测试完全无效。除法是恒定的,因此甚至不应该在每次循环迭代时重新计算,循环中花费的时间应该由 printf
和您与 printf
一起使用的格式说明符主导code> 对于打印 unsigned long long
类型的参数无效,因此您的程序具有未定义的行为。
关于c - 为什么使用 unsigned int 的模数比使用 unsigned long long 的模数运行得更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31101489/