C++中两个向量的点积

6

我需要编写一个程序,可以输出两个向量的点积。

Organise the calculations using only Double type to get the most accurate result as it is possible.

How input should look like:

   N - vector length
   x1, x2,..., xN      co-ordinates of vector x (double type)
   y1, y2,..., yN      co-ordinates of vector y (double type)

Sample of input:

   4
   1.0e20 -1.0e3 0.1 1.0e20
   1.0 4.0 -4.0 -1.0

Output for vectors above:

   -4000.4 

这是我的代码(我还没有使用cin,因为我想首先编写带样例输入的可工作程序):

#include <iostream>
#include <numeric>
#include <vector>
#include <functional>

int main(){
//double N; //length of both vectors , will be used when I will have to input vectors by cin
//std::cin >> N;
//N = 4;

std::vector<double> x{1.0e20, -1.0e3, 0.1, 1.0e20};
std::vector<double> y{1.0, 4.0, -4.0, -1.0};
double result = std::inner_product(x.begin(), x.end(), y.begin(), 0);

std::cout << result;
return 0;
}

我的输出是-2.14748e+09,与预期结果相差甚远。我应该怎么做才能让它正常工作?


尝试检查每个乘法的结果以及每一步的部分和,我强烈怀疑这是浮点精度问题。 - Bob__
溢出或精度问题。 - Omid CompSCI
1
应该是 std::inner_product(x.begin(), x.end(), y.begin(), 0.0);。请注意,最后一个参数使用双精度浮点型字面量 0.0 而不是整型字面量 0 - joni
为了获得最准确的结果,您需要注意对产品求和的顺序。 - molbdnilo
double N; //length of both vectors length should be an integer, not double. The "standard" length type is size_t - phuclv
2个回答

6

第一个问题

这是在<numeric>中用于内积的函数模板:

template <class InputIterator1, class InputIterator2, class T>
   T inner_product (InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2, T init);

注意,定义输出类型T的是init参数。因此,给出你的输入:

std::inner_product(x.begin(), x.end(), y.begin(), 0);

init = 0,因此类型Tint。所以,当算法运行时,它将把double值强制转换为int值,最终将返回一个未定义的int值。

修复方法和第二个问题

要解决这个问题,您只需给出正确类型的init值(即,将double作为init参数)。只需使用0.0即可:

std::inner_product(x.begin(), x.end(), y.begin(), 0.0);

现在,当你对程序进行这个修正、编译并运行时,它仍然输出错误的结果0
这是因为当inner_product函数累加数值时,使用的是标准的double加法。 因此,你受到标准的double不精确性的影响,其机器ε是2^(-52) - 2.22E-16左右,在小数点后第十六位有误差,这意味着对于数字1E20,(1E20+x)=1E20对于所有的x<2^(-52)*1E20 ≈ 22204.46。 进一步解释这个问题:让我们在Python中求出1E20+23000(提醒:Python使用IEEE-754浮点运算,与标准C++编译器中的double精度相同)。
>>> 1e20 + 23000
1.0000000000000002e+20

所以你可以看到,小于二万的任何东西都被忽略或"吸收"在这个加法中。

由于其他数字都小于22204.46,1e20将只是"吸收"它们,直到加到-1E20,然后将它们"取消"掉并返回0

(简单)修复方法

解决第二个问题最简单的方法是使用long double而不是double。这种更精确的双精度类型具有2^(-63)-1.08E-19或约十九个小数位的机器epsilon,这意味着对于您的输入1E20,不精确度将等于2^(-63)*1E20,即约10.84。运行程序,输出将为-4000,非常接近预期答案。但这可能不是您的教授期望的结果,因为他特别要求输出精确地-4000.4

注意:显然,您可以选择另一种更精确的数字类型,但您的教授可能期望您使用double,因此我不会详细介绍它。

编辑:@phuclv在评论中提到的, 一些编译器没有将long double实现为80位浮点值,而是可能具有与double(64位)相同的精度。因此,您可能需要寻找提供正确的80位精度long double或甚至128位IEEE-754四倍精度浮点类型的库。尽管这绝对不会被认为是"简单"的。

(大部分正确的)修复方法

嗯,你不能无限精确,因为double类型的epsilon = 2^(-52),但你可以在加法中更聪明地处理,而不是直接将大值加到小值上(记住:由于double浮点运算的不精确性,大值"吸收"小值)。基本上,您应该计算一个具有值的成对乘法的数组,然后将其排序(基于绝对值),然后使用std::accumulate添加这些值:

#include <iostream>
#include <numeric>
#include <vector>
#include <functional>
//Mind the use of these two new STL libraries
#include <algorithm> //std::sort and std::transform
#include <cmath> //abs()



int main(){

    std::vector<double> x{1.0e20, -1.0e3, 0.1, 1.0e20};
    std::vector<double> y{1.0, 4.0, -4.0, -1.0};
    //The vector with the pairwise products
    std::vector<double> products(x.size());

    //Do element-wise multiplication
    //C code: products[i] += x[i] * y[i];
    std::transform(x.begin(), x.end(), y.begin(), products.begin(), std::multiplies<double>());

    //Sort the array based on absolute-value
    auto sort_abs = [] (double a, double b) { return abs(a) < abs(b); };
    std::sort(products.begin(), products.end(), sort_abs);

    //Add the values of the products(note the init=0.0)
    double result = std::accumulate(products.begin(), products.end(), 0.0);

    std::cout << result << std::endl;
    return 0;
}

通过这段新代码,结果如预期所示:-4000.4

但它显然有其限制。例如,如果输入的向量是 v1 = {100.0, 1E20} 和 v2 = {10.0, 1.0},应该返回 100000000000000001000 作为结果,但显然只会返回1E20。


1
请注意,long double 并不能保证比 double 有更高的精度。例如,在 MSVC 和(几乎)所有微控制器上,它们具有相同的精度。 - phuclv
谢谢你的回答。现在我明白了它应该如何工作。我忘记了Double的限制。最后,我对向量有了更多的了解。 - GoldenRC
@phuclv 谢谢,我不知道。我会把它添加到我的答案中。 - Vinicius Almeida

3

这个代码片段中存在逻辑错误和一些数字问题。

  • std::inner_product 使用传递的初始值初始化累加器,因此它使用相同类型的累加器和返回值。该代码使用了一个整数0,而应该使用浮点数,如0.0
  • 向量中的值具有极大的数量级范围。浮点类型,如double,具有有限精度,无法表示每个可能的实数而不产生舍入误差。此外(由于这个原因),浮点数运算不是关联的,对它们执行操作的顺序敏感。

为了形象化,您可以运行以下代码片段。

#include <numeric>
#include <algorithm>
#include <array>
#include <fmt/core.h> // fmt::print

int main()
{
    using vec4d = std::array<double, 4>;
    
    vec4d x{1.0e20, 1.0e20, -1.0e3, 0.1};
    vec4d y{1.0, -1.0, 4.0, -4.0};
    
    vec4d z;
    std::transform( std::begin(x), std::end(x), std::begin(y), std::begin(z)
                  , std::multiplies<double>{} );
    std::sort(std::begin(z), std::end(z));

    fmt::print("{0:>{1}}\n", "sum", 44);
    fmt::print("{0:->{1}}", '\n', 48);
    do {
        for (auto i : z) {
            fmt::print("{0:8}", i);
        }
        auto sum{ std::accumulate(std::begin(z), std::end(z), 0.0) };
        fmt::print("{0:{1}.{2}f}\n", sum, 14, 1);
    } while ( std::next_permutation(std::begin(z), std::end(z)) );
}

这是它的输出:

                                         sum
-----------------------------------------------
  -1e+20   -4000    -0.4   1e+20           0.0
  -1e+20   -4000   1e+20    -0.4          -0.4
  -1e+20    -0.4   -4000   1e+20           0.0
  -1e+20    -0.4   1e+20   -4000       -4000.0
  -1e+20   1e+20   -4000    -0.4       -4000.4
  -1e+20   1e+20    -0.4   -4000       -4000.4
   -4000  -1e+20    -0.4   1e+20           0.0
   -4000  -1e+20   1e+20    -0.4          -0.4
   -4000    -0.4  -1e+20   1e+20           0.0
   -4000    -0.4   1e+20  -1e+20           0.0
   -4000   1e+20  -1e+20    -0.4          -0.4
   -4000   1e+20    -0.4  -1e+20           0.0
    -0.4  -1e+20   -4000   1e+20           0.0
    -0.4  -1e+20   1e+20   -4000       -4000.0
    -0.4   -4000  -1e+20   1e+20           0.0
    -0.4   -4000   1e+20  -1e+20           0.0
    -0.4   1e+20  -1e+20   -4000       -4000.0
    -0.4   1e+20   -4000  -1e+20           0.0
   1e+20  -1e+20   -4000    -0.4       -4000.4
   1e+20  -1e+20    -0.4   -4000       -4000.4
   1e+20   -4000  -1e+20    -0.4          -0.4
   1e+20   -4000    -0.4  -1e+20           0.0
   1e+20    -0.4  -1e+20   -4000       -4000.0
   1e+20    -0.4   -4000  -1e+20           0.0

请注意,“正确”的答案是-4000.4,只有在较大的项(1e+20和-1e+20)在第一个求和中抵消时才会出现。这是由于所选输入数字的特定数字造成的人为因素,其中最大的两个数字在大小方面是相等的,并且符号相反。通常,减去两个几乎相同的数字会导致灾难性的抵消和重要性的丧失。
接下来最好的结果是-4000.0,当在大小方面较小的值0.4“接近”最大值时,它被抵消掉。
可以采用各种技术来减少求和许多项时增长的数值误差,例如pairwise summation或补偿求和(参见例如Kahan summation)。 在这里,我使用相同的样本测试了Neumaier求和。

非常感谢。现在理解它的工作原理要容易得多了。 - GoldenRC

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接