OccamaRazor
@OccamaRazor

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

Дан вектор длиной до 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);
      
    }
}
  • Вопрос задан
  • 1076 просмотров
Решения вопроса 1
myjcom
@myjcom Куратор тега C++
#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 секунд.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Использовать библиотеку длинных чисел, например GMP.
Ответ написан
maaGames
@maaGames
Погроммирую программы
Можно попробовать поменять порядок арифметический операций. Например, сперва умножать, а потом делить на 100, а не как сейчас, чтобы в арифметике участвовали числа одного порядка. Немножко погрешность может снизиться
Ещё лучше, если сперва все значения в векторе умножить на 100, убрать из цикла деление на 100 и только после цикла, последнее число разделить на 100. Это сильно уменьшит число вычислений и снизит погрешность.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы