大数运算基选择测试

无心人

还没测试呢
别说这么多话
我只是猜测

liangbch

我的建议：

  我的打算，编写一个程序，给出 基为 $2^30 $与基为 $2^32 $的速度对比，具体方法如下。

  1.数的长度采用15×32=480bit。
  2.仿制 x86上128位二进制乘法最快速算法征解 那个帖子中 96楼的程序，写一个480 bit * 480 bit的 SSE2指令 MM 寄存器版，完全循环展开，无循环，无跳转指令，共需15×15共225次 32bit 的乘法。（已经证明，这种算法是最快的版本SSE2指令中最快的版本。

  3.仿制x86上128位二进制乘法最快速算法征解 那个帖子中 102楼的程序，写一个480 bit * 480 bit的 ALU版，完全循环展开，无循环，无跳转指令，共需15×15共225次 32bit 的乘法。（已经证明，这种算法是最快的ALU版,具体数据可从gxq x86上 96bit*96 bit 征解的那个帖子。

  4.将480bit展开为16个DWORD，每个DWORD表示30bit（即基为$2^30$)，写一个ALU版本的程序，共需16×16=256次乘法。
  5.将480bit展开为16个DWORD，每个DWORD表示30bit（即基为$2^30$)，写一个SSE2指令MM寄存器版本（采用32bit乘，64bit加)。共需16×16=256次乘法。
  6.将480bit展开为16个DWORD，每个DWORD表示30bit（即基为$2^30$)，写一个SSE2指令XMM寄存器版本（采用128位寄存器，充分发挥SSE2指令优势)。

至于和基为2^28的速度对比，如果gxq愿意的话，可参照如下形式。
  1.数的长度采用14×32=448bit。
  2.仿制 x86上128位二进制乘法最快速算法征解 那个帖子中 96楼的程序，写一个448 bit * 448 bit的 SSE2指令 MM 寄存器版，完全循环展开，无循环，无跳转指令，共需15×15共225次 32bit 的乘法。（已经证明，这种算法是最快的版本SSE2指令中最快的版本。

  3.仿制x86上128位二进制乘法最快速算法征解 那个帖子中 102楼的程序，写一个448 bit * 448 bit的 ALU版，完全循环展开，无循环，无跳转指令，共需14×14共196次 32bit 的乘法。（已经证明，这种算法是最快的ALU版,具体数据可从gxq x86上 96bit*96 bit 征解的那个帖子。

  4.将448bit展开为16个DWORD，每个DWORD表示28bit（即基为$2^28$)，写一个ALU版本的程序，共需16×16=256次乘法。
  5.可根据需要写1个或者几个SSE2 指令的版本。

几点说明，基准程序（采用基为2^32的版本），公开源代码。其他 基为2^30或者2^28的程序，可不公布源代码。

无心人

不行的
不能完全循环展开
那只是用于小数字的算法
如果你想基于真实环境
请写一个能用于从1-4096bit都能正确工作的版本
可不考虑结果清零过程
结果清零由外部函数完成
我可提供个高于4GB / s的结果清零函数

gxqcn

为了达到实用之目的，
还是不固定乘数的bit长度的好，但可事先约定其上限，以方便算法优化。

无心人

//双字串清零，提高了速度,达到  < 2 Clock / DWORD
void AsmMemZero(unsigned long * p, unsigned long t)
{
    __asm
    {
    mov ecx, t
    cmp ecx, 0
    je  AsmMemZero3
    mov eax, dword ptr [p]
    mov ebx, 0
    test eax, 15 //不是16字节对齐的执行下面的语句
  je  AsmMemZero4
    mov edx, eax
    shr edx, 4
    shl edx, 4
    cmp edx, eax
    je  AsmMemZero4
    add edx, 16
    sub edx, eax
    shr edx, 2
    sub ecx, edx
AsmMemZero7:
    mov [eax], ebx
    add eax, 4
    sub edx, 1
    jne AsmMemZero7
    cmp ecx, 0
    je  AsmMemZero3
AsmMemZero4:
    mov ebx, ecx
    shr ebx, 2
    mov edx, ebx
    shl ebx, 2
    cmp ebx, 0 //是否不足16字节
  je AsmMemZero6
    sub ecx, ebx
    mov ebx, ecx  //保留末尾的不足16字节的部分
  mov ecx, edx //循环的次数
  pxor xmm0, xmm0
AsmMemZero1:
    movntdq [eax], xmm0 //t较小用movdqa
    add eax, 16
    loop AsmMemZero1
    cmp ebx, 0
    je AsmMemZero3
    mov ecx, ebx
AsmMemZero6:
    mov ebx, 0
AsmMemZero2:
    mov [eax], ebx
    add eax, 4
    loop AsmMemZero2
AsmMemZero3:
    sfence
    emms
    }
}

liangbch

to gxq 就其应用而言，不固定长度是必须的。但这里我 主要想测试/展示一下这几种做法的速度之比，及理论最佳速度。如果采用不固定长度，可能会使用许多技巧，如循环展开等，使得比较不公平。

  to 无心人，清0不是必须的，这样反而浪费时间。

   看可一下你的代码，伪代码大抵是这样的。
   for (i=0;i<n;i++)
   {
     UINT64 c=0;               
     UINT64 p;
     for (j=0;j<n;j++)
        {
           p=left[ i ] * right[j];
           p+=c;
           p+=result[i+j];
           result[i+j]=p 的低32bit;
           c= (p>>32);        
               
        }
     }
    总共需要n*n次操作，每次操作包括，一次32bit * 32bit 乘法，2次 64bit和 32bit 的加法。这种做法，需要事先清空result.

    将算法作如下修改，就不需要清空result，而且在第一趟计算中，不需对result[ i ]累加，这样节省了不少运行时间。
     其实，我的96楼的程序就是这么做的，不知你为什么没有采用这种做法。

   //第一趟，不需和result[ i ]累加        
   c=0;
   for (j=0;j<n;j++)
   {
           p=left[0] * right[j];
           p+=c;
          result[j]= p的低32bit；
            c= (p>>32);        
  }
   result[j]=c;


   for (i=1;i<n;i++)
   {
     DWORD c=0;               
     UINT64 p;
     for (j=0;j<n;j++)
     {
           p=left[ i ] * right[j];
           p+=c;
          p+=result[i+j];
          result[i+j]= p 的低32bit；
             c= (p>>32);        
     }
     result[i+j]=c;
   }

  }

无心人

//双字串清零函数最新版本
//已测试比前版速度快
//已测试长度越大，比ALU指令越快
//应该总假定是双字串
void AsmMemZero(unsigned long * p, unsigned long t)
{
    __asm
    {
    xor eax, eax
        cld
        mov edi, dword ptr [p]
        mov edx, t
        test edx, 0xFFFFFFFF
        je exit0
        test edi, 15  //是否16字节对齐
        je  AsmZero1
    mov ecx, edi
        and ecx, 0xFFFFFFF0
        add ecx, 16
        sub ecx, edi  //得到需要双字复制部分，要和edx比较谁大
    shr ecx, 2 //转换为双字长度
        mov ebx, ecx
        cmp ecx, edx
    ja  AsmZero2  //不足，转尾处理
        rep stosd
    sub edx, ebx
        je exit0  //是否刚好
AsmZero1: //16字节对齐
        mov ecx, edx
        shr ecx, 4
        je AsmZero2  //是否不足16字节
    pxor xmm0, xmm0
AsmZero11:
        movdqa [edi], xmm0
        add edi, 16
        sub ecx, 1
        jne AsmZero11
AsmZero2:
        mov ecx, edx
        and ecx, 15
        rep stosd
exit0:
        sfence
        }
}

无心人

谢谢你的提醒
我会修改的
========
顺上刚测试的清零函数共享

无心人

考虑一次乘4个的可能性
如果有效率提高
是否说明比你们算法好？
至少那个长加你们可能就无法超越吧
毕竟32位是系统自动规整的

liangbch

原帖由 无心人 于 2008-4-8 20:43 发表
考虑一次乘4个的可能性
如果有效率提高
是否说明比你们算法好？
至少那个长加你们可能就无法超越吧
毕竟32位是系统自动规整的

   我准备写3个基为 $2^32 $的版本， 3个基为 $2^30$的版本， 总体说来，后三者一定比前三者快，并且公布前三者的代码（后3者的代码将在适当的时候公开）。
   你等着看好消息吧，看看我的版本可比你的版本快多少。