最快的因子实现,64位结果

Question

这不是家庭作业,只是我喜欢的东西.因此,直接计算因子不是很快; 记忆化可以帮助,但如果结果是装配到32或64位,则阶乘只能为输入工作0通过12和20分别.所以...我们不妨使用查找表:

n   n!
0   1       
1   1       
2   2       
3   6       
4   24      
5   120     
6   720     
7   5040        
8   40320       
9   362880      
10  3628800     
11  39916800        
12  479001600       
13  6227020800  2^32=   4294967296
14  87178291200     
15  1.30767E+12     
16  2.09228E+13     
17  3.55687E+14     
18  6.40237E+15     
19  1.21645E+17     
20  2.4329E+18      
        2^64=   1.84467E+19

因此,假设我想要一个使用内联汇编的内联C++阶乘函数,结果需要32位或64位无符号整数.如果输入为负或大到足以导致溢出,则输出应为0.如何在汇编中完成此操作以使其消耗最少量的循环？此代码将在64位Intel/AMD架构上运行.如果可行,我有兴趣改善最坏的情况,所以20!不应该花费更多的时间来计算0!- 希望有一种二元搜索方法.希望有一个聪明的伎俩if (n == 0 || n == 1) { return 1; }.此外,如果输出需要是32位,那么我认为汇编指令可以包含代码和数据.我的装配知识很薄弱.如果这个问题没有多大意义,请告诉我.

能够在C++中使用该函数会很好 - 使它成为一个更现实的问题.例如,如果调用函数是昂贵的,那么尝试在程序集的主体中保存1-2个时钟周期将无济于事.

Answer 1

我巧妙地在汇编中构建了一个查找表.为了防止你的程序集生锈,例程需要参数在ecx寄存器中.我验证它在范围内,然后将查找表的值读入eax和edx寄存器.如果该值超出了范围,我只是异或eax,并edx用自己注册(这迫使他们为0).不幸的是,由于它是一个汇编例程,编译器将无法内联代码.但是,我确信通过编写令人敬畏的汇编例程而节省的几个周期将通过内联来弥补任何收益.

factorial:
    xorl    %eax, %eax
    xorl    %edx, %edx
    cmpl    $20, %ecx
    ja  .TOOBIG
    movl    CSWTCH.1(,%ecx,8), %eax
    movl    CSWTCH.1+4(,%ecx,8), %edx
.TOOBIG:

LOOKUP_TABLE:
    .section    .rodata
    .align 32
    .type   CSWTCH.1, @object
    .size   CSWTCH.1, 168
CSWTCH.1:
    .long   1
    .long   0
    .long   1
    .long   0
    .long   2
    .long   0
    .long   6
    .long   0
    .long   24
    .long   0
    .long   120
    .long   0
    .long   720
    .long   0
    .long   5040
    .long   0
    .long   40320
    .long   0
    .long   362880
    .long   0
    .long   3628800
    .long   0
    .long   39916800
    .long   0
    .long   479001600
    .long   0
    .long   1932053504
    .long   1
    .long   1278945280
    .long   20
    .long   2004310016
    .long   304
    .long   2004189184
    .long   4871
    .long   -288522240
    .long   82814
    .long   -898433024
    .long   1490668
    .long   109641728
    .long   28322707
    .long   -2102132736
    .long   566454140

查找表很难维护,所以我已经包含了我用来构建它的脚本

static constexpr uint64_t const_factorial(uint32_t i) {
    return (i==0)? 1: (i * const_factorial(i-1));
}

uint64_t factorial(uint32_t i) {
    switch(i) {
        case 0: return const_factorial(0);
        case 1: return const_factorial(1);
        case 2: return const_factorial(2);
        case 3: return const_factorial(3);
        case 4: return const_factorial(4);
        case 5: return const_factorial(5);
        case 6: return const_factorial(6);
        case 7: return const_factorial(7);
        case 8: return const_factorial(8);
        case 9: return const_factorial(9);
        case 10: return const_factorial(10);
        case 11: return const_factorial(11);
        case 12: return const_factorial(12);
        case 13: return const_factorial(13);
        case 14: return const_factorial(14);
        case 15: return const_factorial(15);
        case 16: return const_factorial(16);
        case 17: return const_factorial(17);
        case 18: return const_factorial(18);
        case 19: return const_factorial(19);
        case 20: return const_factorial(20);
        default: return 0;
    }
}

万一你错过了我的幽默尝试.C++编译器能够正确优化您的代码.正如您所看到的,我不需要对查找表,二叉搜索树或哈希进行任何花哨的操作.只是一个简单的switch声明,编译器完成了其余的工作.

Answer 2

我弯曲组装肌肉已经有一段时间了,所以我只提供一些一般的建议.

由于您事先知道所有项目的确切数量和大小,只需创建一个连续的值数组(硬编码或预先计算).验证函数的输入(<0或> 12/20)后,可以使用简单的偏移量寻址来检索适当的值.这将在O(1)时间内起作用.