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

@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, но вы же в конце все равно удалите

Новые блоги и статьи Все статьи Все блоги /
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .

@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