#引言

在程序设计之中，往往会遇到计算long long * long long % long long的问题，这时候，我们往往会使用快速加来解决这个问题：

long long tim(long long a, long long b) {
    long long r = 0;
    while (b) {
        if (b & 1) {
            r += a;
            if (r > mod2) r -= mod2;
        }
        a += a;
        if (a > mod2) a -= mod2;
        b >>= 1;
    }
    return r;
}

这一点似乎已经成为了共识，但是我偶然了解到，GCC提供了一种标准之外的内容，即__int128，然而，目前商用级的CPU的字长最长也只有64位，至于它的效率如何，尚没有现成的资料，这里，我将进行五千万组测试，来探究它们的效率关系。

#分析

对于代码，尽量避免了CPU层面的优化以尽量真实地体现算法本身的效率，分为数据产生和计算两部分，在每一组计算之前，用一个既定的数组实现强制性的Cache Miss，以避免效率上的疑问，通过汇编代码的分析来确认了这一点

首先，我的测试从int * int % int开始，这里的代码略去，它和下面实验所采用的代码很相似，结果是这样的：

通过足够多的测试数据，我们可以发现，直接进行long long的计算，比快速加算法要显著性的快16%左右，接下来将在long long * long long % long long中进一步确认复杂度：

可以看出，采用__int128计算效率也要比快速加要快8%左右，而且这个8%是较为稳定的数据，在正式的比赛中，如果遇到了可能会被卡时间的情况，应当尽量采用__int128进行计算。

#结论

在程序设计竞赛中，鉴于评测环境一般都是gcc套件，提供x86-64的CPU，所以一般是支持__int128数据类型的，所以可以考虑放弃使用快速加，来实现显著的更高效率。

另外，不光gcc，已知其它的一些编译器（如LLVM Clang）也支持__int128数据类型。

这是农历新年的第一篇文章，祝各位在新的年里能拿到更多的气球～