c - 以最少的指令获得最快的整数平方根

Question

我需要不涉及任何显式除法的快速整数平方根。目标RISC架构可以做类似add的操作, mul , sub , shift在一个循环中(嗯 - 操作的结果是在第三个循环中写入的，真的 - 但是有交错)，所以任何使用这些操作并且速度很快的整数算法都会非常受欢迎。

这就是我现在所拥有的，我认为二进制搜索应该更快，因为以下循环每次执行 16 次(无论值如何)。我还没有对其进行广泛的调试(但很快)，所以也许有可能提前退出:

unsigned short int int_sqrt32(unsigned int x)
{
    unsigned short int res=0;
    unsigned short int add= 0x8000;   
    int i;
    for(i=0;i<16;i++)
    {
        unsigned short int temp=res | add;
        unsigned int g2=temp*temp;      
        if (x>=g2)
        {
            res=temp;           
        }
        add>>=1;
    }
    return res;
}

看起来上面[在目标RISC的上下文中]的当前性能成本是5条指令(bitset，mul，compare，store，shift)的循环。缓存中可能没有空间可以完全展开(但这将是部分展开的主要候选对象[例如，循环 4 而不是 16]，当然)。所以，成本是 16*5 = 80 条指令(加上循环开销，如果没有展开的话)。如果完全交错，则只需 80 个(最后一条指令为 +2)个周期。

我可以在 82 个周期下获得其他一些 sqrt 实现(仅使用 add、mul、bitshift、store/cmp)吗？

常问问题:

为什么不依靠编译器来生成良好的快速代码？

该平台没有可用的 C → RISC 编译器。我将把当前的引用 C 代码移植到手写的 RISC ASM 中。

您是否分析了代码以查看 sqrt其实是瓶颈？

不，没有必要那样做。目标 RISC 芯片大约为 20 MHz，因此每条指令都很重要。核心循环(计算发射器和接收器贴片之间的能量传输形状因子)，其中 sqrt使用，每个渲染帧将运行约 1,000 次(当然，假设它足够快)，每秒高达 60,000 次，整个演示大约运行 1,000,000 次。

您是否尝试优化算法以删除 sqrt ?

是的，我已经这样做了。事实上，我摆脱了 2 sqrt s 已经和很多部门(删除或由移位替换)。即使在我的千兆赫兹笔记本上，我也可以看到巨大的性能提升(与引用 float 版本相比)。

应用程序是什么？

这是用于组合演示的实时渐进式细化光能传递渲染器。这个想法是每帧有一个拍摄周期，所以它会在每个渲染帧上明显收敛并看起来更好(例如每秒上升 60 次，尽管 SW 光栅化器可能不会那么快 [但至少它可以运行在与 RISC 并行的另一个芯片上 - 因此，如果渲染场景需要 2-3 帧，RISC 将并行处理 2-3 帧光能传递数据])。

为什么不直接在目标 ASM 中工作？

因为光能传递是一种稍微复杂的算法，我需要 Visual Studio 的即时编辑和继续调试功能。我周末在 VS 中所做的事情(将浮点数学转换为仅整数的数百个代码更改)将在目标平台上花费我 6 个月的时间，并且只进行打印调试”。

为什么不能使用除法？

因为它在目标 RISC 上比以下任何一个慢 16 倍:mul、add、sub、shift、compare、load/store(只需要 1 个周期)。因此，它仅在绝对需要时使用(不幸的是，当无法使用移位时，已经使用了几次)。

您可以使用查找表吗？

该引擎已经需要其他 LUT，并且从主 RAM 复制到 RISC 的小缓存非常昂贵(而且绝对不是每一帧)。但是，如果 sqrt 至少给我 100-200% 的提升，我也许可以节省 128-256 字节。 .

sqrt 的值范围是多少？ ?

我设法将它减少到仅无符号的 32 位 int (4,294,967,295)

Answer 1

看看 here .

例如，在 3(a) 处有这种方法，它非常适合做 64->32 位平方根，并且也非常容易转录到汇编程序:

/* by Jim Ulery */
static unsigned julery_isqrt(unsigned long val) {
    unsigned long temp, g=0, b = 0x8000, bshft = 15;
    do {
        if (val >= (temp = (((g << 1) + b)<<bshft--))) {
           g += b;
           val -= temp;
        }
    } while (b >>= 1);
    return g;
}

没有除法，没有乘法，只有位移。但是，所花费的时间将有些不可预测，特别是如果您使用分支(在 ARM RISC 条件指令上可以工作)。

一般来说， this page列出计算平方根的方法。如果您碰巧想要生成快速平方根(即 x**(-0.5))，或者只是对优化代码的惊人方法感兴趣，请查看 this , this和 this .