标签: approximation

我在javascript中看到了很多关于模拟和动画的问题,通常涉及计算斜边:

hypot = Math.sqrt(x*x + y*y);

由于笛卡尔坐标是大多数这些引擎中的首选武器,因此需要进行这些计算以找到点对之间的距离等.因此,计算斜边的任何加速都可能对许多项目有很大帮助.

为此,您能看到比上述简单实现更快的方法吗？我发现Chrome中的近似值稍微快一些,但根据SuperCollider中的近似函数, Firefox中的近似值要慢得多.

编辑2015-08-15:我已将接受的答案改为Math.hypot答案; 我怀疑目前的实用方法是使用Math.hypot或合成的hypot函数(如果不可用),并且如果足够并且Math.hypot不可用则与square(每个sch的答案)进行比较.

我有一个方法,它使用随机样本来近似计算.这种方法被称为数百万次,因此选择随机数的过程非常有效.

我不确定javas Random().nextInt真的有多快,但我的程序似乎并没有像我想的那样受益.

选择随机数时,我会执行以下操作(半伪代码):

// Repeat this 300000 times
Set set = new Set();
while(set.length != 5)
    set.add(randomNumber(MIN,MAX));

现在,这显然有一个糟糕的最坏情况运行时间,因为理论上的随机函数可以为永恒添加重复数字,从而永远保持在while循环中.但是,数字是从{0..45}中选择的,因此重复的值大部分都不太可能.

当我使用上面的方法时,它只比我的其他方法快40%,这不是近似的,但会产生正确的结果.这大约跑了100万次,所以我期待这种新方法至少快50%.

您对更快的方法有什么建议吗？或许你知道一种更有效的方法来生成一组随机数.

澄清一下,这是两种方法:

// Run through all combinations (1 million). This takes 5 seconds
 for(int c1 = 0; c1 < deck.length; c1++){
    for(int c2 = c1+1; c2 < deck.length; c2++){
     for(int c3 = c2+1; c3 < deck.length; c3++){
        for(int c4 = c3+1; c4 < deck.length; c4++){
         for(int c5 = c4+1; c5 < deck.length; c5++){
             enumeration(hands, cards, deck, c1, c2, c3, …

我正在使用一些流行的python包作为基础,为图形和网络开发一个开源近似算法库.主要目标是在图形和网络上包含NP-Complete问题的最新近似算法.原因是1)我还没有看到一个很好的(现代)整合软件包来涵盖这个和2)它将是一个很好的教学工具,用于学习NP-Hard优化问题的近似算法.

在构建这个库时,我使用单元测试来进行健全性检查(正如任何适当的开发人员所做的那样).我对我的单元测试有些谨慎,因为它们本质上是近似算法可能无法返回正确的解决方案.目前我正在手工解决一些小实例,然后确保返回的结果与之匹配,但这在实现意义上是不可取的,也不是可扩展的.

单元测试近似算法的最佳方法是什么？生成随机实例并确保返回的结果小于算法保证的界限？这似乎有误报(测试时间很幸运,并不能保证所有实例都低于限制).

我从其他地方得到了这段代码片段.根据网站管理员的说法,代码是从Knuth的计算机编程艺术中挑选出来的

由于我没有那本书的副本,我可否知道这两个功能有什么区别？

bool approximatelyEqual(float a, float b, float epsilon)
{
    return fabs(a - b) <= ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool essentiallyEqual(float a, float b, float epsilon)
{
    return fabs(a - b) <= ( (fabs(a) > fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

问候.我正在尝试近似函数

Log10 [x ^ k0 + k1],其中.21 <k0 <21,0 <k1 <~2000,并且x是整数<2 ^ 14.

k0和k1是不变的.出于实际目的,可以假设k0 = 2.12,k1 = 2660.期望的精度是5*10 ^ -4相对误差.

这个函数实际上与Log [x]相同,除了0附近,它有很大的不同.

我已经提出了一个比简单查找表快1.15倍的SIMD实现,但是如果可能的话我想改进它,我认为由于缺乏有效的指令而非常困难.

我的SIMD实现使用16位定点算法来评估三次多项式(我使用最小二乘拟合).多项式对不同的输入范围使用不同的系数.有8个范围,范围i跨越(64)2 ^ i到(64)2 ^(i + 1).这背后的理性是Log [x]的导数随x快速下降,这意味着多项式将更准确地拟合它,因为多项式非常适合于具有超出某个阶的0的导数的函数.

使用单个_mm_shuffle_epi8()可以非常有效地完成SIMD表查找.我使用SSE的float到int转换来获得指数和有效数,用于固定点近似.我还通过软件管道化循环以获得~1.25倍的加速,因此可能不太可能进行进一步的代码优化.

我要问的是,如果在更高的水平上有更高效的近似值？例如:

1. 可以将此函数分解为具有有限域的函数,如log2((2 ^ x)*significand)= x + log2(有效数字)

因此消除了处理不同范围(表查找)的需要.我认为的主要问题是添加k1术语会杀死我们所知道和喜爱的所有那些不错的日志属性,这使得它无法实现.或者是吗？

1. 迭代方法？不要这么认为,因为log [x]的牛顿方法已经是一个复杂的表达式

2. 利用邻近像素的局部性？ - 如果8个输入的范围落在相同的近似范围内,那么我可以查找单个系数,而不是查找每个元素的单独系数.因此,我可以将其用作快速常见的情况,并在不使用时使用较慢的通用代码路径.但是对于我的数据,在该属性保持70%的时间之前,范围需要大约2000,这似乎不会使这种方法具有竞争力.

请给我一些意见,特别是如果你是一名应用数学家,即使你说它不能完成.谢谢.

我试图将多项式拟合到我的数据集,看起来像那样(完整的数据集在帖子的末尾):

该理论预测曲线的表述为:

看起来像这样(对于x在0和1之间):

当我尝试通过以下方式在R中创建线性模型时:

mod <- lm(y ~ poly(x, 2, raw=TRUE)/poly(x, 2))

我得到以下曲线:

这与我的期望大不相同.您是否知道如何根据这些数据拟合一条新曲线,以便它与理论预测的曲线类似？此外,它应该只有一个最小值.

完整数据集:

x值向量:

x <- c(0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08, 0.09, 0.10, 0.11, 0.12,
 0.13, 0.14, 0.15, 0.16, 0.17, 0.18, 0.19, 0.20, 0.21, 0.22, 0.23, 0.24, 0.25,
 0.26, 0.27, 0.28, 0.29, 0.30, 0.31, 0.32, 0.33, 0.34, 0.35, 0.36, 0.37, 0.38,
 0.39, 0.40, 0.41, 0.42, 0.43, 0.44, 0.45, 0.46, 0.47, 0.48, 0.49, 0.50, 0.51,
 0.52, 0.53, 0.54, 0.55, 0.56, 0.57, 0.58, 0.59, 0.60, 0.61, 0.62, 0.63, …

我有一些长串(约1.000.000个字符).例如,每个字符串仅包含来自定义的字母表的符号

A = {1,2,3}

示例字符串

string S1 = "1111111111 ..."; //[meta complexity] = 0
string S2 = "1111222333 ..."; //[meta complexity] = 10
string S3 = "1213323133 ..."; //[meta complexity] = 100

问:我可以使用哪种措施来量化这些字符串的复杂性？我可以看到S1没有S3那么复杂,但我怎么能以编程方式从.NET做到这一点？任何算法或指向工具/文献将非常感激.

编辑

我试过Shannon熵,但事实证明它对我来说并不是真的有用.我将对这些序列AAABBBCCC和ABCABCABC以及ACCCBABAB和BBACCABAC具有相同的H值

我正在用javascript做一些数字信号处理计算,我发现计算双曲正切(tanh)有点太贵了.这是我目前近似tanh的方式:

function tanh (arg) {
    // sinh(number)/cosh(number)
    return (Math.exp(arg) - Math.exp(-arg)) / (Math.exp(arg) + Math.exp(-arg));
}

有人知道更快的计算方法吗？

注意:由于旅行不是在它开始的同一个地方结束的事实,而且只要我仍然访问所有这些点,每个点都可以被访问多次这一事实,这不是真正的TSP变体,而是我之所以说是因为缺乏对问题的更好定义.

所以..

假设我正在徒步旅行,有n个兴趣点.这些景点都通过远足径相连.我有一张地图显示了所有距离的路径,给我一个有向图.

我的问题是如何近似一个从A点开始并且访问所有n个兴趣点的旅游,同时结束旅行的任何地方,但我开始的点,我希望旅游尽可能短.

由于远足的性质,我认为这可能不是一个对称问题(或者我可以将我的不对称图转换为对称图？),因为从高海拔到低海拔显然比其他方式更容易.

另外我认为它必须是一种适用于非度量图的算法,其中不满足三角不等式,因为从a到b到c可能比从a到c的真正漫长而奇怪的道路更快直.我确实考虑过三角不等式是否仍然存在,因为对于我访问每个点的次数没有限制,只要我访问所有这些,这意味着我总是选择从a到c的两条不同路径中最短的路径,从而永远不会抓住漫长而奇怪的道路.

我相信我的问题比TSP更容易,因此这些算法不适合这个问题.我考虑过使用最小生成树,但我很难说服自己可以将它们应用于非度量非对称有向图.

我真正想要的是关于如何能够提出近似算法的一些指示,该算法将通过所有n个点找到近乎最佳的旅行

我有一些地理数据(下面的图像显示了河流的路径为红点),我想用多段三次贝塞尔曲线近似.通过对计算器等问题,在这里和这里我发现由Philip J.施耐德从"图形宝石"的算法.我成功地实现了它并且可以报告即使有数千个点它也非常快.不幸的是,速度带来了一些缺点,即装配非常不合适.请考虑以下图形:

红点是我的原始数据,蓝线是由Schneider算法创建的多段贝塞尔曲线.如您所见,算法的输入是一个容差,至少与绿线表示的一样高.然而,该算法创建了具有太多急转弯的贝塞尔曲线.你也会在图像中看到这些不必要的急转弯.很容易想象,对于所示数据,具有较小急转弯的贝塞尔曲线,同时仍保持最大公差条件(仅将贝塞尔曲线稍微推向品红色箭头的方向).问题似乎是算法从我的原始数据中选取数据点作为各个贝塞尔曲线的终点(品红箭头指示一些嫌疑人).由于贝塞尔曲线的端点受到限制,很明显该算法有时会产生相当尖锐的曲率.

我正在寻找的是一种算法,它使用具有两个约束的多段贝塞尔曲线来近似我的数据:

• 多段贝塞尔曲线绝不能超过数据点一定距离(由Schneider算法提供)
• 多段贝塞尔曲线绝不能产生过于尖锐的曲率.检查此标准的一种方法是沿多段贝塞尔曲线滚动具有最小曲率半径的圆,并检查它是否沿其路径接触曲线的所有部分.虽然看起来有更好的方法涉及一阶和二阶导数的叉积

我发现可以创造更好拟合的解决方案或者仅适用于单个贝塞尔曲线(并且省略了如何在多段贝塞尔曲线中找到每个贝塞尔曲线的良好起点和终点的问题)或者不允许最小曲率约束.我认为最小曲率约束是这里的棘手条件.

这是另一个例子(这是手绘而不是100%精确):

让我们假设图1显示了两者,曲率约束(圆必须适合整个曲线)以及任何数据点与曲线的最大距离(恰好是绿色圆的半径).图2中红色路径的成功近似显示为蓝色.该近似值符合曲率条件(圆可以在整个曲线内滚动并在任何地方触摸它)以及距离条件(以绿色显示).图3显示了路径的不同近似值.虽然它符合距离条件但很明显圆圈不再适合曲率.图4显示了一条不可能用给定约束近似的路径,因为它太尖了.该示例应该说明为了正确地近似路径中的一些尖转弯,算法必须选择不属于路径的控制点.图3显示,如果选择沿路径的控制点,则不能再满足曲率约束.此示例还显示算法必须退出某些输入,因为无法使用给定的约束来近似它.

这个问题是否存在解决方案？解决方案不一定要快.如果需要一天时间来处理1000点,那就没问题了.解决方案也不必是最佳的,因为它必须导致最小二乘拟合.

最后,我将用C和Python实现它,但我也可以阅读大多数其他语言.