标签: approximation

请考虑以下代码段

float num = 281.583f;
int amount = (int) Math.round(num*100f);
float rounded = amount/100.0f;
double dblPrecision = rounded;
double dblPrecision2 = num;
System.out.println("num : " + num + " amount: " + amount + " rounded: " + rounded + " dbl: " + dblPrecision + " dbl2: " + dblPrecision2);

我得到的输出是

num : 281.583 amount: 28158 rounded: 281.58 dbl: 281.5799865722656 dbl2: 281.5830078125

为浮点数分配给双变量时,为什么会有近似值？

我试图规范化4d向量.

我的第一个approch是使用SSE内在函数 - 这为我的向量算法提供了2倍的速度提升.这是基本代码:( v.v4是输入)(使用GCC)(所有内容都是内联的)

//find squares
v4sf s = __builtin_ia32_mulps(v.v4, v.v4);
//set t to square
v4sf t = s;
//add the 4 squares together
s   = __builtin_ia32_shufps(s, s, 0x1B);
t      = __builtin_ia32_addps(t, s);
s   = __builtin_ia32_shufps(s, s, 0x4e);
t      = __builtin_ia32_addps(t, s);
s   = __builtin_ia32_shufps(s, s, 0x1B);
t      = __builtin_ia32_addps(t, s);
//find 1/sqrt of t
t      = __builtin_ia32_rsqrtps(t);
//multiply to get normal
return Vec4(__builtin_ia32_mulps(v.v4, t));

我检查了反汇编,它看起来像我期待的.我没有看到任何大问题.

无论如何,然后我尝试使用近似值:(我从谷歌得到这个)

float x = (v.w*v.w) + (v.x*v.x) + (v.y*v.y) + (v.z*v.z);
float xhalf …

问题

我正在尝试实现一个快速浮点数= log2(浮点数).我写了一个简单的C程序来比较我的结果和log2,我得到一个小错误,我找不到源代码.

背景

我正在采用识别浮点表示(忽略符号位)的方法2^(exponent) * 1.significand.使用我得到的日志属性log2(float) = exp + log2(1.significand).最终我会截断表查找的有效数字,但是现在我想验证正确的结果.

有关灵感的进一步背景阅读:http://www.icsi.berkeley.edu/pubs/techreports/TR-07-002.pdf

码

这就是问题所在.这是一个简单的程序,它提取浮点位并将指数加到log2(有效数字).

#include <math.h>
#include <stdint.h>
#include <stdio.h>

int main()
{
    typedef union {
      int32_t i;
      float f;
    } poly32_t;

    float x = 31415926535.8;
    poly32_t one;
    one.f = 1.0f;

    uint32_t ii;
    uint32_t num_iter = 15;
    for(ii=0; ii < num_iter; ++ii) {
        poly32_t poly_x;
        poly32_t poly_x_exponent;
        poly32_t poly_x_significand;

        // extract the exponent and significand
        poly_x.f = x;
        poly_x_significand.i = (0x007fffff & poly_x.i); …

我有一个特定的运动学作为一个更复杂的机器的一部分,需要计算一些非常困难(更不可能)的物理参数,用我可以使用的仪器以适当的精度进行测量

[运动学]

首先看它是一个简单1的自由度臂(黑色),它可以围绕x轴旋转.它有一个重量,迫使它一直向上,直到它达到机械终点(角度a0)或一些半径的管(蓝色)r0.手臂旋转中心位于y0.管可以移动到任何y(t)高度.

[用法]

这用于测量管的半径以进行进一步处理.可以计算半径(通过基本测角仪),这导致图像底部的方程.常数a0,y0,z0非常难以测量(它在复杂的机械内部),因此距离的测量精度是最小值0.1 mm和角度0.1 deg,甚至是有问题的.

[校准]

所以我决定尝试从机器本身完成的一组测量中计算这些参数(自动校准).所以我有已知半径的校准管r0.所有绿色参数都可以作为常量处理.现在我沿着y轴定位管子以尽可能多地覆盖手臂的角度.遗憾的是,该范围仅为20 degrees(对于当前的机器设置)记住测量a(t)的预设y(t)...作为n点数据集.这给了我n超越方程组.从此我尝试/猜测a0,y0,z0记住最佳解决方案的"所有"可能性(最接近r0)

[近似a0,y0,z0]

近似是基于这类矿井:

//---------------------------------------------------------------------------
class approx
    {
public:
    double a,aa,a0,a1,da,*e,e0;
    int i,n;
    bool done,stop;

    approx()            { a=0.0; aa=0.0; a0=0.0; a1=1.0; da=0.1; e=NULL; e0=NULL; i=0; n=5; done=true; }
    approx(approx& a)   { *this=a; …

我有一个由线段和圆弧组成的折线轮廓，我想将其挤出为棱柱。

由于我的挤压函数只支持直边多边形，我需要使用线段来近似弧。

圆弧通过起点、中心点和扫掠角 (CCW) 定义。

我需要显示的扫角范围从 <10° 到 179.9°，半径范围从 0.3 毫米到 300 毫米。

我目前计算了一些弧顶点来计算并以原始方式将它们添加到我的多边形中：我只是在给定弧长的每一毫米上放置一个顶点。虽然这有效，但对于大半径和小扫掠角的弧似乎效率很低。

必须有一种算法可以为所有类型的弧生成良好的近似值。如果有的话，我想知道一些关键字来缩小我的谷歌搜索范围。

我需要求解 N 个线性方程组作为数值优化器的中间步骤。AFAIK 相当简单的算法精确地做到这一点是 O(N^3) （尽管我在一些数学论文中看到了一个非常复杂的算法，可以用 O(N^2.8) 和一个巨大的常数来完成）。在某些情况下，N 很大，即几千。

有没有什么好方法可以在小于 O(N^3) 的时间内获得线性方程组的近似解？

编辑：

如果有帮助的话，这里有一些更多的细节。

1. 我的矩阵是对称的，并且不稀疏。

2. 这是 Newton-Raphson 的二阶导数矩阵。我正在尝试在 2000 维空间中优化某些内容。

我需要做一个线性近似。但是，它必须是对数刻度。

这是我的gnuplot脚本：

f(x)= a*x+b
fit f(x) "d0.dat" via a,b
set logscale x
set logscale y
plot "d0.dat" with points lt rgb "#ff0000" title "Points", \
f(x) with lines lt rgb "#ff00ff" title "Approximation"

显然，这种近似是错误的。谁能帮我修复它。我在Google中找不到任何东西。

有谁知道对数组进行 k 近似排序的算法吗？

我们被要求找到 k 近似排序的算法，它应该在 O(n log(n/k)) 中运行。但我似乎找不到任何。

K-大约。排序意味着数组和任何 1 <= i <= nk 使得 sum a[j] <= sum a[j] i<=j<= i+k-1 i+1<=j<= i+k

我有 3 个由 3 个列表组成的数组：

 x = np.array(xlist)\n y = np.array(ylist)\n z = np.array(zlist)\n

其中每个列表代表 x 坐标、y 坐标以及每个指定坐标的权重。每个列表中有大约 3000 个值（对应于 3000 个单独的点，每个点具有一定的权重 z）。

问题是，这些值是非常精确的浮点数，精度达到 10 级。但是，我想要做的是能够创建 \xe2\x80\x9cn\xe2\x80\x9d 数量大致均匀分布的轮廓线（不是填充颜色，只是一些闭合的细线），其阈值为近似。

尽管我的 z 点非常精确并且可能没有 2 个是精确的，但它们有很多，并且作为一个整体在 3d 中绘制时形成一个 \xe2\x80\x9chollowed mountain\xe2\x80\x9d 类似的形状（所以在在我的想象中，轮廓线只是均匀分布的水平切片）。

我没有表示 z = f(x,y) 的函数。因此我不能只这样做：

plt.contour(x,y,z, contour_num)\n

因为这揭示了 z 必须是二维数组的预期错误。

然而，z 只是一组仅与基于位置的 x 和 y 相关的点。

如何在没有网格的情况下绘制此 \xe2\x80\x9cap 近似等高线图 \xe2\x80\x9d （是否有直接使用数据执行此操作的手动方法？）？

编辑注意：

另外，正如您所知，当我尝试类似的操作时出现的错误是 \xe2\x80\x9cValue Error: Cannot reshape array of size 3000 …

我已经在 C 中实现了用单精度（32 位浮点）计算的三角函数（sin、cos、arctan）的一些近似值。它们精确到大约 +/- 2 ulp。

我的目标设备不支持任何<cmath>方法<math.h>。它不提供FMA，而是提供MAC ALU。ALU 和 LU 以 32 位格式进行计算。

我的反正切近似实际上是N.juffa 近似的修改版本，它在整个范围内近似反正切。正弦和余弦函数在 [-pi,pi] 范围内精确度高达 2 ulp。

我现在的目标是为正弦和余弦提供更大的输入范围（尽可能大，最好是 [FLT_MIN,FLT_MAX]），这使我能够减少参数。

我目前正在阅读不同的论文，例如KCNg 的 A RGUMENT REDUCTION FOR HUGE ARGUMENTS: Good to the Last Bit或有关此新参数缩减算法的论文，但我无法从中导出实现。

另外，我想提一下两个涉及相关问题的 stackoverflow 问题：有一种使用 matlab 和 c++ 的方法，它基于我链接的第一篇论文。它实际上使用 matlab、cmath 方法，并将输入限制为 [0,20.000]。另一种已经在评论中提到了。这是一种在 C 中实现 sin 和 cos 的方法，使用了我无法使用的各种 c 库。由于这两篇文章已经有几年的历史了，可能会有一些新的发现。

看起来这种情况下最常用的算法是将 2/pi 的数量精确存储到所需的位数，以便能够准确地进行模计算，同时避免取消。我的设备不提供大型 DMEM，这意味着无法查找具有数百位的大型查找表。该过程实际上在本参考文献的第 70 页上进行了描述，顺便说一句，它提供了许多有关浮点数学的有用信息。

所以我的问题是：是否有另一种有效的方法来减少正弦和余弦的参数以获得单精度，避免使用大的 LUT？上面提到的论文实际上专注于双精度并使用最多 1000 位数字，这不适合我的用例。

实际上我还没有找到任何 C 语言的实现，也没有找到针对单精度计算的实现，我将不胜感激任何类型的提示/链接/示例...