我需要一个快速的整数平方根算法，不涉及任何显式除法。目标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）个周期。
我能否得到某些其他sqrt实现（仅使用add，mul，bitshift，store/cmp）低于82个周期？
常见问题解答：
- 为什么不依赖编译器生成良好快速的代码？
该平台不存在可用的C→RISC编译器。我将把当前的参考C代码转换为手写的RISC ASM。
- 您是否对代码进行了剖析以查看
sqrt是否实际上成为瓶颈？
不需要这样做。目标RISC芯片约为20 MHz，因此每个单独的指令都很重要。核心循环（计算射线枪和接收器补丁之间的能量传递形式因子）中使用了这个sqrt，每个渲染帧将运行约1,000次（如果快到足够快），最多每秒60,000次，在整个演示程序中大约运行了1,000,000次。
- 您是否尝试过优化算法以消除
sqrt？
是的，我已经这样做了。实际上，我已经去掉了两个sqrt，并且还去掉了许多除法（被移位替换或删除）。即使在我的千兆赫笔记本电脑上（与参考浮点版本相比），我也可以看到巨大的性能提升。
- 应用程序是什么？
这是一个实时的渐进式辐射度渲染器，用于竞赛演示。想法是每帧进行一次射线追踪，因此每隔一段时间会可见地收敛，并随着每帧渲染而变得更好（例如每秒上涨60次，尽管软件光栅化器可能不会那么快[但至少可以与RISC并行运行-因此如果需要2-3帧来渲染场景，则RISC将在并行中处理2-3帧辐射度数据]）。
- 为什么不直接使用目标ASM工作？
因为辐射度是一个稍微有些复杂的算法，我需要Visual Studio的即时编辑和继续调试能力。如果只打印调试信息，在目标平台上我在VS中所做的几百个代码更改（将浮点数学转换为仅限整数）需要6个月的时间。
- 为什么不能使用除法？
因为在目标 RISC 上，与以下任何操作相比（mul、add、sub、shift、compare、load/store 只需1个周期），除法速度慢16倍。因此，只有在绝对必要的情况下才使用它（不幸的是已经出现了几次情况无法使用移位）。
- 能否使用查找表？
引擎已经需要其他 LUT，从主内存复制到 RISC 的小缓存开销太大了（肯定不是每一帧都需要）。但是，如果可以让 sqrt 获得至少100-200% 的提升，我可以把128-256字节的空间留出来。
sqrt值的范围是多少？
我设法将其降至仅为无符号32位int（4,294,967,295）。
编辑1：我已经将两个版本移植到目标RISC ASM中，因此我现在可以在执行期间获得确切的 ASM 指令计数（针对测试场景）。
sqrt 调用数：2,800。
方法1：本帖中的相同方法（循环执行16次）
方法2：fred_sqrt（来自http://www.azillionmonkeys.com/qed/sqroot.html，只需3个周期）
方法1：每个sqrt的指令数为152.98。
方法2：每个sqrt的指令数为39.48（具有最终舍入和2个牛顿迭代）。
方法2：每个sqrt的指令数为21.01（不带最终舍入和2个牛顿迭代）。
方法2 使用了256个值的 LUT，但由于目标 RISC 在其4 KB 的缓存中只能使用32位访问，因此实际上需要 256*4 = 1 KB。但是考虑到其性能，我想我必须留出 1 KB 的空间（在总共 4 KB 的情况下）。
此外，我发现在禁用Method2的最后舍入和两个牛顿迭代时，没有任何可见的视觉瑕疵。也就是说，那个LUT的精度显然是足够好的。谁知道呢……
最终成本为每个平方根21.01条指令，几乎比第一个解决方案快了一个数量级。还有可能通过牺牲32个可用寄存器中的一些用于条件和跳转标签的常数来进一步降低它（每个条件必须填充2个寄存器——一个用于实际比较的常数（CMPQ指令只允许小于16的值，大于16的值必须放入寄存器），另一个用于跳转到else标签（then跳转是fall-through），因为直接相对跳转仅能在约10个指令内实现（除了最内层的两个条件外，对于如此大的if-then-else链来说是不可能的）。
编辑2: ASM微优化
在基准测试时，我为26个If.Then.Else代码块中的每一个添加了计数器，以查看是否有任何最常执行的块。
结果显示，0号、10号和11号块在99.57%/99.57%/92.57%的情况下被执行。这意味着我可以为这些比较常数（在这3个块中）牺牲3个寄存器（32个寄存器中的3个），例如r26 = $1.0000 r25 = $100.0000 r24 = $10.0000。
这将使总指令成本从58,812（平均值：21.01）降至50,448（平均值：18.01）。
因此，现在每个sqrt的平均成本只有18.01条ASM指令（且没有除法！），但它必须被内联。
编辑3: ASM微优化
由于我们知道那3个块（0/10/11）最常执行，因此我们可以在这些特定条件中使用局部短跳转（两个方向上的16字节，通常只有几个指令（因此大多无用），尤其是在条件期间使用6字节MOVEI #jump_label，register）。
当然，Else条件将会产生额外的2个操作（否则不会），但这是值得的。块10将不得不交换（Then块与Else块），这将使其更难阅读和调试，但我已经详细记录了原因。
现在，在测试场景中，总指令成本只有42,500，平均每个sqrt的指令数为15.18条ASM指令。
EDIT4: ASM微优化
第11个块条件分割为最内层的块12&13。恰好这些块不需要额外的+1数学操作，因此如果我将位移右边界与必要的位移左移#2合并（因为缓存中的所有偏移量都必须是32位），那么本地短跳跃实际上可以到达Else块。这样可以节省填充跳转寄存器的开销，但我需要牺牲另一个寄存器r23来比较$40.000的值。
最终成本是34,724条指令，每个sqrt平均12.40个ASM指令。
我还意识到我可以重新排列条件的顺序（这将使其他范围的操作更加昂贵，但只会在约7％的情况下发生），首选这个特定范围（$10,000，$40,000），至少可以节省1甚至2个条件。
如果这样做，则每个sqrt应该会降至~8.40。
我意识到范围直接取决于光线强度和距离墙的距离。这意味着我可以直接控制光的RGB值和距离墙的距离。虽然我希望解决方案尽可能通用，但是鉴于这一认识（每个sqrt平均12个操作令人惊叹），如果我可以获得如此快速的sqrt，我很乐意牺牲一些灯光颜色的灵活性。此外，在整个演示中可能只有10-15种不同的灯，因此我可以简单地找到最终导致相同sqrt范围的颜色组合，但将获得疯狂快速的sqrt。当然，这是值得的。而且我的通用备选方案（涵盖整个int范围）仍然可以很好地工作。真正做到了两全其美。
clz或类似的 1 个周期指令的情况下。 - biziclop