How to remove the error when using double in calculations?

Question

C++ / C#

Given a vector with a length of up to 200,000 elements, and a percentage of deductions. It is necessary to go through the vector, take the first two values ​​that should be minimal in the vector, calculate the given percentage of these numbers, add the result back to the vector so that it remains sorted, remove the first two values ​​from the vector. The answer is the last number left in the vector. It seems to me that in order to remove the error, you need to use a data type whose volume is more than that of double float, since tests with float pass only 70%, with long double 90%.

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void) {
    double percent = 5.023;
    
    vector<double> v ; // = {  значения от 0 до 10000  };
 
    vector<double>::iterator it;
 
    while(v.size()!= 1)
    {
      stable_sort(v.begin(), v.end());
      
      for (it = v.begin() ; it != v.end(); ++it)
        cout << ' ' << *it;
      cout << '\n';
      
      double a = *(v.begin()), b = *(v.begin()+1);
      double x = ( a + b ) * ( percent / 100 );
      
      v.push_back(x);
      v.erase(v.begin() , v.begin()+2);
      
    }
}

Answer 1

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;
const double percent = 5.023;
long double fn(const long double &one,const long double &two)
{
    return ((one + two) / 100) * percent;
}
int main()
{
    vector<long double> v;

    for(int i=0;i<=10000;++i)
    {
        v.push_back(i);
    }

    sort(v.begin(),v.end());
    partial_sum(v.begin(), v.end(), v.begin(),fn);
    long double sum = std::accumulate(v.begin(), v.end(), 0);
    cout<<sum<<endl; //2.63956e+06
    return 0;
}

As a variant of your algorithm, only 10 times faster.
sorting is not necessary; the set is ordered.

#include <iostream>
#include <numeric>
#include <set>
#include <algorithm>
#include <iterator>
using namespace std;

const double percent = 5.023;
typedef long double ddouble;
typedef multiset<ddouble> DblSet;

int main() {

    int size = 10;
    ddouble *d = new ddouble[size];
    for(int i=0;i<size;++i)
    {
        d[i]=i;
    }
    DblSet myset(d,d+size);
    ostream_iterator<ddouble> output( cout, " ");

    while(myset.size()!=1)
    {
        ddouble a = *myset.begin();
        myset.erase(myset.begin());
        ddouble b = *myset.begin();
        myset.erase(myset.begin());
        myset.insert(myset.begin(),((a+b)/100)*percent);
    }

    copy(myset.begin(),myset.end(),output);
    delete d;
    return 0;
}

I got 0.723 sec for 200000 elements.
for 10 million items 28 seconds.

Answer 2

Use a long number library like GMP .

Answer 3

You can try to change the order of arithmetic operations. For example, first multiply, and then divide by 100, and not as it is now, so that numbers of the same order participate in arithmetic. The error can decrease a little
. Even better, if you first multiply all the values ​​in the vector by 100, remove the division by 100 from the loop, and only after the loop, divide the last number by 100. This will greatly reduce the number of calculations and reduce the error.