-4

为什么要测试模数速度？

我有一个应用程序，模数运算每秒执行数百万次。我必须处理非常大的数字，所以我选择了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不会保持不变；还是一样的结果。

Update2：删除printf并添加accum以消除所花费的时间printf；现在的结果要少得多，但仍然有很大不同。

4

2 回答 2

2

从根本上说，执行算术运算所需的时间量至少与操作数中的位数成线性关系。对于现代 CPU，当操作数适合寄存器时，加法、减法、逻辑运算和乘法的时间是恒定的（通常是一个周期），但扩展到 RSA 数量级或其他“bignum”使用，你会清楚地看到如何执行算术标度的时间。

在除法和余数运算的情况下，这些运算本质上成本更高，并且您通常会注意到不同操作数大小的显着差异。当然，如果您的 cpu 是 32 位的，那么进行 64 位除法/余数运算将涉及从多个较小的运算中构造它（很像“bignum”算术的一个小特例），所以它将是相当慢。

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

于 2015-06-28T15:40:29.680 回答
1

假设是 32 位系统，区别在于 64 位与 32 位的模运算。

ull cnt;

结果（使用-O2优化）：

.L2:
    pushl   $0
    pushl   $80
    pushl   %edi
    pushl   %esi
    call    __umoddi3           ; note the function call here
    addl    $16, %esp
    addl    %eax, -32(%ebp)
    adcl    %edx, -28(%ebp)
    addl    $-1, %esi
    movl    %esi, %eax
    adcl    $-1, %edi
    xorl    $88765432, %eax
    orl     %edi, %eax
    jne     .L2
    pushl   -28(%ebp)
    pushl   -32(%ebp)
    pushl   $.LC1
    pushl   $1
    call    __printf_chk

尽管

unsigned int cnt;

结果（也使用 -O2 优化）：

.L2:
    movl    %ecx, %eax
    mull    %ebx
    shrl    $6, %edx
    leal    (%edx,%edx,4), %eax
    movl    %ecx, %edx
    sall    $4, %eax
    subl    %eax, %edx
    movl    %edx, %eax
    xorl    %edx, %edx
    addl    %eax, %esi
    adcl    %edx, %edi
    subl    $1, %ecx
    cmpl    $88765432, %ecx
    jne     .L2
    pushl   %edi
    pushl   %esi
    pushl   $.LC1
    pushl   $1
    call    __printf_chk

还考虑到函数中的代码量，__umoddi3我们已经回答了这个问题。

于 2015-06-28T18:11:59.033 回答