Как убрать погрешность при использовании double в вычислениях?

Question

[OccamaRazor]

Дан вектор длиной до 200 000 элементов, и процент отчислений. Нужно проходить по вектору, брать два первых значения которые должны быть минимальными в векторе, вычисляем заданный процент от этих чисел, результат добавляем обратно в вектор чтобы он оставался отсортированным, два первых значения удаляем из вектора. Ответ это последнее число оставшееся в векторе. Мне кажется чтобы убрать погрешность нужно использовать тип данных объём которого более чем у double float, так как тесты с float проходят лишь на 70%, с 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

[Roman]

#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;
}

Как вариант Вашего алгоритма, только в 10 раз быстрее.
сортировать не нужно множество упорядочено.

#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;
}

у меня получилось для 200000 элементов 0.723 сек.
для 10 миллионов элементов 28 секунд.

Comments

[Roman]

для 100000 элементов. на 130000 отваливается пока не понял почему

[Roman]

затупил, нужно в куче

ddouble *d = new ddouble[size];

[OccamaRazor]

Подскажите, пожалуйста, можно ли этой структурой пользоваться на больших числах? У меня выдаёт на тестах погрешность на последних тестах, видимо где-то на 100 000 ошибка в вчычислениях, может в long long преобразовать и затем считать процент? Число каждую итерацию страдает из-за вычисления процента умножения и деления

[Roman]

ru.cppreference.com/w/cpp/language/types
используйте какой нужен.

Answer 2

[Rsa97]

Использовать библиотеку длинных чисел, например GMP.

Comments

[OccamaRazor]

А если запрещено применение библиотек?

[Rsa97]

OccamaRazor, Тогда писать свою длинную арифметику необходимой точности.

Answer 3

[maaGames]

Можно попробовать поменять порядок арифметический операций. Например, сперва умножать, а потом делить на 100, а не как сейчас, чтобы в арифметике участвовали числа одного порядка. Немножко погрешность может снизиться
Ещё лучше, если сперва все значения в векторе умножить на 100, убрать из цикла деление на 100 и только после цикла, последнее число разделить на 100. Это сильно уменьшит число вычислений и снизит погрешность.

Comments

[OccamaRazor]

Благодарю за идею! Сейчас попробую, интересно что я заметил погрешность появляется только в числах после запятой и в основном на больших обрабатываемых данных отчётливо видна, только что пробовал векторс с 100 000 элементов обрабатывать и что странно в Ruby 198134590.93999999 , C++ 198134590,59 , то есть где-то недобор идёт постепенно

[maaGames]

OccamaRazor, Там не совсем до запятой, у очень больших чисел и в целой части может возникать погрешность (при большой экспоненте). Почитайте про представление вещественных чисел в википедии, Станет понятнее, почему иногда есть погрешность, а иногда нет.)

[OccamaRazor]

maaGames, благодарю за совет, но разве можно вычислять процент от двух полученных чисел из вектора уже после всего цикла как вы предложили? В задании сказано брать два значения и вычислять процент от их суммы а не от суммы всего вектора

[maaGames]

OccamaRazor,
a/100 + b/100 == (a + b)/100

Множитель можно вынести за скобки. Хотя, конечно, в цельном алгоритме мог и ошибиться. Но, Кажется, можно вынести за скобки.