我们将经过-进一步
在上一篇文章中，我展示了如何通过以下方法来提高计算贝塞尔曲线（KB）上的点的速度：
- 计算公式的转换-加速度〜3倍。
- 从PT到FT几乎没有加速度-但它允许3。
- 通过乘法和移位进行除法的替换操作又增加了40％。
悲伤的退却-我在最后一个公式中犯了一个错误，可以通过折叠另一个常数表达式来加快计算速度，并且不包括乘法，而不是每个计算周期502获得410个时钟周期。 不幸的是，上一篇文章的读者都没有在评论中向我指出这一点……但我一直希望如此，这意味着我对读者的兴趣不足，无法正确地（即，仔细地）阅读我的意见。 好的，再试一次。
在上述帖子的结尾，我说过计算可以更快地完成，但是“男孩说-男孩做了什么”。
让我再次提醒您有关计算KB上的点的公式
速度的下一个增长与问题的特殊性有关-我们不仅需要在参数“和”的不同值上计算KB的值，还需要在以已知的固定值（以in为单位）改变（在这种情况下，增加）该参数时找到一系列值。案例单位），这样您就可以使用以下技术。 在我的时代，这被称为差异计算法（如果记忆对我有用，至少那是在讲座中所说的），整个Internet都在您的掌控之中，也许（即使可以肯定），还有另一个名字。
我们考虑P = A *和（=> 1 *）的情况，并假设我们知道带有某些参数u0的P0的值。 然后可以将下一个参数为u0 + 1的值计算为P = A *（u0 + 1）= A * u0 + A = P0 + A（=> 1+）。 在不损失任何精度的情况下，我们能够用快得多的加法运算代替乘法运算。
现在是一个更复杂的示例P = A *和*和（=> 2 *），我们通过类比考虑P = A *（和+ 1）*（和+ 1）= A *（和*和+ 2 *和+1） = A *和*和+ 2 * A *和+ A = P0 + 2 * A *和+ A（=> 2 * 2 +）。 乍一看，我们什么都没有赢，但是如果我们预先计算A'= 2 * A，我们得到（=> 1 * 2 +），那么赢就很有可能。 但是我们不会止步于用获得的表达式A'*实现的结果，并应用我们已知的技术，然后我们将对两个变量进行两个运算：P = P + A'+ A; A'= A'+ A（=> 3+）。 如果考虑到A的初始值可以由A来完成，那么通常只剩下两个加法而不是两个乘法。 是的，我们必须获得两个额外的变量，但这是经典的交换-我们用内存来支付时间。
它仅保留计算正确的初始值，但在迭代开始时仅执行一次，并且如果参数的初始值为u = 0，则其通常是微不足道的P = 0，A'=A。 我们将在几次迭代中测试我们的方法（这完全没有必要，正确应用的数学方法不会给出错误的答案），但是它将使我们能够更好地了解正在发生的事情。 所以
迭代0：和= 0; P = 0（真）; A'= A; A''= 2 * A;
迭代1：和= 1; P = 0 + A'= 0 + A = A（是）; A'= A'+ A''= A + 2 * A = 3 * A;
迭代2：和= 2; P = A + 3 * A = 4 * A（是）; A'= 3 * A + 2 * A = 5 * A;
迭代3：和= 3; P = 9 * A（是）； A'= 7 * A，依此类推。
我们注意到，所获得的公式与牛顿法之间的联系用于计算具有已知值的点附近函数的值。 而且，由于我们的函数是二阶的，并且所有从三阶开始的导数都等于零，因此我们可以安全地用精确的等号替换近似等号。 与该方法的唯一区别是，我们不断移动要相对于其建立新邻域的点，以避免在原始公式中执行乘法运算。
用扩展形式重写我们的KB原始表达
然后对于使用这种方法的计算，我们需要第一个项2+（和两个变量），第二个项1+（和一个变量）以及2+才能将所有内容加在一起（=> 5+）。 可以预期，即使是这种（错误的）方法也将比2 * 2 +有所收获，但是一切都好得多。 显然，加法运算是加法运算（谢谢，队长），因此您可以对术语进行分组并用新的表达式替换常数项，从而得到以下算法：
1. P的初始值= C; A'= A1 + B1; A''= 2 * A1;
2.在下一步P = P + A'; A'= A'+ A''（=> 2+），无疑比Horner的方案快。
我们以程序形式实现算法（这看起来并不琐碎，因为为简单起见，我忘记了移位的必要，但是20分钟并不是很难），我们获得了计算复杂度（=> 2 + 1 >>）并进行测量速度-事实证明每个循环140个循环（速度再提高3倍），但这几乎是理想的结果。 为了获得理想的（某种意义上）选项，我们要做的是注意公式中操作数的维数。 现在，我们对长整数（32位）执行所有操作，这在某些地方可能是不必要的。 如果我们将操作数的容量减少到最低限度，那么我们可以获得20％到25％的增益，但这将需要我们切换到汇编器（C没有适合此类运算的方法）并仔细分析原始问题的数据。 无论是由读者决定是否执行此操作，与“天真的”方法相比，我们已经将计算速度提高了1900/140 = 13倍以上。
关于算法实现的最后一点是，我们仍然通过常数乘法更改除法运算来排除除法运算，在生成初始数据并以8的常数倍进行移位时会考虑到这一点。这可以通过多种方式完成，执行时间略有不同，从而使此类实验吸引了好奇的读者注意。
但是，一个问题完全出乎意料地出现-我们清楚地看到对32位数字进行两次加法运算，这需要4 + 4 = 8个时钟周期，另外8 * 3 * 2 = 48个时钟周期用于发送操作数，4个时钟周期用于接收移位结果，4一个时钟周期调用计算过程并返回，还有4个时钟周期来组织该周期-从那里还不清楚另外60个时钟周期。 以前，我们只是在数百个时钟周期的背景下才注意到这一点，但是现在您可以注意了。 容易发现过多的措施-在该周期中，进行了不必要的调试操作，如果仔细清理所有内容，则仅剩下120项措施，并且每个目的都是可以理解的（当然，并不是完全可以理解的）。 接下来，我们找出空循环的执行时间-22个小节，我想知道它们一直在做什么，但是，好了，清除实际的计算时间，即98个循环。 请注意，对获得的工作加速度的评估会发生变化：我们得到（1900-50）/（140-40）= 19倍，而不是1900/140 = 13，这是没有实际意义的，因为循环仍然是必需的，但是您可以将其提高得更多自尊。
最后一句话-显而易见，我们只有在处理大型鹿甲虫并且它们（跳蚤）的存在变得明显而且意义重大时才开始寻找和消除跳蚤。 在性能方面优化程序时，我强烈建议使用这种方法（并且我并不孤单）。
好吧，总而言之，关于``某种意义上的''注释-如果我们谈论的是在更改参数时（代表时间）依次计算KB上下一个点的坐标，那么提出的算法（经过所有优化）将不再可能进行改进。 但是，如果您重新制定任务，例如，设定仅在屏幕上建立设计局（不参考时间）的目标，那么就有一个非常有前途的方法，关键字“ Brezenheim”，但是“这是一个完全不同的故事”，我将在另一篇文章中进行介绍。 （如果姐姐不介意的话，也许有一天）。