我在,给出的线段,并且想知道它们是否具有相同的长度(最多有一些错误),因此天真的测试看起来像
但是,我需要测试一大组段,所以我想摆脱sqrt
范数内的计算。每个片段仅在完整计算中出现一次,以便我可以预先计算和存储长度。
如果是的平方范数,我可以将方程写为
如果我两边都平方,我只会得到一个
这再次迫使我计算根。
我错过了一些明显的东西吗?
我在,给出的线段,并且想知道它们是否具有相同的长度(最多有一些错误),因此天真的测试看起来像
但是,我需要测试一大组段,所以我想摆脱sqrt
范数内的计算。每个片段仅在完整计算中出现一次,以便我可以预先计算和存储长度。
如果是的平方范数,我可以将方程写为
如果我两边都平方,我只会得到一个
这再次迫使我计算根。
我错过了一些明显的东西吗?
您还可以重写表达式以完全避免平方根。重新排序,使不等式为 这等价于 依次等价到 不涉及平方根
一般来说,函数将是其中最慢的部分。幸运的是,如果它们的长度相同,那么它们的长度的平方也相同。因此,您可以省略该部分并比较范数的平方。
我不知道有什么方法可以使用跨平台代码让它变得更快。
但是,如果您真的想让它快速运行,您可以随时查看您正在运行的处理器,并确定它是否支持向量指令(即 SSE 或 AVX)并使用这些内在函数。https://software.intel.com/sites/landingpage/IntrinsicsGuide/
通过这样做,您可以利用计算中的指令级并行性并实现巨大的加速,尽管以您的时间为代价。但是,您的编译器可能已经为您执行此操作,特别是如果您使用 (for gcc) -march=native 进行编译。在花时间自己对代码进行矢量化之前,您应该检查编译器产生的程序集。
我想为这个问题提交一个单独的答案,因为有一种方法可以自动简化这些公式以去除平方根。我将使用 sage 和QEPCAD(都是免费的)。教程在这里。
不等式 等价于存在使得 这些是量化的多项式不等式,可以使用 QEPCAD 在 sage 中使用以下简单会话进行简化:
var('a,b,u,v,t')
qepcad(qf.E([u,v], qf.and_((u-v)^2 < t^2, u^2 == a, v^2 == b)))
输出给出了原始不等式成立的等价条件:
a >= 0 /\ b >= 0 /\ [ t^4 - 2 b t^2 - 2 a t^2 + b^2 - 2 a b + a^2 < 0 \/ t^2 - b - a > 0 ]
换句话说,它等价于
这种方法的好处是它没有人为错误。
不要对差异设置阈值,而是在比率上设置阈值:
并摆脱平方根。取决于所选顺序这一事实感到不安,那么您可以考虑使用简短的 if 语句。