Максимальная точность для чисел с плавающей точкой

@StolenCookie · Регистрация: 23.03.2018

Студворк — интернет-сервис помощи студентам

Суть поставленной задачи: дан вектор от 10_000 до 100_000 элементов, нужно проходить по вектору, брать два первых значения которые должны быть минимальными в векторе, вычисляем заданный процент от этих чисел, результат добавляем обратно в вектор чтобы он оставался отсортированным, два первых значения удаляем из вектора. Ответ это последнее число оставшееся в векторе.

Вопрос такой: как достичь максимально возможной точности при этих вычислениях, как не потерять милионные у double? Я заметил что, он отсекает довольно жестко числа, на Python результат мог быть 1.7355299999999998 тогда как на C++ получаю 1.73553. На C++ не пишу, решил данную задачу с использованием языка Python, там точность удовлетворяет всем тестам поставленной задачи, однако время выполнения кода Python гораздо больше чем C++, поэтому я решил этот алгоритм воплотить на C++.

Идея как сохранить милионные доли :
- сохранять числа после "," в long long и затем конвертируя в double добавлять к результату(не знаю как реализовать и не знаю поможет ли сохранить точность);

Пример на 100 элементах

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void) {
    double percent = 5.023;
    
    vector<double> v = {4736.672140518191, 370.20560577748165,
    7824.503468418985, 9968.678288247196, 552.0215066222, 2170.244286475398,
    6192.7791814058355, 4927.363346750624, 7879.810103521766,
    797.2098513115455, 7462.806163471812, 3068.872156880171,
    7657.036086346869, 1704.9269731581974, 8052.250320982811,
    8714.339301541788, 1827.3152883987364, 7310.8179741642425,
    7557.263244559295, 6693.767439796644, 1683.5316019595903,
    5994.257565688173, 602.9555356107074, 6567.084884832069,
    4540.323700822444, 3168.086862075651, 9863.028259686305,
    7987.967191887508, 5884.644983158085, 4246.986926593025,
    4435.892852109723, 2515.3640726612357, 366.70771759479413,
    9500.896240471217, 6466.592228368489, 6644.3980775342025,
    9039.47880626952, 2146.465840281503, 812.464152829182, 6384.543308568792,
    9762.496549897227, 1627.9778420167224, 9951.763436022391,
    9697.589795353842, 5251.596446220592, 1255.8529740398694,
    156.1029718953455, 6607.901752051685, 985.2465010896805,
    9586.037927405972, 5382.691326751201, 4963.9199239590125,
    3810.4268155912537, 6826.385996531188, 366.22162518377354,
    9747.270187859016, 4820.881952260375, 3614.229494366743,
    9561.652374746454, 4308.4678598754035, 6018.208591561486,
    2793.985752367261, 8252.823147577697, 9116.463141195245,
    5742.522574630054, 277.47913526242064, 9682.850366476561,
    5842.791895271258, 28.783409240891178, 7552.566598806799,
    2490.7839473270656, 6528.506470259108, 8886.709438616332,
    6417.959103490428, 7962.60638770992, 95.01138411451615,
    6154.411340373068, 2999.545284647318, 4405.1869437042415,
    8402.519626549632, 1807.1409803047534, 4827.597375450656,
    8472.444606885023, 3558.1783761815723, 5460.6227038715115,
    4183.33083687942, 2689.871540490688, 4407.541550002077,
    8402.340810170253, 8204.831766251174, 7057.6784912146095,
    5465.179372366143, 5257.751351404398, 3369.7583751234993,
    7426.79378177493, 4541.352097020977, 8448.229843013882,
    2529.193000531962, 497.6264190973612, 6995.366944780006};
 
    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);
      
    }
}

@Aymurat · 23.03.2018, 12:03

percent можно выразить как $https://www.cyberforum.ru/cgi-bin/latex.cgi?5023 * {10}^{-3}$ и оно не длинное
Также можно умножить все ваши числа с плавающей точкой на пару десятков, а то и сотен, чтобы цифр после точек не было совсем. Можно реализовать структуру long num(длинная арифметика, реализована в библиотеке boost или же см. e-maxx.ru/algo/)
Как мы знаем, (a + b) / l = a / l + b / l
Каждый раз будем умножать на какую то степень десятки, в конце расположим точку на позиции длина_числа - количество_умноженных_десяток
Должно сработать

@anapshy · 23.03.2018, 12:33

Нашел в интернете, может будет полезным.
https://github.com/vpiotr/decimal_for_cpp

@Renji · 23.03.2018, 12:38

Сообщение от StolenCookie

Вопрос такой: как достичь максимально возможной точности при этих вычислениях, как не потерять милионные у double? Я заметил что, он отсекает довольно жестко числа, на Python результат мог быть 1.7355299999999998 тогда как на C++ получаю 1.73553.

double ничего не отсекает, у него мантисса - 52 бита или 15 знаков. Отсекает cout и правильно делает, потому что хвост "99999999998" никакого смысла не несет. Видите ли, числа с плавающей запятой хранятся в форме X делить/умножить на два в степени Y. А десятичные дроби при записи в таком формате превращаются в дроби бесконечные. Дальше хвост этой периодической дроби обрубается и вы получаете то самое "и девять в периоде" на выходе.

Но если так уж нужно полюбоваться на хвост из девяток, то:

C++
1
std::cout<<std::setprecision(20);

@StolenCookie · 23.03.2018, 12:44 **[ТС]**

Сообщение от Renji

хвост "99999999998" никакого смысла не несет

Какие конкретно "9"? В данном примере при использовании setprecision

C++
1
2
cout << *(v.begin()) << endl;                                  // 527.151
cout << setprecision(20) << *(v.begin()) << endl;    // 527.15093342013722122

На результат к сожалению не влияет

@Renji · 23.03.2018, 13:00

Сообщение от StolenCookie

акие конкретно "9"? В данном примере при использовании setprecision

Девятки из 1.7355299999999998 в вашем примере, "3342013722122" этим действительно не объяснишь. Ну, тогда только шаманить с длинной арифметикой, чтобы исключить ошибки округления.

@StolenCookie · 26.03.2018, 20:32 **[ТС]**

Сообщение от Aymurat

(a + b) / l = a / l + b / l

Благодарю за ответ, что значит эта строка? не совсем понял. Если к примеру все числа в векторе и сам процент были бы целым числом long double возможно ли упростить получение процента или избежать ошибки при вычислении?

@Ромаха · 26.03.2018, 21:12

А еще само решение у Вас чутка идиотское..
Может, конечно, так и нужно..
Но каждый раз запускать сортировку..
Тут или ручками за линию
Или юзайте сет за лог

@Aymurat · 27.03.2018, 08:47

StolenCookie, Нет разницы между (chislo1 + chislo2) / 2 и chislo1 / 2 + chislo2 / 2
То есть, можно ускорить программу, не сортируя посчитав percent процентов от чисел

@StolenCookie · 27.03.2018, 13:25 **[ТС]**

Сообщение от StolenCookie

нужно проходить по вектору, брать два первых значения которые должны быть минимальными в векторе, вычисляем заданный процент от этих чисел, результат добавляем обратно в вектор чтобы он оставался отсортированным, два первых значения удаляем из вектора.

Но ведь нам нужно находить процент от суммы мин чисел а не просто от случайных

@Aymurat · 27.03.2018, 17:53

StolenCookie, но вы же в конце все равно удалите

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@Aymurat 125 / 117 / 67 Регистрация: 07.11.2014 Сообщений: 788
	23.03.2018, 12:03
	percent можно выразить как $https://www.cyberforum.ru/cgi-bin/latex.cgi?5023 * {10}^{-3}$ и оно не длинное Также можно умножить все ваши числа с плавающей точкой на пару десятков, а то и сотен, чтобы цифр после точек не было совсем. Можно реализовать структуру long num(длинная арифметика, реализована в библиотеке boost или же см. e-maxx.ru/algo/) Как мы знаем, (a + b) / l = a / l + b / l Каждый раз будем умножать на какую то степень десятки, в конце расположим точку на позиции длина_числа - количество_умноженных_десяток Должно сработать 0

@anapshy 531 / 272 / 220 Регистрация: 14.11.2016 Сообщений: 1,052
	23.03.2018, 12:33
	Нашел в интернете, может будет полезным. https://github.com/vpiotr/decimal_for_cpp 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	26.03.2018, 21:12
	А еще само решение у Вас чутка идиотское.. Может, конечно, так и нужно.. Но каждый раз запускать сортировку.. Тут или ручками за линию Или юзайте сет за лог 0

@Aymurat 125 / 117 / 67 Регистрация: 07.11.2014 Сообщений: 788
	27.03.2018, 08:47
	StolenCookie, Нет разницы между (chislo1 + chislo2) / 2 и chislo1 / 2 + chislo2 / 2 То есть, можно ускорить программу, не сортируя посчитав percent процентов от чисел 0

@Aymurat 125 / 117 / 67 Регистрация: 07.11.2014 Сообщений: 788
	27.03.2018, 17:53
	StolenCookie, но вы же в конце все равно удалите 0