c++ - 2 个 vector C++ 的点积

Question

我必须编写输出两个 vector 的点积的程序。

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 所以它甚至不接近预期的输出。我应该怎么做才能使它工作？

Answer 1

(第一)问题
这是<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 ，因此类型 T是 int .所以，当算法运行时，它会类型转换 double值转换为 int s 最终将返回一个未定义的 int值(value)。
“修复”和第二个问题
修复问题 , 你所要做的就是给出一个正确输入的 init值(即，给出 double 作为 init 参数)。刚刚 0.0会做:

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

现在，当您编译并运行带有该修复程序的程序时， 它仍然会输出错误的结果 : 0这是因为当 inner_product函数累积值，它使用标准 double添加。因此，您必须遵守标准 double不精确， which has a machine epsilon 2^(-52) — 2.22E-16 或小数点后十六位的不精确度 — 这意味着，对于数字 1E20，对于所有 x < 2^(-52)*1E20，(1E20 + x) = 1E20 ≈ 22204.46。
为了说明这一点 ，让我们添加 1E20 + 23000在python解释器中(提醒python使用 IEEE-754 floating point arithmetic ，它等于标准C++编译器中 double的精度):

>>> 1e20 + 23000
1.0000000000000002e+20

因此，您会看到添加中忽略/“吸收”了少于两万的任何内容。
由于您的其他数字小于 22204.46，1e20 只会“吸收”它们，直到它被添加到 -1E20，然后“取消”并返回 0 .
(简单)修复
解决第二个问题的最简单方法是使用 long double而不是 double .这种更精确的 double 类型的机器 epsilon 为 2^(-63) — 1.08E-19 或大约 19 个小数位 — 这意味着，对于您的输入 1E20，不精确将等于 2^(-63) *1E20，或约 10.84。运行程序，输出为 -4000 ，这与预期的答案非常接近。 但这可能不是您教授所期望的 ，因为他特别要求输出精确 -4000.4 .
注意:显然，您可以使用另一种更精确的数字类型，但您的教授可能希望您使用 double ，所以我不会详细介绍。
编辑:如 @phuclv评论中提到， some compilers不执行 long double作为 80 位浮点值，但可能具有与 double 相同的精度(64 位)。因此，您可能需要寻找提供适当 80 位精度的库 long double s 甚至 128-bit IEEE-754 quadruple-precision浮点类型。虽然这绝对不会被认为是“容易的”。
(大部分是正确的)修复
好吧，你不能无限精确，因为 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坚韧它显然有它的局限性。例如，如果输入是 vector v1 = {100.0, 1E20} 和 v2 = {10.0, 1.0}，则应返回 100000000000000001000结果，显然只会返回 1E20。